[RUBY] Insertion sort implementation

Foreword

An article about programming beginners implementing algorithms from one end. This time, insert sort is written in C, Java, Ruby, Python. If there are any improvements in the code, I would appreciate it if you could teach me.

Insertion sort features

・ Effective for arrays with a small number of elements -Effective for arrays that are almost aligned or have many overlapping elements (Because the number of element replacements is reduced) ・ Average complexity [^ 1] is $ O $ ($ n ^ 2 $) [^ 2] (To replace each of n elements on average a constant multiple of n)

[^ 1]: Computational complexity: Algorithm evaluation criteria. Obtained based on constituent instructions. [^ 2]: Order notation: Notation indicating the amount of calculation. Terms and coefficients other than the terms with the highest degree are ignored.

C language

/*size is the size of the array*/
void insertionSort(int data[10], int size) {
	int i, j;
	for(i = 1; i < size; i++) {
		j = i;
		while(j > 0 && data[j - 1] > data[j]) {
			swap(&data[j - 1], &data[j]);
			j--; 
		}
	}
}

void swap(int *a, int *b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

Java

public static void insertionSort(int[] data) {	
	int i, j;
	for(i = 1; i < data.length; i++) {
        j = i;
        while(j > 0 && data[j - 1] > data[j]) {
            swap(data, j);
            j--; 
        }
    }
}

public static void swap(int[] data, int j) {
	int tmp;
	tmp = data[j];
	data[j] = data[j - 1];
	data[j - 1] = tmp;
}

Ruby

def insertionSort(data)
	(1...data.length).each do |i|
		j = i
		while j > 0 && data[j - 1] > data[j]
			data[j - 1], data[j] = data[j], data[j - 1]
			j -= 1
		end
	end
end

Python

def insertionSort(data):
	for i in range(1, len(data)):
		j = i
		while j > 0 and data[j - 1] > data[j]:
				data[j - 1], data[j] = data[j], data[j - 1]
				j -=1

What I noticed

-Java reference type variables are "String", "Array", "Class" ・ In Ruby and Python, the elements can be replaced in one line. -Ruby for statement is interpreted as each method (When the each method is changed, the behavior of the for statement also changes) ・ "&&" and "and" are different in Ruby etc. Reference: Difference between && and and

References / Sites

--"Algorithm Reference", O'Reilly Japan, April 2010 --Takahiro Hara, Satoshi Mizuta, Takenao Okawa, "Digital Series 10 Algorithms and Data Structures for the Future", Kyoritsu Shuppan, June 2012 --Source Code Expedition https://www.codereading.com/algo_and_ds/algo/insertion_sort.html

Recommended Posts

Insertion sort implementation
Insertion sort
visualize insertion sort
sort
Selection Sort
Closure implementation
[Python] Sort
Natural sort
Bubble sort
Bubble sort