Sorting algorithms/Insertion sort: Difference between revisions

← Older editNewer edit →
Content deleted Content added
m Fixed lang tags.
Line 44: Line 44:
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
⚫
<lang algol68>MODE DATA = REF CHAR;
<pre>
⚫
MODE DATA = REF CHAR;


PROC in place insertion sort = (REF[]DATA item)VOID:
PROC in place insertion sort = (REF[]DATA item)VOID:
Line 69: Line 68:
in place insertion sort(ref data);
in place insertion sort(ref data);
FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line);
FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line);
print((data))
print((data))</lang>
</pre>
Output:
Output:
⚫
<lang algol68>abcdefghiijklmnopqrstuvwxyz
<pre>
⚫
big fjords vex quick waltz nymph</lang>
⚫
abcdefghiijklmnopqrstuvwxyz
⚫
big fjords vex quick waltz nymph
</pre>
=={{header|AutoHotkey}}==
=={{header|AutoHotkey}}==
contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276481.html#276481 forum]
contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276481.html#276481 forum]
Line 201: Line 197:
=={{header|Clojure}}==
=={{header|Clojure}}==
Translated from the Haskell example:
Translated from the Haskell example:
<lang lisp>
<lang lisp>(defn in-sort! [data]
(defn in-sort! [data]
(letfn [(insert ([raw x](insert [] raw x))
(letfn [(insert ([raw x](insert [] raw x))
([sorted [y & raw] x]
([sorted [y & raw] x]
Line 210: Line 205:
(reduce insert [] data)))
(reduce insert [] data)))
;Usage:(in-sort! [6,8,5,9,3,2,1,4,7])
;Usage:(in-sort! [6,8,5,9,3,2,1,4,7])
;Returns: [1 2 3 4 5 6 7 8 9]
;Returns: [1 2 3 4 5 6 7 8 9]</lang>
⚫
</lang>


=={{header|Common Lisp}}==
=={{header|Common Lisp}}==
Line 275: Line 269:


=={{header|Erlang}}==
=={{header|Erlang}}==
<lang Erlang>
<lang Erlang>-module(sort).
-module(sort).
-export([insertion/1]).
-export([insertion/1]).


Line 283: Line 276:
insert(X,[]) -> [X];
insert(X,[]) -> [X];
insert(X,L=[H|_]) when X =< H -> [X|L];
insert(X,L=[H|_]) when X =< H -> [X|L];
insert(X,[H|T]) -> [H|insert(X, T)].
insert(X,[H|T]) -> [H|insert(X, T)].</lang>
</lang>


And the calls:
And the calls:
<lang erlang>
<lang erlang>1> c(sort).
1> c(sort).
{ok,sort}
{ok,sort}
2> sort:insertion([5,3,9,4,1,6,8,2,7]).
2> sort:insertion([5,3,9,4,1,6,8,2,7]).
[1,2,3,4,5,6,7,8,9]
[1,2,3,4,5,6,7,8,9]</lang>
</lang>


=={{header|Forth}}==
=={{header|Forth}}==
<pre>: insert ( start end -- start )
<lang forth>: insert ( start end -- start )
dup @ >r ( r: v ) \ v = a[i]
dup @ >r ( r: v ) \ v = a[i]
begin
begin
Line 312: Line 302:
create test 7 , 3 , 0 , 2 , 9 , 1 , 6 , 8 , 4 , 5 ,
create test 7 , 3 , 0 , 2 , 9 , 1 , 6 , 8 , 4 , 5 ,
test 10 sort
test 10 sort
test 10 cells dump
test 10 cells dump</lang>
</pre>


=={{header|Fortran}}==
=={{header|Fortran}}==
Line 352: Line 341:
=={{header|J}}==
=={{header|J}}==
Solution inspired by the Common LISP solution:
Solution inspired by the Common LISP solution:
⚫
<lang J>isort=:((>: # ]) , [ , < #])/</lang>
<lang J>
⚫
isort=:((>: # ]) , [ , < #])/
</lang>
Example of use:
Example of use:
<lang J> isort 32 4 1 34 95 3 2 120 _38
<lang J>
isort 32 4 1 34 95 3 2 120 _38
_38 1 2 3 4 32 34 95 120</lang>
_38 1 2 3 4 32 34 95 120
</lang>


=={{header|Java}}==
=={{header|Java}}==
Line 424: Line 409:


=={{header|PL/I}}==
=={{header|PL/I}}==
⚫
<lang pli>INSSORT: PROCEDURE (A,N);
<lang PL/I>
DCL (A(*)) FIXED BIN(31),
⚫
INSSORT: PROCEDURE (A,N);
DCL (A(*)) FIXED BIN(31),
N FIXED BIN(31) NONASGN;
N FIXED BIN(31) NONASGN;
DCL (I,J,V) FIXED BIN(31);
DCL (I,J,V) FIXED BIN(31);
DO I=2 TO N;
DO I=2 TO N;
V=A(I);
V=A(I);
J=I-1;
J=I-1;
DO WHILE (J > 0 & A(J) > V);
DO WHILE (J > 0 & A(J) > V);
A(J+1)=A(J); J-=1;
A(J+1)=A(J); J-=1;
END;
END;
A(J+1)=V;
A(J+1)=V;
END;
END;
RETURN;
⚫
END INSSORT;</lang>
RETURN;
⚫
END INSSORT;
</lang>


=={{header|Prolog}}==
=={{header|Prolog}}==
Line 490: Line 473:
=={{header|R}}==
=={{header|R}}==
Direct translation of pseudocode.
Direct translation of pseudocode.
<lang r>
<lang r>insertionsort <- function(x)
insertionsort <- function(x)
{
{
for(i in 2:(length(x)))
for(i in 2:(length(x)))
Line 506: Line 488:
x
x
}
}
insertionsort(c(4, 65, 2, -31, 0, 99, 83, 782, 1)) # -31 0 1 2 4 65 83 99 782
insertionsort(c(4, 65, 2, -31, 0, 99, 83, 782, 1)) # -31 0 1 2 4 65 83 99 782</lang>
</lang>


=={{header|Ruby}}==
=={{header|Ruby}}==
Line 568: Line 549:
arr[j] := help;
arr[j] := help;
end for;
end for;
end func;
end func;</lang>
</lang>


Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#insertionSort]
Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#insertionSort]
Line 604: Line 584:


=={{header|UnixPipes}}==
=={{header|UnixPipes}}==
⚫
<lang bash>selectionsort() {
<pre>
⚫
selectionsort() {
read a
read a
test -n "$a" && ( selectionsort | sort -nm <(echo $a) -)
test -n "$a" && ( selectionsort | sort -nm <(echo $a) -)
⚫
}</lang>
}
⚫
<lang bash>cat to.sort | selectionsort</lang>
</pre>
<pre>
⚫
cat to.sort | selectionsort
</pre>


=={{header|Ursala}}==
=={{header|Ursala}}==
<lang Ursala>
<lang Ursala>#import nat
#import nat


insort = ~&i&& @hNCtX ~&r->lx ^\~&rt nleq-~rlrSPrhlPrSCPTlrShlPNCTPQ@rhPlD
insort = ~&i&& @hNCtX ~&r->lx ^\~&rt nleq-~rlrSPrhlPrSCPTlrShlPNCTPQ@rhPlD</lang>
</lang>
test program:
test program:
<lang Ursala>
<lang Ursala>#cast %nL
#cast %nL


example = insort <45,82,69,82,104,58,88,112,89,74>
example = insort <45,82,69,82,104,58,88,112,89,74></lang>
</lang>
output:
output:
<pre>
<pre>
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort"