Sorting algorithms/Insertion 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):

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.

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

<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

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

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).
 
 % 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>

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