Anonymous user
Sorting algorithms/Insertion sort: Difference between revisions
m
{{out}}
(Added zkl) |
m ({{out}}) |
||
Line 2:
{{Sorting Algorithm}}
{{wikipedia|Insertion sort}}
{{omit from|GUISS}}▼
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
(i) small <span style="font-family: serif">''n''</span>, <br>
(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 [[wp:Insertion_sort#Algorithm|wikipedia]]):
Line 104 ⟶ 109:
FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line);
print((data))</lang>
{{out}}
<pre>
abcdefghiijklmnopqrstuvwxyz
Line 187 ⟶ 192:
END SUB</lang>
{{out}}
<pre>
1486 ; 9488 ; 9894 ; 17479 ; 18989 ; 23119 ; 23233 ; 24927 ; 25386 ; 26689 ;
</pre>
=={{header|BBC BASIC}}==
Line 213 ⟶ 220:
NEXT
ENDPROC</lang>
{{out}}
<pre>
-31 0 1 2 2 4 65 83 99 782
Line 269 ⟶ 276:
std::cout << "\n";
}</lang>
{{out}}
<pre>
-199 -52 2 3 33 56 99 100 177 200
Line 471 ⟶ 478:
Readln;
end.</lang>
{{out}}
<pre>
0 3 86 20 27 67 31 16 37 42 8 47 7 84 5 29
Line 654 ⟶ 661:
pretty_print(1,insertion_sort(s),{2})</lang>
{{out}}
<pre>Before: {
4,
Line 811 ⟶ 818:
fmt.Println("sorted! ", list)
}</lang>
{{out}}
<pre>
unsorted: [31 41 59 26 53 58 97 93 23 84]
Line 840 ⟶ 847:
fmt.Println("sorted! ", list)
}</lang>
{{out}}
<pre>
unsorted: [31 41 59 26 53 58 97 93 23 84]
Line 870 ⟶ 877:
fmt.Println("sorted! ", list)
}</lang>
{{out}}
<pre>
unsorted: [31 41 59 26 53 58 97 93 23 84]
Line 896 ⟶ 903:
println (insertionSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))</lang>
{{out}}
<pre>..................................................................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]
...............................................................................................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]</pre>
Line 945 ⟶ 952:
Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'sortop', and 'demosort' in Bubble Sort]]. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.
{{out|abbreviated}}
on list : [ 3 14 1 5 9 2 6 3 ]
with op = &null: [ 1 2 3 3 5 6 9 14 ] (0 ms)
Line 1,302 ⟶ 1,310:
return ArrayList(A)
</lang>
{{out}}
<pre>
UK London
Line 1,336 ⟶ 1,344:
insertSort a
echo a</lang>
{{out}}
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
Line 1,450 ⟶ 1,458:
print "@a\n";
</lang>
{{out}}
-31 0 1 2 4 65 83 99 782
Line 1,471 ⟶ 1,479:
</lang>
{{out}}
output = -5 2 4 7 8 22
</pre>
Line 1,500 ⟶ 1,509:
(rot J (offset I J)) ) ) )
Lst )</lang>
{{out}}
<pre>: (insertionSort (5 3 1 7 4 1 1 20))
-> (1 1 1 3 4 5 7 20)</pre>
Line 1,676 ⟶ 1,685:
return a;
}</lang>
{{out}}
<lang rascal>rascal>rascal>insertionSort([4, 65, 2, -31, 0, 99, 83, 782, 1])
list[int]: [-31,0,1,2,4,65,83,99,782]</lang>
Line 1,732 ⟶ 1,741:
say copies('─',79) /*show a separator line that fits*/
return</lang>
{{out}}
<pre style="height:40ex;overflow:scroll">
element 1 before sort: ---Monday's Child Is Fair of Face (by Mother Goose)---
Line 1,919 ⟶ 1,928:
while output = A<i>; i = ?lt(i,aSize) i + 1 :s(while)
end</lang>
=={{header|Standard ML}}==
Line 2,013 ⟶ 2,021:
example = insort <45,82,69,82,104,58,88,112,89,74></lang>
{{out}}
<pre>
<45,58,69,74,82,82,88,89,104,112>
Line 2,076 ⟶ 2,084:
L("big","fjords","nymph","quick","vex","waltz")
</pre>
▲{{omit from|GUISS}}
| |||