Sorting algorithms/Insertion sort: Difference between revisions
Content added Content deleted
(→Insertion sort with binary search: rm gap) |
(from the wikipedia -> from wikipedia) |
||
Line 6: | Line 6: | ||
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 (i) small <span style="font-family: serif">''n''</span>, (ii) 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]]. |
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 (i) small <span style="font-family: serif">''n''</span>, (ii) 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 |
The algorithm is as follows (from [[wp:Insertion_sort#Algorithm|wikipedia]]): |
||
'''function''' ''insertionSort''(array A) |
'''function''' ''insertionSort''(array A) |
||
'''for''' i '''from''' 1 '''to''' length[A]-1 '''do''' |
'''for''' i '''from''' 1 '''to''' length[A]-1 '''do''' |