Sorting algorithms/Insertion sort: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 574: | Line 574: | ||
sorted .= "," . a%A_Index% |
sorted .= "," . a%A_Index% |
||
Return SubStr(sorted,2) ; drop leading comma |
Return SubStr(sorted,2) ; drop leading comma |
||
}</lang> |
}</lang> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
Line 739: | Line 739: | ||
-31 0 1 2 2 4 65 83 99 782 |
-31 0 1 2 2 4 65 83 99 782 |
||
</pre> |
</pre> |
||
=={{header|C sharp|C#}}== |
|||
<lang csharp>namespace Sort { |
|||
using System; |
|||
static class InsertionSort<T> where T : IComparable { |
|||
public static void Sort(T[] entries) { |
|||
Sort(entries, 0, entries.Length - 1); |
|||
} |
|||
public static void Sort(T[] entries, Int32 first, Int32 last) { |
|||
for (var i = first + 1; i <= last; i++) { |
|||
var entry = entries[i]; |
|||
var j = i; |
|||
while (j > first && entries[j - 1].CompareTo(entry) > 0) |
|||
entries[j] = entries[--j]; |
|||
entries[j] = entry; |
|||
} |
|||
} |
|||
} |
|||
}</lang> |
|||
'''Example''': |
|||
<lang csharp> using Sort; |
|||
using System; |
|||
class Program { |
|||
static void Main(String[] args) { |
|||
var entries = new Int32[] { 3, 9, 4, 6, 8, 1, 7, 2, 5 }; |
|||
InsertionSort<Int32>.Sort(entries); |
|||
Console.WriteLine(String.Join(" ", entries)); |
|||
} |
|||
}</lang> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
Line 774: | Line 808: | ||
-199 -52 2 3 33 56 99 100 177 200 |
-199 -52 2 3 33 56 99 100 177 200 |
||
</pre> |
</pre> |
||
=={{header|C sharp|C#}}== |
|||
<lang csharp>namespace Sort { |
|||
using System; |
|||
static class InsertionSort<T> where T : IComparable { |
|||
public static void Sort(T[] entries) { |
|||
Sort(entries, 0, entries.Length - 1); |
|||
} |
|||
public static void Sort(T[] entries, Int32 first, Int32 last) { |
|||
for (var i = first + 1; i <= last; i++) { |
|||
var entry = entries[i]; |
|||
var j = i; |
|||
while (j > first && entries[j - 1].CompareTo(entry) > 0) |
|||
entries[j] = entries[--j]; |
|||
entries[j] = entry; |
|||
} |
|||
} |
|||
} |
|||
}</lang> |
|||
'''Example''': |
|||
<lang csharp> using Sort; |
|||
using System; |
|||
class Program { |
|||
static void Main(String[] args) { |
|||
var entries = new Int32[] { 3, 9, 4, 6, 8, 1, 7, 2, 5 }; |
|||
InsertionSort<Int32>.Sort(entries); |
|||
Console.WriteLine(String.Join(" ", entries)); |
|||
} |
|||
}</lang> |
|||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
Line 1,232: | Line 1,232: | ||
end</lang> |
end</lang> |
||
=={{header|Elena}}== |
=={{header|Elena}}== |
||
ELENA 5.0 : |
ELENA 5.0 : |
||
Line 1,622: | Line 1,623: | ||
<pre>unsort -7 -1 4 -6 5 2 1 -2 0 -5 -4 6 -3 7 3 |
<pre>unsort -7 -1 4 -6 5 2 1 -2 0 -5 -4 6 -3 7 3 |
||
sort -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7</pre> |
sort -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7</pre> |
||
=={{header|GAP}}== |
=={{header|GAP}}== |
||
<lang gap>InsertionSort := function(L) |
<lang gap>InsertionSort := function(L) |
||
Line 2,004: | Line 2,006: | ||
{{Out}} |
{{Out}} |
||
[null,-1.1,1,1,1.1,2,[null],{"null":null}] |
[null,-1.1,1,1,1.1,2,[null],{"null":null}] |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Line 2,260: | Line 2,261: | ||
END IntSort; |
END IntSort; |
||
END InsertSort.</lang> |
END InsertSort.</lang> |
||
=={{header|Nanoquery}}== |
|||
{{trans|Python}} |
|||
<lang Nanoquery>def insertion_sort(L) |
|||
for i in range(1, len(L) - 1) |
|||
j = i - 1 |
|||
key = L[i] |
|||
while (L[j] > key) and (j >= 0) |
|||
L[j + 1] = L[j] |
|||
j -= 1 |
|||
end |
|||
L[j+1] = key |
|||
end |
|||
return L |
|||
end</lang> |
|||
=={{header|N/t/roff}}== |
=={{header|N/t/roff}}== |
||
Line 2,384: | Line 2,369: | ||
.insertionsort a |
.insertionsort a |
||
.a.dump</lang> |
.a.dump</lang> |
||
=={{header|Nanoquery}}== |
|||
{{trans|Python}} |
|||
<lang Nanoquery>def insertion_sort(L) |
|||
for i in range(1, len(L) - 1) |
|||
j = i - 1 |
|||
key = L[i] |
|||
while (L[j] > key) and (j >= 0) |
|||
L[j + 1] = L[j] |
|||
j -= 1 |
|||
end |
|||
L[j+1] = key |
|||
end |
|||
return L |
|||
end</lang> |
|||
=={{header|Nemerle}}== |
=={{header|Nemerle}}== |
||
Line 2,657: | Line 2,658: | ||
{InsertionSort Arr} |
{InsertionSort Arr} |
||
{Show {Array.toRecord unit Arr}}</lang> |
{Show {Array.toRecord unit Arr}}</lang> |
||
=={{header|Qi}}== |
|||
Based on the scheme version. |
|||
<lang qi>(define insert |
|||
X [] -> [X] |
|||
X [Y|Ys] -> [X Y|Ys] where (<= X Y) |
|||
X [Y|Ys] -> [Y|(insert X Ys)]) |
|||
(define insertion-sort |
|||
[] -> [] |
|||
[X|Xs] -> (insert X (insertion-sort Xs))) |
|||
(insertion-sort [6 8 5 9 3 2 1 4 7]) |
|||
</lang> |
|||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
Line 2,709: | Line 2,696: | ||
{{out}} |
{{out}} |
||
-31 0 1 2 4 65 83 99 782 |
-31 0 1 2 4 65 83 99 782 |
||
=={{header|Perl 6}}== |
|||
<lang perl6>sub insertion_sort ( @a is copy ) { |
|||
for 1 .. @a.end -> $i { |
|||
my $value = @a[$i]; |
|||
my $j; |
|||
loop ( $j = $i-1; $j >= 0 and @a[$j] > $value; $j-- ) { |
|||
@a[$j+1] = @a[$j]; |
|||
} |
|||
@a[$j+1] = $value; |
|||
} |
|||
return @a; |
|||
} |
|||
my @data = 22, 7, 2, -5, 8, 4; |
|||
say 'input = ' ~ @data; |
|||
say 'output = ' ~ @data.&insertion_sort; |
|||
</lang> |
|||
{{out}} |
|||
<pre>input = 22 7 2 -5 8 4 |
|||
output = -5 2 4 7 8 22 |
|||
</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 2,939: | Line 2,903: | ||
for i in range(1, len(seq)): |
for i in range(1, len(seq)): |
||
bisect.insort(seq, seq.pop(i), 0, i)</lang> |
bisect.insort(seq, seq.pop(i), 0, i)</lang> |
||
=={{header|Qi}}== |
|||
Based on the scheme version. |
|||
<lang qi>(define insert |
|||
X [] -> [X] |
|||
X [Y|Ys] -> [X Y|Ys] where (<= X Y) |
|||
X [Y|Ys] -> [Y|(insert X Ys)]) |
|||
(define insertion-sort |
|||
[] -> [] |
|||
[X|Xs] -> (insert X (insertion-sort Xs))) |
|||
(insertion-sort [6 8 5 9 3 2 1 4 7]) |
|||
</lang> |
|||
=={{header|R}}== |
=={{header|R}}== |
||
Line 2,994: | Line 2,972: | ||
[else (cons y (insert x rst))])])) |
[else (cons y (insert x rst))])])) |
||
(foldl insert '() l))</lang> |
(foldl insert '() l))</lang> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
<lang perl6>sub insertion_sort ( @a is copy ) { |
|||
for 1 .. @a.end -> $i { |
|||
my $value = @a[$i]; |
|||
my $j; |
|||
loop ( $j = $i-1; $j >= 0 and @a[$j] > $value; $j-- ) { |
|||
@a[$j+1] = @a[$j]; |
|||
} |
|||
@a[$j+1] = $value; |
|||
} |
|||
return @a; |
|||
} |
|||
my @data = 22, 7, 2, -5, 8, 4; |
|||
say 'input = ' ~ @data; |
|||
say 'output = ' ~ @data.&insertion_sort; |
|||
</lang> |
|||
{{out}} |
|||
<pre>input = 22 7 2 -5 8 4 |
|||
output = -5 2 4 7 8 22 |
|||
</pre> |
|||
=={{header|Rascal}}== |
=={{header|Rascal}}== |
||
Line 3,351: | Line 3,353: | ||
while output = A<i>; i = ?lt(i,aSize) i + 1 :s(while) |
while output = A<i>; i = ?lt(i,aSize) i + 1 :s(while) |
||
end</lang> |
end</lang> |
||
=={{header|Stata}}== |
=={{header|Stata}}== |
||
<lang stata>mata |
<lang stata>mata |
||
Line 3,473: | Line 3,476: | ||
PRINT |
PRINT |
||
RETURN</lang> |
RETURN</lang> |
||
=={{header|UnixPipes}}== |
=={{header|UnixPipes}}== |
||
<lang bash>selectionsort() { |
<lang bash>selectionsort() { |
||
Line 3,492: | Line 3,496: | ||
<45,58,69,74,82,82,88,89,104,112> |
<45,58,69,74,82,82,88,89,104,112> |
||
</pre> |
</pre> |
||
=={{header|Vala}}== |
=={{header|Vala}}== |
||
{{trans|Nim}} |
{{trans|Nim}} |