Insertion sort is a sorting algorithm based on comparison of elements. Insertion sort is stable and has quadratic asymptotic complexity . Generalized version of this algorithm is Shell sort, which is an insertion sort with diminishing increment.
Description
The idea of the insertion sort is simple:
- One element is sorted trivially
- Pick element next to the already sorted sequence and insert it to the correct place - move every element of the already sorted sequence, which has a higher value than the element being sorted, one place right, than put the element into the gap (correct place within the sequence).
- While array contains any unsorted elements GOTO: 2.
Advantages of insertion sort
If the input sequence is already sorted, than the insertion sort only checks the ordering and does not perform any moves. Hence if there are only few unsorted elements, the complexity of insertion sort gets close to . In these cases insertion sort outperforms divide-and-conquer algorithms with asymptotic complexity
such as quicksort, merge sort or heapsort.
Also for small inputs () the insertion sort tends to be faster than the algorithms mentioned above, so it might be used as a subroutine of divide-and-conquer algorithms for small sub-problems.
Visualization
Example
(3 2 8 7 6) // Pick 2 and insert it to the correct place (already done)
(3 2 8 7 6) // Insert 1 to the first place, move the elements 3 and 2 one place right
(8 3 2 7 6) // Insert 7 between 8 and 3, move 3 a 2 one place right
(8 7 3 2 6) // Insert 6 between 7 and 3, move 3 and 2 one place right
(8 7 6 3 2) // Sorted
Code
function insertionSort(array a)
for i in 0 -> a.length - 2 do
j = i + 1
tmp = a[j]
while j > 0 AND tmp > a[j-1] do //create a gap
a[j] = a[j-1]
j--
a[j] = tmp //insert
/**
* Insertion sort (descending order)
* @param array array to be sorted
*/
public static void insertionSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int j = i + 1;
int tmp = array[j];
while (j > 0 && tmp > array[j-1]) {
array[j] = array[j-1];
j--;
}
array[j] = tmp;
}
}
/**
* Insertion sort (descending order)
* @param array array to be sorted
* @param size size of the array
*/
void insertionSort(int array[], int size) {
for (int i = 0; i < size - 1; i++) {
int j = i + 1;
int tmp = array[j];
while (j > 0 && tmp > array[j-1]) {
array[j] = array[j-1];
j--;
}
array[j] = tmp;
}
}
/**
* Insertion sort (descending order)
* @param array array to be sorted
*/
public static void InsertionSort(int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
int j = i + 1;
int tmp = array[j];
while (j > 0 && tmp > array[j - 1])
{
array[j] = array[j - 1];
j--;
}
array[j] = tmp;
}
}
procedure Insert(var X : ArrayType; N : integer);
var
J,
K,
Y : integer;
Found : boolean;
begin
for J := 2 to N do
begin
Y := X[J];
K := J - 1;
Found := false;
while (K >= 1)
and (not Found) do
if (Y < X[K]) then
begin
X[K + 1] := X[K];
K := K - 1
end
else
Found := true;
X[K + 1] := Y;
end
end;