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.
・ 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.
/*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
-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
--"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