Algorithm Implementation/Sorting/Insertion sort

Ada

Sorts an array of integers.

type Integer_Array is array (Natural range <>) of Integer;

procedure Insertion_Sort (A : in out Integer_Array) is
   Value : Integer;
   J : Natural;
begin
   for I in A'First + 1 .. A'Last loop
      Value := A(I);
      J := I - 1;
      while J >= A'First and then A(J) > Value loop
         A(J + 1) := A(J);
         J := J - 1;
      end loop;
      A(J + 1) := Value;
   end loop;   
end Insertion_Sort;

AutoIt3

Func insertionSort( ByRef $array )
    For $i = 1 to Ubound( $array ) - 1
        $j = $i - 1
        $temp = $array[$i]
        While ( $j >= 0 ) And ( $array[$j] > $temp )
            $array[$j+1] = $array[$j]
            $j -= 1
        WEnd
        $array[$j+1] = $temp
    Next
EndFunc

C/C++

In C:

#include <iostream>
using namespace std;

void insertSort(int a[], int length)
{
    int i, j, value;

    for(i = 0 ; i < length ; i++)
    {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; j--)
            a[j + 1] = a[j];
        a[j+1] = value;
    }
}

In C++:

#include <iostream>
using namespace std;

template<class Iterator>
void insertion_sort( Iterator a, Iterator end )
{
    std::iter_swap( a, std::min_element( a, end ) );
 
    for ( Iterator b = a; ++b < end; a = b )
        for( Iterator c = b; *c < *a; --c, --a )
            std::iter_swap( a, c );
}

In C++, half insertion sort:

void halfInsertSort(int array[], int length)
{
    int begin;
    int end;
    int middle;
    int value;
    
    for (int i = 1; i < length; ++i)
    {
        value = array[i];           
        begin = 0;                  
        end = i - 1;                
        while (begin <= end)        
        {
            middle = (begin + end) / 2;   
            if (value < array[middle])
            {
                end = middle - 1;   
            }      
            else                          
            {
                begin = middle + 1;       
            }
        }
        
        for (int j = i - 1; j >= begin; --j) 
        {
            array[j + 1] = array[j];         
        }
            
        array[begin] = value;                
    }
}

C#

static void InsertSort(IComparable[] array)
{
    int i, j;

    for (i = 1; i < array.Length; i++)
    {
        IComparable value = array[i];
        j = i - 1;
        while ((j >= 0) && (array[j].CompareTo(value) > 0))
        {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = value;
    }
}

C# 2.0

This example sorts a list of objects of any type T that implements IComparable. It demonstrates C# 2.0 generics and in particular the "where" clause.

static void InsertSort<T>(IList<T> list) where T : IComparable<T>
{
    int i, j;

    for (i = 1; i < list.Count; i++)
    {
        T value = list[i];
        j = i - 1;
        while ((j >= 0) && (list[j].CompareTo(value) > 0))
        {
            list[j + 1] = list[j];
            j--;
        }
        list[j + 1] = value;
    }
}

CAML

let rec insertion_sort l =
  match l with
   | [] -> []
   | (h::n) -> insert h (insertion_sort n)
and insert t l =
  match l with
   | [] -> [t]
   | (h::n) -> if t > h then h::(insert t n)
                        else t::h::n ;;

Common Lisp

(defun insert (target list)
  (if (null list)
    (cons target nil)
    (if (<= target (first list))
      (cons target list)
      (cons (first list) (insert target (rest list))))))

(defun insertSort (myList)
  (if (null myList)
    nil
    (insert (first myList) (insertSort (rest myList)))))

Fortran 90/95

This implementation of Insertion sort follows closely the implementation that can be found in the GPL FORTRAN 90/95 GPL library AFNL.

! ***********************************
! *
  Subroutine Insrt(X, Ipt)
! *
! ***********************************
! * Sort Array X(:) in ascendent order.
! * If present Ipt, a pointer with the 
! * changes is returned in Ipt. 
! ***********************************

    Real (kind=4), Intent (inout) :: X(:)
    Integer, Intent (out), Optional :: Ipt(:)
    
    Real (kind=4) :: Rtmp
    Integer :: I, J

    If (Present(Ipt)) Then
       Forall (I=1:Size(X)) Ipt(I) = I
       
       Do I = 2, Size(X)
          Rtmp = X(I)
          Do J = I-1, 1, -1
             If (Rtmp < X(J)) Then
                X(J+1) = X(J)
                CALL Swap(Ipt, J, J+1)
             Else
                Exit
             End If
          End Do
          X(J+1) = Rtmp
       End Do
    Else
       Do I = 2, Size(X)
          Rtmp = X(I)
          Do J = I-1, 1, -1
             If (Rtmp < X(J)) Then
                X(J+1) = X(J)
             Else
                Exit
             End If
          End Do
          X(J+1) = Rtmp
       End Do
    End If

    Return
  End Subroutine Insrt

! ***********************************
! *
  Subroutine Swap(X, I, J)
! *
! ***********************************
! * Swaps elements I and J of array X(:). 
! ***********************************

    Integer, Intent (inout) :: X(:)
    Integer, Intent (in) :: I, J

    Integer :: Itmp

    Itmp = X(I)
    X(I) = X(J)
    X(J) = Itmp

    Return
  End Subroutine Swap

F#

let insertionSort l = 
    let rec insert x sortedList =
        match sortedList with
        | smallest :: sortedTail when smallest < x -> smallest :: insert x sortedTail
        | _ -> x :: sortedList
    List.foldBack insert l []

Go

func InsertionSort(data []int) {
    for i, v := range data {
        j := i
        for ;j > 0 && v < data[j - 1]; j-- {
            data[j] = data[j - 1]
        }
        data[j] = v
    }
}

Java

public static void insertionsort(int[] numbers) {
    for (int i = 0; i < numbers.length; i++) {
        int copyNumber = numbers[i];
        int j = i;
        while (j > 0 && copyNumber < numbers[j-1]) {
            numbers[j] = numbers[j-1];
            j--;
        }
        numbers[j] = copyNumber;
    }
}

another general implements.

public static < E extends Comparable<? super E> > void insertSort( E[] comparable )
{
	for ( int i = 1; i < comparable.length; i++ )
	{
		E	value	= comparable[i];
		int	j	= i - 1;
		while ( j >= 0 && comparable[j].compareTo( value ) > 0 )
		{
			comparable[j + 1] = comparable[j--];
		}
		comparable[j + 1] = value;
	}
}

JavaScript

// Assumes all elements are non-null and non-undefined
function insertionSort(sortMe) {
   for (var i = 0, j; i < sortMe.length; ++i) {
      var tmp = sortMe[i];
      for (var j = i - 1; j >= 0 && sortMe[j] > tmp; --j)
         sortMe[j + 1] = sortMe[j];
      sortMe[j + 1] = tmp;
   }
}

Haskell

import Data.List (insert)

insertsort :: Ord a => [a] -> [a]
insertsort  =  foldr insert []

OCaml

In lists

let rec insert e = function
  h::t when e <= h -> h :: insert e t
| l                -> e :: l

let rec insertion_sort = function
  []   -> []
| h::t -> insert h (insertion_sort t)

shorter version

The insert function is the same as above.

let rec insert e = function
  h::t when e <= h -> h :: insert e t
| l                -> 
let insertion_sort xs = List.fold_right insert xs []

Pascal

Procedure InsertionSort(var ArrayOfOrd: AnyOrdType);
var 
  Top, InsertionPos: integer;
  Cache :string;

Begin
  for Top := 1 to length(ArrayOfOrd) - 1 do
  begin
    Cache := ArrayOfOrd[Top];
    InsertionPos := Top;
    while (ArrayOfOrd[InsertionPos - 1] > Cache) and (InsertionPos > 0) do
    begin
      ArrayOfOrd[InsertionPos] := ArrayOfOrd[InsertionPos - 1];
      dec(InsertionPos);
    end;
    ArrayOfOrd[InsertionPos] := Cache;
  end;
End;

Linked list version

procedure insertionSort(var L:PNode);
var h, x, xs, y, z:PNode;
begin
  h := NIL;
  x := L;
  while x <> NIL do
  begin
    xs := x^.next;
    y := h;
    z :=NIL;
    while (y <> NIL)and(x^.key > y^.key)do
    begin
      z := y;
      y := y^.next;
    end;
    x^.next := y;
    if z <> NIL then
      z^.next := x
    else
      h := x;
    x := xs;
  end;
  L := h;
end;

Perl

sub insert_sort {
    for(my $i = 1; $i <= $#_; $i++) {
        my ($j, $val) = ($i - 1, $_[$i]);
        $_[$j-- + 1] = $_[$j] while ($j >= 0 && $_[$j] > $val);
        $_[$j+1] = $val;
    }
}

Phix

function insertion_sort(sequence s)
object temp
integer j
    for i=2 to length(s) do
        temp = s[i]
        j = i-1
        while j>=1 and s[j]>temp do
            s[j+1] = s[j]
            j -= 1
        end while
        s[j+1] = temp
    end for
    return s
end function

PHP

for ($j=1; $j < count($array); $j++) {
    $temp = $array[$j];
    $i = $j;
    while (($i >= 1) && ($array[$i-1] > $temp)) {
       $array[$i] = $array[$i-1];
       $i--;
    }
    $array[$i] = $temp;
}

Python

def insertsort(array):
    for removed_index in range(1, len(array)):
        removed_value = array[removed_index]
        insert_index = removed_index
        while insert_index > 0 and array[insert_index - 1] > removed_value:
            array[insert_index] = array[insert_index - 1]
            insert_index -= 1
        array[insert_index] = removed_value

Standard ML

fun insertsort [] = []
  | insertsort (x::xs) =
    let fun insert (x:real, []) = [x]
          | insert (x:real, y::ys) =
              if x<=y then x::y::ys
              else y::insert(x, ys)
    in insert(x, insertsort xs)
    end;

shorter version

The insert function is the same as above.

fun insert (x:real, []) = [x]
  | insert (x, y::ys) =
      if x <= y then x::y::ys
                else y::insert(x, ys)

val insertion_sort = foldr insert []

Ruby

It sorts the original array.

def insert_sort!(list)
    for i in 1..(list.length - 1)
        value = list[i]
        j = i - 1
        while j >= 0 and list[j] > value
            list[j + 1] = list[j] 
            j -= 1
        end
        list[j + 1] = value
    end
end

Swift

In Swift:

func insertionSort<T: Comparable> (list: inout [T]) {
    for i in 1..<list.count {
        var j = i - 1
        let x = list[i]
        while 0 <= j && x < list[j] {
            swap(&list[j+1], &list[j])
            j -= 1
        }
        list[j+1] = x
    }
}

NASM

C prototype is

void isort(int *a, int n)

Assembler routine is

isort:
 %define a [ebp + 8]
 %define n [ebp + 12]
 enter 0, 0
 pusha
 mov ecx, 1
 for:
   mov ebx, ecx
   imul ebx, 4
   add ebx, a
   mov ebx, [ebx]
   mov edx, ecx
   dec edx
   while:
     cmp edx, 0
     jl while_quit
     mov eax, edx
     imul eax, 4
     add eax, a
     cmp ebx, [eax]
     jge while_quit
     mov esi, [eax]
     mov dword [eax + 4], esi
     dec edx
     jmp while
   while_quit:
   mov [eax], ebx
   inc ecx
   cmp ecx, n
   jl for
 popa
 leave
 ret

VB

Public Sub InsertionSort(ByRef ArrayAngka() As Long)
Dim i, j    As Integer
Dim t       As Long
For i = 0 To (n - 1) 
   For j = i + 1 To 1 Step -1 
       If ArrayAngka(j) < ArrayAngka(j - 1) Then
           Call tukar(ArrayAngka(j), ArrayAngka(j - 1))
       End If
   Next j
Next i
End Sub
Private Sub tukar(data1 As Long, data2 As Long)
   Dim temp As Long
   temp = data1
   data1 = data2
   data2 = temp
End Sub

And here's something a little bit quicker.

Public Sub Insertionsort(nums() As Long)
Dim i&, j&, k&, length&
length = UBound(nums)
For i = 1 To length
  j = nums(i)
  k = i
  Do While (k > 0) And (nums(k - 1) > j)
    nums(k) = nums(k - 1)
    k = k - 1
  Loop
  nums(k) = j
Next i
End Sub