32 lines
1.4 KiB
Plaintext
32 lines
1.4 KiB
Plaintext
{{Sorting Algorithm}}
|
|
[[Category:Sorting]]
|
|
{{wikipedia|Insertion sort}}
|
|
{{omit from|GUISS}}
|
|
|
|
<br>
|
|
An <span style="font-family: serif">[[O]](''n''<sup>2</sup>)</span> sorting algorithm which moves elements one at a time into the correct position.
|
|
The algorithm consists of inserting one element at a time into the previously sorted part of the array, moving higher ranked elements up as necessary.
|
|
To start off, the first (or smallest, or any arbitrary) element of the unsorted array is considered to be the sorted part.
|
|
|
|
Although insertion sort is an <span style="font-family: serif">[[O]](''n''<sup>2</sup>)</span> algorithm, its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases: <br>
|
|
|
|
:# small <span style="font-family: serif">''n''</span>, <br>
|
|
:# as the final finishing-off algorithm for <span style="font-family: serif">[[O]](''n'' log''n'')</span> algorithms such as [[Merge sort|mergesort]] and [[quicksort]].
|
|
|
|
|
|
The algorithm is as follows (from [[wp:Insertion_sort#Algorithm|wikipedia]]):
|
|
'''function''' ''insertionSort''(array A)
|
|
'''for''' i '''from''' 1 '''to''' length[A]-1 '''do'''
|
|
value := A[i]
|
|
j := i-1
|
|
'''while''' j >= 0 '''and''' A[j] > value '''do'''
|
|
A[j+1] := A[j]
|
|
j := j-1
|
|
'''done'''
|
|
A[j+1] = value
|
|
'''done'''
|
|
|
|
Writing the algorithm for integers will suffice.
|
|
<br><br>
|
|
|