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) // Element 3 is sorted trivially
(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
1.
function insertionSort(array a)
2.
for
i in
0
-> a.length -
2
do
3.
j = i +
1
4.
tmp = a[j]
5.
while
j >
0
AND tmp > a[j-
1
]
do
//create a gap
6.
a[j] = a[j-
1
]
7.
j--
8.
a[j] = tmp
//insert
01.
/**
02.
* Insertion sort (descending order)
03.
* @param array array to be sorted
04.
*/
05.
public
static
void
insertionSort(
int
[] array) {
06.
for
(
int
i =
0
; i < array.length -
1
; i++) {
07.
int
j = i +
1
;
08.
int
tmp = array[j];
09.
while
(j >
0
&& tmp > array[j-
1
]) {
10.
array[j] = array[j-
1
];
11.
j--;
12.
}
13.
array[j] = tmp;
14.
}
15.
}
01.
/**
02.
* Insertion sort (descending order)
03.
* @param array array to be sorted
04.
* @param size size of the array
05.
*/
06.
void
insertionSort(
int
array[],
int
size) {
07.
for
(
int
i = 0; i < size - 1; i++) {
08.
int
j = i + 1;
09.
int
tmp = array[j];
10.
while
(j > 0 && tmp > array[j-1]) {
11.
array[j] = array[j-1];
12.
j--;
13.
}
14.
array[j] = tmp;
15.
}
16.
}
01.
/**
02.
* Insertion sort (descending order)
03.
* @param array array to be sorted
04.
*/
05.
public
static
void
InsertionSort(
int
[] array)
06.
{
07.
for
(
int
i = 0; i < array.Length - 1; i++)
08.
{
09.
int
j = i + 1;
10.
int
tmp = array[j];
11.
while
(j > 0 && tmp > array[j - 1])
12.
{
13.
array[j] = array[j - 1];
14.
j--;
15.
}
16.
array[j] = tmp;
17.
}
18.
}
01.
procedure
Insert(
var
X : ArrayType; N :
integer
);
02.
var
03.
J,
04.
K,
05.
Y :
integer
;
06.
Found :
boolean
;
07.
begin
08.
for
J :=
2
to
N
do
09.
begin
10.
Y := X[J];
11.
K := J -
1
;
12.
Found :=
false
;
13.
while
(K >=
1
)
14.
and
(
not
Found)
do
15.
if
(Y < X[K])
then
16.
begin
17.
X[K +
1
] := X[K];
18.
K := K -
1
19.
end
20.
else
21.
Found :=
true
;
22.
X[K +
1
] := Y;
23.
end
24.
end
;