Sorting algorithms/Insertion sort: Difference between revisions
Added PL/I; added text at top
m (better formatting of the pseudocode) |
(Added PL/I; added text at top) |
||
Line 1:
[[Category:Less Than 20 Examples]]{{task|Sorting Algorithms}}
{{Sorting Algorithm}}
An [[O]](n<sup>2</sup>) sorting algorithm which moves elements one at a time into the correct position. The algorithm
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)
'''for''' i '''from''' 1 '''to''' length[A]-1 '''do'''
Line 324 ⟶ 328:
Output:
-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}}==
| |||