Insertion sort
|
|
Insertion sort is a simple sort algorithm in which the sorted array (or list) is built one entry at a time. It is much less efficient than the more advanced algorithms such as quicksort, heapsort, or merge sort, but it has various advantages:
- Simple to implement
- Efficient on (quite) small data sets
- Efficient on data sets which are already substantially sorted
- Stable (does not change the order of already ordered elements)
- In-place
In abstract terms, each iteration of an insertion sort removes an element from the input data, inserting it at the correct position in the already sorted list, until no elements are left in the input. The choice of which element to remove from the input is arbitrary and can be made using almost any choice algorithm.
Sorting is typically done in-place. The result array after k iterations contains the first k entries of the input array and is sorted. In each step, the first remaining entry of the input is removed, inserted into the result at the right position, thus extending the result:
becomes:
Missing image
Insertionsort-after.png
The array right after insertion of x
with each element > x copied to the right as it is compared against x.
The algorithm can be described as:
- Start with the result being the first element of the input.
- Loop over the input array until it is empty, "removing" the first remaining (leftmost) element.
- Compare the removed element against the current result, starting from the highest (rightmost) element, and working left towards the lowest element.
- If the removed input element is lower than the current result element, copy that value into the following element to make room for the new element below, and repeat with the next lowest result element.
- Otherwise, the new element is in the correct location; save it in the cell left by copying the last examined result up, and start again from (2) with the next input element.
A simple pseudocode expression of the complete algorithm is:
function insertsort (A : list[0..n-1])
{
var int i, j;
for i from 0 to n - 1
{
value = a[i];
j := i - 1;
while (j >= 0) and (a[j] > value)
{
a[j+1] = a[j];
j = j - 1;
}
a[j+1] = value;
}
}
| Contents |
Implementations
C
void insertSort(int a[], size_t length) {
size_t i, j;
for(i = 1; i < length; i++) {
int value = a[i];
j = i - 1;
while (j >= 0 && a[j] > value) {
a[j+1] = a[j];
j--;
}
a[j+1] = value;
}
}
C#
static void InsertSort(IComparable[] array)
{
int i, j;
for (i = 1; i < array.Length; i++)
{
IComparable value = array[i];
j = i - 1;
while ((j >= 0) && (array[j].CompareTo(value) > 0))
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = value;
}
}
C# 2.0
static void InsertSort<T>(IList<T> list) where T : IComparable<T>
{
int i, j;
for (i = 1; i < list.Count; i++)
{
T value = list[i];
j = i - 1;
while ((j >= 0) && (list[j].CompareTo(value) > 0))
{
list[j + 1] = list[j];
j--;
}
list[j + 1] = value;
}
}
Haskell
insert :: Ord a => a -> [a] -> [a]
insert item [] = [item]
insert item (h:t) | item <= h = item:h:t
| otherwise = h:(insert item t)
insertsort :: Ord a => [a] -> [a]
insertsort [] = []
insertsort (h:t) = insert h (insertsort t)
Java
void insertionSort (int[] A)
{
for (int i = 1, j; i < A.length; i++)
{
int a = A[i];
for (j = i - 1; j >=0 && A[j] > a; j--)
{
A[j + 1] = A[j];
}
A[j + 1] = a;
}
}
ML
fun insertsort [] = []
| insertsort (x::xs) =
let fun insert (x:real, []) = [x]
| insert (x:real, y::ys) =
if x<=y then x::y::ys
else y::insert(x, ys)
in insert(x, insertsort xs)
end;
Perl
sub insert_sort {
for(my $i = 0; $i <= $#_; $i++) {
my ($j, $val) = ($i - 1, $_[$i]);
$_[$j-- + 1] = $_[$j] while ($j >= 0 && $_[$j] > $val);
$_[$j+1] = $val;
}
}
Python
def insertsort(array):
for removed_index in range(1, len(array)):
removed_value = array[removed_index]
insert_index = removed_index
while insert_index > 0 and array[insert_index - 1] > removed_value:
array[insert_index] = array[insert_index - 1]
insert_index = insert_index - 1
array[insert_index] = removed_value
Good and bad input cases
In the best case of an already sorted array, this implementation of insertion sort takes O(n) time: in each iteration, the first remaining element of the input is only compared with the last element of the result. It takes O(n2) time in the average and worst cases, which makes it impractical for sorting large numbers of elements. However, insertion sort's inner loop is very fast, which often makes it one of the fastest algorithms for sorting small numbers of elements, typically less than 10 or so.
Variants
D.L. Shell made substantial improvements to the algorithm, and the modified version is called Shell sort. It compares elements separated by a distance that decreases on each pass. Shellsort has distinctly improved running times in practical work, with two simple variants requiring O(n3/2) and O(n4/3) time.
If comparisons are very costly compared to swaps, as is the case for example with string keys stored by reference, then using binary insertion sort can be a good strategy. Binary insertion sort employs binary search to find the right place to insert new elements, and therefore performs <math>\lceil ln(n!) \rceil<math> comparisons in the worst case, which is Θ(n log n). The algorithm as a whole still takes Θ(n2) time on average due to the series of swaps required for each insertion, and since it always uses binary search, the best case is no longer O(n) but O(n log n).
To avoid having to make a series of swaps for each insertion, we could instead store the input in a linked list, which allows us to insert and delete elements in constant time. Unfortunately, binary search on a linked list is impossible, so we still spend Ω(n2) time searching. If we instead replace it by a more sophisticated data structure such as a heap or binary tree, we can significantly decrease both search and insert time. This is the essence of heap sort and binary tree sort.
Comparisons to other sorts
Insertion sort is very similar to bubble sort. In bubble sort, after k passes through the array, the k largest elements have bubbled to the top. (Or the k smallest elements have bubbled to the bottom, depending on which way you do it.) In insertion sort, after k passes through the array, you have a run of k sorted elements at the bottom of the array. Each pass inserts another element into the sorted run. So with bubble sort, each pass takes less time than the previous one, but with insertion sort, each pass may take more time than the previous one.
In contrast, C A R Hoare's Quicksort works by recursively dividing the array to be sorted into smaller runs each of which is sorted separately; highly optimized implementations of Quicksort often use insertion sort to sort these runs once they get "small enough".
External links
- Another animated Java applet showing a step-by-step insertion sort. (http://web.engr.oregonstate.edu/~minoura/cs162/javaProgs/sort/InsertSort.html)de:Insertionsort
fr:Tri par insertion it:Insertion sort lt:Įterpimo rūšiavimo algoritmas nl:Insertion sort ja:挿入ソート pl:Sortowanie przez wstawianie fi:Lisyslajittelu zh:插入排序