Sorting algorithms/Insertion sort

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:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) 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(n²) 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 = 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
        A[j+1] = value

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

Translation of: Ada

Works with: ALGOL 68 version Standard - no extensions to language used

Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386

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

1. 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

Translation of: Ada

<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!

1. => [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