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):

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

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>

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>

UnixPipes

selectionsort() {
   read a
   test -n "$a" && ( selectionsort | sort -nm <(echo $a) -)
}

cat to.sort | selectionsort