Sorting algorithms/Insertion sort
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 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
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))
Output:
abcdefghiijklmnopqrstuvwxyz big fjords vex quick waltz nymph
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>
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>
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>
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
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>insert x [] = [x] insert x (y:ys) | x <= y = x:y:ys insert x (y:ys) | otherwise = y:(insert x ys)
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>
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
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>
REALbasic
<lang realbasic> 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>
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>
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>
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
selectionsort() { read a test -n "$a" && ( selectionsort | sort -nm <(echo $a) -) }
cat to.sort | selectionsort