Sorting algorithms/Insertion sort: Difference between revisions
Content added Content deleted
m (better formatting of the pseudocode) |
(Added PL/I; added text at top) |
||
| Line 1: | Line 1: | ||
[[Category:Less Than 20 Examples]]{{task|Sorting Algorithms}} |
[[Category:Less Than 20 Examples]]{{task|Sorting Algorithms}} |
||
{{Sorting Algorithm}} |
{{Sorting Algorithm}} |
||
An [[O]](n<sup>2</sup>) sorting algorithm which moves elements one at a time into the correct position. The algorithm |
An [[O]](n<sup>2</sup>) 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 [[O]](n<sup>2</sup>) algorithm, its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases (i) small n, (ii) as the final finishing-off algorithm for [[O]](n log n) algorithms such as mergesort and quicksort. |
|||
The algorithm is as follows (from the [[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''' |
||
| Line 324: | Line 328: | ||
Output: |
Output: |
||
-31 0 1 2 4 65 83 99 782 |
-31 0 1 2 4 65 83 99 782 |
||
=={{header|PL/I}}== |
|||
<lang PL/I> |
|||
INSSORT: PROCEDURE (A,N); |
|||
DCL (A(*)) FIXED BIN(31), |
|||
N FIXED BIN(31) NONASGN; |
|||
DCL (I,J,V) FIXED BIN(31); |
|||
DO I=2 TO N; |
|||
V=A(I); |
|||
J=I-1; |
|||
DO WHILE (J > 0 & A(J) > V); |
|||
A(J+1)=A(J); J-=1; |
|||
END; |
|||
A(J+1)=V; |
|||
END; |
|||
RETURN; |
|||
END INSSORT; |
|||
</lang> |
|||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||