Sorting algorithms/Insertion sort: Difference between revisions

Content added Content deleted

Inline

Revision as of 04:51, 4 February 2010

An O(n²) 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(n²) 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

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

<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

Works with: QBasic

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); ";";

   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 ;

Works with: REALbasic

<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

Some lines in this example are too long (more than 80 characters). Please fix the code if it's possible and remove this message.

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>

Lua

<lang lua>function bins(tb, val, st, en)

 local st, en = st or 1, en or #tb
 local mid = math.floor((st + en)/2)
 if en == st then return tb[st] > val and st or st+1
 else return tb[mid] > val and bins(tb, val, st, mid) or bins(tb, val, mid+1, en)
 end

end function isort(t)

 local ret = {t[1], t[2]}
 for i = 3, #t do
   table.insert(ret, bins(ret, t[i]), t[i])
 end
 return ret

end

print(unpack(isort{4,5,2,7,8,3}))</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>

Oz

Direct translation of pseudocode. In-place sorting of mutable arrays. <lang oz>declare

 proc {InsertionSort A}
    Low = {Array.low A}
    High = {Array.high A}
 in
    for I in Low+1..High do
       Value = A.I
       J = {NewCell I-1}
    in
       for while:@J >= Low andthen A.@J > Value do
          A.(@J+1) := A.@J
          J := @J - 1
       end
       A.(@J+1) := Value
    end
 end

 Arr = {Tuple.toArray unit(3 1 4 1 5 9 2 6 5)}

in

 {InsertionSort Arr}
 {Show {Array.toRecord unit Arr}}</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>

TI-83 BASIC

Store input in L₁, run prgmSORTINS, get output in L₂.

:L₁→L₂
:0→A
:Lbl L
:A+1→A
:A→B
:While B>0
:If L₂(B)<L₂(B+1)
:Goto B
:L₂(B)→C
:L₂(B+1)→L₂(B)
:C→L₂(B+1)
:B-1→B
:End
:Lbl B
:If A<(dim(L₂)-1)
:Goto L
:DelVar A
:DelVar B
:DelVar C
:Stop

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>

TI-83 BASIC

Input into L₁, run prgmSORTINS, output in L₂.

:"INSERTION"
:L₁→L₂
:0→A
:Lbl L
:A+1→A
:A→B
:While B>0
:If L₂(B)≤L₂(B+1)
:Goto B
:L₂(B)→C
:L₂(B+1)→L₂(B)
:C→L₂(B+1)
:B-1→B
:End
:Lbl B
:If A<(dim(L₂)-1)
:Goto L
:DelVar A
:DelVar B
:DelVar C
:Return

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>