Sorting algorithms/Insertion sort: Difference between revisions
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}} |
||
⚫ | |||
<pre> |
|||
⚫ | |||
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: |
||
⚫ | |||
<pre> |
|||
⚫ | |||
⚫ | |||
⚫ | |||
</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> |
||
⚫ | |||
=={{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}}== |
||
< |
<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> |
|||
⚫ | |||
</lang> |
|||
Example of use: |
Example of use: |
||
<lang J> isort 32 4 1 34 95 3 2 120 _38 |
|||
<lang J> |
|||
_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 PL/I> |
|||
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; |
|||
J |
DO WHILE (J > 0 & A(J) > V); |
||
A(J+1)=A(J); J-=1; |
|||
END; |
|||
A(J+1)=V; |
|||
END; |
|||
RETURN; |
|||
⚫ | |||
RETURN; |
|||
⚫ | |||
</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}}== |
||
⚫ | |||
<pre> |
|||
⚫ | |||
read a |
read a |
||
test -n "$a" && ( selectionsort | sort -nm <(echo $a) -) |
test -n "$a" && ( selectionsort | sort -nm <(echo $a) -) |
||
⚫ | |||
} |
|||
⚫ | |||
</pre> |
|||
<pre> |
|||
⚫ | |||
</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> |
Revision as of 18:49, 20 November 2009
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
An O(n2) 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(n2) 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 logn) algorithms such as mergesort and quicksort.
The algorithm is as follows (from the wikipedia):
function insertionSort(array A) for i from 1 to length[A]-1 do value := A[i] j := i-1 while j >= 0 and A[j] > value do A[j+1] := A[j] j := j-1 done A[j+1] = value done
Writing the algorithm for integers will suffice.
Ada
<lang ada>type Data_Array is array(Natural range <>) of Integer;
procedure Insertion_Sort(Item : in out Data_Array) is
First : Natural := Item'First; Last : Natural := Item'Last; J : Integer; Value : Integer;
begin
for I in (First + 1)..Last loop Value := Item(I); J := I - 1; while J in Item'range and then Item(J) > Value loop Item(J + 1) := Item(J); J := J - 1; end loop; Item(J + 1) := Value; end loop;
end Insertion_Sort;</lang>
ALGOL 68
<lang algol68>MODE DATA = REF CHAR;
PROC in place insertion sort = (REF[]DATA item)VOID: BEGIN
INT first := LWB item; INT last := UPB item; INT j; DATA value; FOR i FROM first + 1 TO last DO value := item[i]; j := i - 1; # WHILE j >= LWB item AND j <= UPB item ANDF item[j] > value DO // example of ANDF extension # WHILE ( j >= LWB item AND j <= UPB item | item[j]>value | FALSE ) DO # no extension! # item[j + 1] := item[j]; j -:= 1 OD; item[j + 1] := value OD
END # in place insertion sort #;
[32]CHAR data := "big fjords vex quick waltz nymph"; [UPB data]DATA ref data; FOR i TO UPB data DO ref data[i] := data[i] OD; in place insertion sort(ref data); FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line); print((data))</lang> Output: <lang algol68>abcdefghiijklmnopqrstuvwxyz big fjords vex quick waltz nymph</lang>
AutoHotkey
contributed by Laszlo on the ahk forum <lang AutoHotkey>MsgBox % InsertionSort("") MsgBox % InsertionSort("xxx") MsgBox % InsertionSort("3,2,1") MsgBox % InsertionSort("dog,000000,xx,cat,pile,abcde,1,cat,zz,xx,z")
InsertionSort(var) { ; SORT COMMA SEPARATED LIST
StringSplit a, var, `, ; make array, size = a0 Loop % a0-1 { i := A_Index+1, v := a%i%, j := i-1 While j>0 and a%j%>v u := j+1, a%u% := a%j%, j-- u := j+1, a%u% := v } Loop % a0 ; construct string from sorted array sorted .= "," . a%A_Index% Return SubStr(sorted,2) ; drop leading comma
}</lang>
AWK
Sort standard input (storing lines into an array) and output to standard output <lang awk>{
line[NR] = $0
} END { # sort it with insertion sort
for(i=1; i <= NR; i++) { value = line[i] j = i - 1 while( ( j > 0) && ( line[j] > value ) ) { line[j+1] = line[j] j-- } line[j+1] = value } #print it for(i=1; i <= NR; i++) { print line[i] }
}</lang>
BASIC
This version (which is a translation of the REALbasic version immediately below) should work on any BASIC that can accept arrays as function arguments. <lang qbasic>DECLARE SUB InsertionSort (theList() AS INTEGER)
DIM n(10) AS INTEGER, L AS INTEGER, o AS STRING FOR L = 0 TO 10
n(L) = INT(RND * 32768)
NEXT InsertionSort n() FOR L = 1 TO 10
PRINT n(L); ";";
NEXT
SUB InsertionSort (theList() AS INTEGER)
DIM insertionElementIndex AS INTEGER FOR insertionElementIndex = 1 TO UBOUND(theList) DIM insertionElement AS INTEGER insertionElement = theList(insertionElementIndex) DIM j AS INTEGER j = insertionElementIndex - 1 DO WHILE (j >= 0) 'necessary for BASICs without short-circuit evaluation IF (insertionElement < theList(j)) THEN theList(j + 1) = theList(j) j = j - 1 ELSE EXIT DO END IF LOOP theList(j + 1) = insertionElement NEXT
END SUB</lang>
Sample output:
1486 ; 9488 ; 9894 ; 17479 ; 18989 ; 23119 ; 23233 ; 24927 ; 25386 ; 26689 ;
<lang vb> Sub InsertionSort(theList() as Integer)
for insertionElementIndex as Integer = 1 to UBound(theList) dim insertionElement as Integer = theList(insertionElementIndex) dim j as Integer = insertionElementIndex - 1 while (j >= 0) and (insertionElement < theList(j)) theList(j + 1) = theList(j) j = j - 1 wend theList(j + 1) = insertionElement next End Sub</lang>
C
<lang c>#include <stdio.h>
void Isort(int a[], int size) {
int i, j, temp; for(i=1; i<=size-1; i++) { temp = a[i]; j = i-1; while(j>=0 && a[j] > temp) { a[j+1] = a[j]; j -= 1; } a[j+1] = temp; }
}
int main (int argc, char *argv[]) {
int intArray[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1}; int i, n; n = sizeof(intArray)/sizeof(intArray[0]); Isort(intArray, n); for(i=0; i<=n-1; i++) printf("%d ", intArray[i]);
}</lang>
Clojure
Translated from the Haskell example: <lang lisp>(defn in-sort! [data]
(letfn [(insert ([raw x](insert [] raw x))
([sorted [y & raw] x] (if (nil? y) (conj sorted x) (if (<= x y ) (concat sorted [x,y] raw) (recur (conj sorted y) raw x )))))]
(reduce insert [] data)))
- Usage
- (in-sort! [6,8,5,9,3,2,1,4,7])
- Returns
- [1 2 3 4 5 6 7 8 9]</lang>
Common Lisp
<lang lisp>(defun span (predicate list)
(let ((tail (member-if-not predicate list))) (values (ldiff list tail) tail)))
(defun less-than (x)
(lambda (y) (< y x)))
(defun insert (list elt)
(multiple-value-bind (left right) (span (less-than elt) list) (append left (list elt) right)))
(defun insertion-sort (list)
(reduce #'insert list :initial-value nil))</lang>
D
<lang d>import std.stdio: writefln;
void insertionSort(T)(T[] A) {
for(int i = 1; i < A.length; i++) { T value = A[i]; int j = i - 1; while (j >= 0 && A[j] > value) { A[j + 1] = A[j]; j = j - 1; } A[j+1] = value; }
}
void main() {
auto a1 = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]; insertionSort(a1); writefln(a1); auto a2 = [4.0,65.0,2.0,-31.0,0.0,99.0,2.0,83.0,782.0,1.0]; insertionSort(a2); writefln(a2);
}</lang>
E
A direct conversion of the pseudocode.
<lang e>def insertionSort(array) {
for i in 1..!(array.size()) { def value := array[i] var j := i-1 while (j >= 0 && array[j] > value) { array[j + 1] := array[j] j -= 1 } array[j+1] := value }
}</lang>
Test case:
<lang e>? def a := [71, 53, 22, 24, 83, 54, 39, 78, 65, 26, 60, 75, 67, 27, 52, 59, 93, 62, 85, 99, 88, 10, 91, 85, 13, 17, 14, 96, 55, 10, 61, 94, 27, 50, 75, 40, 47, 63, 10, 23].diverge() > insertionSort(a) > a
- value: [10, 10, 10, 13, 14, 17, 22, 23, 24, 26, 27, 27, 39, 40, 47, 50, 52, 53, 54, 55, 59, 60, 61, 62, 63, 65, 67, 71, 75, 75, 78, 83, 85, 85, 88, 91, 93, 94, 96, 99].diverge()</lang>
Erlang
<lang Erlang>-module(sort). -export([insertion/1]).
insertion(L) -> lists:foldl(fun insert/2, [], L).
insert(X,[]) -> [X]; insert(X,L=[H|_]) when X =< H -> [X|L]; insert(X,[H|T]) -> [H|insert(X, T)].</lang>
And the calls: <lang erlang>1> c(sort). {ok,sort} 2> sort:insertion([5,3,9,4,1,6,8,2,7]). [1,2,3,4,5,6,7,8,9]</lang>
Forth
<lang forth>: insert ( start end -- start )
dup @ >r ( r: v ) \ v = a[i] begin 2dup < \ j>0 while r@ over cell- @ < \ a[j-1] > v while cell- \ j-- dup @ over cell+ ! \ a[j] = a[j-1] repeat then r> swap ! ; \ a[j] = v
- sort ( array len -- )
1 ?do dup i cells + insert loop drop ;
create test 7 , 3 , 0 , 2 , 9 , 1 , 6 , 8 , 4 , 5 , test 10 sort test 10 cells dump</lang>
Fortran
<lang fortran>SUBROUTINE Insertion_Sort(a)
REAL, INTENT(in out), DIMENSION(:) :: a REAL :: temp INTEGER :: i, j DO i = 2, SIZE(a) j = i - 1 temp = a(i) DO WHILE (j>=1 .AND. a(j)>temp) a(j+1) = a(j) j = j - 1 END DO a(j+1) = temp END DO
END SUBROUTINE Insertion_Sort</lang> In Fortran 90 and above the intrinsic function CSHIFT can be used to shift the elements in the array but in practice is slower than the above example <lang fortran>DO i = 2, SIZE(a)
j = i - 1 DO WHILE (j>=1 .AND. a(j) > a(i)) j = j - 1 END DO a(j+1:i) = cshift(a(j+1:i),-1)
END DO</lang>
Haskell
<lang haskell>import Data.List (insert)
insertionSort :: Ord a => [a] -> [a] insertionSort = foldr insert []
-- Example use: -- *Main> insertionSort [6,8,5,9,3,2,1,4,7] -- [1,2,3,4,5,6,7,8,9]</lang>
J
Solution inspired by the Common LISP solution: <lang J>isort=:((>: # ]) , [ , < #])/</lang> Example of use: <lang J> isort 32 4 1 34 95 3 2 120 _38 _38 1 2 3 4 32 34 95 120</lang>
Java
<lang java5>public static void insertSort(int[] A){
for(int i = 1; i < A.length; i++){ int value = A[i]; int j = i - 1; while(j >= 0 && A[j] > value){ A[j + 1] = A[j]; j = j - 1; } A[j + 1] = value; }
}</lang>
Modula-3
<lang modula3>MODULE InsertSort;
PROCEDURE IntSort(VAR item: ARRAY OF INTEGER) =
VAR j, value: INTEGER; BEGIN FOR i := FIRST(item) + 1 TO LAST(item) DO value := item[i]; j := i - 1; WHILE j >= FIRST(item) AND item[j] > value DO item[j + 1] := item[j]; DEC(j); END; item[j + 1] := value; END; END IntSort;
END InsertSort.</lang>
OCaml
<lang ocaml>let rec insert x = function
[] -> [x]
| y :: ys ->
if x <= y then x :: y :: ys else y :: insert x ys
let insertion_sort lst = List.fold_right insert lst [];;
insertion_sort [6;8;5;9;3;2;1;4;7];;</lang>
Perl
<lang perl>sub insertion_sort {
$arr = shift; for ($i = 0; $i <= $#{$arr}; $i++) { $j = $i - 1; $key = $arr->[$i]; while ($arr->[$j] > $key && $j >= 0) { $arr->[$j + 1] = $arr->[$j]; $j -= 1; } $arr->[$j + 1] = $key; }
} $a = [4, 65, 2, -31, 0, 99, 83, 782, 1]; insertion_sort($a); print join(' ', @{$a}), "\n";</lang> Output:
-31 0 1 2 4 65 83 99 782
PL/I
<lang pli>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>
Prolog
<lang prolog>insert_sort(L1,L2) :-
insert_sort_intern(L1,[],L2).
insert_sort_intern([],L,L). insert_sort_intern([H|T],L1,L) :-
insert(L1,H,L2), insert_sort_intern(T,L2,L).
insert([],X,[X]). insert([H|T],X,[X,H|T]) :-
X =< H, !.
insert([H|T],X,[H|T2]) :-
insert(T,X,T2).</lang> % Example use: % ?- insert_sort([2,23,42,3,10,1,34,5],L). % L = [1,2,3,5,10,23,34,42] ? % yes
Python
<lang python>def insertion_sort(l):
for i in xrange(1, len(l)): j = i-1 key = l[i] while (l[j] > key) and (j >= 0): l[j+1] = l[j] j -= 1 l[j+1] = key</lang>
Insertion sort with binary search
<lang python>def insertion_sort_bin(seq):
for i in range(1, len(seq)): key = seq[i] # invariant: ``seq[:i]`` is sorted # find the least `low' such that ``seq[low]`` is not less then `key'. # Binary search in sorted sequence ``seq[low:up]``: low, up = 0, i while up > low: middle = (low + up) // 2 if seq[middle] < key: low = middle + 1 else: up = middle # insert key at position ``low`` seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]</lang>
R
Direct translation of pseudocode. <lang r>insertionsort <- function(x) {
for(i in 2:(length(x))) { value <- x[i] j <- i - 1 while(j >= 1 && x[j] > value) { x[j+1] <- x[j] j <- j-1 } x[j+1] <- value } x
} insertionsort(c(4, 65, 2, -31, 0, 99, 83, 782, 1)) # -31 0 1 2 4 65 83 99 782</lang>
Ruby
<lang ruby>class Array
def insertionsort! 1.upto(length - 1) do |i| value = self[i] j = i - 1 while j >= 0 and self[j] > value self[j+1] = self[j] j -= 1 end self[j+1] = value end self end
end ary = [7,6,5,9,8,4,3,1,2,0] ary.insertionsort!
- => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang>
Scala
<lang scala>def insert(list: List[Int], value: Int) = list.span(_ < value) match {
case (lower, upper) => lower ::: value :: upper
} def insertSort(list: List[Int]) = list.foldLeft(List[Int]())(insert)</lang>
Scheme
<lang scheme>(define (insert x lst)
(if (null? lst) (list x) (let ((y (car lst)) (ys (cdr lst))) (if (<= x y) (cons x lst) (cons y (insert x ys))))))
(define (insertion-sort lst)
(if (null? lst) '() (insert (car lst) (insertion-sort (cdr lst)))))
(insertion-sort '(6 8 5 9 3 2 1 4 7))</lang>
Seed7
<lang seed7>const proc: insertionSort (inout array elemType: arr) is func
local var integer: i is 0; var integer: j is 0; var elemType: help is elemType.value; begin for i range 2 to length(arr) do j := i; help := arr[i]; while j > 1 and arr[pred(j)] > help do arr[j] := arr[pred(j)]; decr(j); end while; arr[j] := help; end for; end func;</lang>
Original source: [1]
Standard ML
<lang sml>fun insertion_sort cmp = let
fun insert (x, []) = [x] | insert (x, y::ys) = case cmp (x, y) of GREATER => y :: insert (x, ys) | _ => x :: y :: ys
in
foldl insert []
end;
insertion_sort Int.compare [6,8,5,9,3,2,1,4,7];</lang>
Tcl
<lang tcl>package require Tcl 8.5
proc insertionsort {m} {
for {set i 1} {$i < [llength $m]} {incr i} { set val [lindex $m $i] set j [expr {$i - 1}] while {$j >= 0 && [lindex $m $j] > $val} { lset m [expr {$j + 1}] [lindex $m $j] incr j -1 } lset m [expr {$j + 1}] $val } return $m
}
puts [insertionsort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</lang>
UnixPipes
<lang bash>selectionsort() {
read a test -n "$a" && ( selectionsort | sort -nm <(echo $a) -)
}</lang> <lang bash>cat to.sort | selectionsort</lang>
Ursala
<lang Ursala>#import nat
insort = ~&i&& @hNCtX ~&r->lx ^\~&rt nleq-~rlrSPrhlPrSCPTlrShlPNCTPQ@rhPlD</lang> test program: <lang Ursala>#cast %nL
example = insort <45,82,69,82,104,58,88,112,89,74></lang> output:
<45,58,69,74,82,82,88,89,104,112>