Sorting algorithms/Insertion sort: Difference between revisions
Content added Content deleted
(formatting) |
m (better formatting of the pseudocode) |
||
| Line 3: | Line 3: | ||
An [[O]](n<sup>2</sup>) sorting algorithm which moves elements one at a time into the correct position. The algorithm is as follows (from the [[wp:Insertion_sort#Algorithm|wikipedia]]): |
An [[O]](n<sup>2</sup>) sorting algorithm which moves elements one at a time into the correct position. The algorithm is as follows (from the [[wp:Insertion_sort#Algorithm|wikipedia]]): |
||
'''function''' ''insertionSort''(array A) |
'''function''' ''insertionSort''(array A) |
||
'''for''' i |
'''for''' i '''from''' 1 '''to''' length[A]-1 '''do''' |
||
value = A[i] |
value := A[i] |
||
j = i-1 |
j := i-1 |
||
'''while''' j >= 0 '''and''' A[j] > value '''do''' |
'''while''' j >= 0 '''and''' A[j] > value '''do''' |
||
A[j |
A[j+1] := A[j] |
||
j = j-1 |
j := j-1 |
||
'''done''' |
|||
A[j+1] = value |
A[j+1] = value |
||
'''done''' |
|||
Writing the algorithm for integers will suffice. |
Writing the algorithm for integers will suffice. |
||