Simple Sorting : Insertion Sort

The insertion sort is better than the bubble sort and the selection sort.

Process

For a better understanding, we will describe the process from the middle.

1. Outer loop : Record the current value (e.g. index 6) as temp (The values at the left are partially sorted).
2. Inner loop : Start comparison to the left
3. For each Inner pass : [If inner - 1 > temp] then [move inner - 1 to inner] else [move temp to inner]
4. Outer loop : move to the right (e.g. index 7)
5. continue above steps until end of outer loop

Java:

	int size = arr.length;
	for(int i = 1; i < size; i++){
	long temp = arr[i];
	int j = i;
	while(j > 0 && arr[j - 1] >= temp){
	arr[j] = arr[j - 1];
	--j;
	}
	a[j] = temp;
	}

view raw insertion_sort_java hosted with ❤ by GitHub

Python:

	for x in range(1, len(numbers)):
	temp = numbers[ x ]
	j = x
	for y in range(j, 0, -1):
	if numbers[ y - 1 ] >= temp:
	numbers[ y ] = numbers[ y - 1]
	j -= 1
	numbers[ j ] = temp

view raw insertion_sort_python hosted with ❤ by GitHub

The insertion sort runs in O(N²) time.

As a bonus, you can see below a version which removes duplicate:

	def sort_remove_duplicate(arr):
	size = len(arr)
	for x in range(1, size):
	temp = arr[x]
	j = x
	for y in range(j, 0, -1):
	if arr[y - 1] > temp:
	arr[y] = arr[y-1]
	j -= 1
	#when duplicate is found, write over with -1
	elif arr[y-1] == temp:
	arr[y] = temp
	temp = -1
	j -= 1
	arr[j] = temp
	#remove all the -1
	return [item for item in arr if item >= 0]

view raw insertion_sort_without_duplicate hosted with ❤ by GitHub