Last modified on 20 July 2014, at 00:40

Algorithm Implementation/Sorting/Insertion sort

AdaEdit

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;

AutoIt3Edit

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++Edit

void insertSort(int a[], int length)
{
    int i, j, value;
 
    for(i = 1; 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;
    }
}
template< typename Iterator >
void insertion_sort( Iterator First, Iterator Last )
{
    Iterator min = First;
    for( Iterator i = First + 1; i < Last; ++i )
        if ( *i < *min )
            min = i;
 
    std::iter_swap( First, min );
    while( ++First < Last )
        for( Iterator j = First; *j < *(j - 1); --j )
            std::iter_swap( (j - 1), j );
}
void SortInsert::insertSort(vector<int>::iterator begin, vector<int>::iterator end)
{
    for (vector<int>::iterator i = begin + 1; i < end; ++i)
    {
        for(vector<int>::iterator j = i; *j < *(j - 1) && j > begin; --j )
        {
            std::iter_swap((j - 1), j);
        }
    }
}

This is 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#Edit

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.0Edit

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;
    }
}

CAMLEdit

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 LispEdit

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

F#Edit

 let rec insert x l =  match l with 
   | []    -> [x]
   | y::ys -> if x <= y then x::y::ys
              else y::insert x ys
 and insertsort l = match l with 
   | []    -> []
   | x::xs -> insert x (insertsort xs)

JavaEdit

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;
    }
}

JavaScriptEdit

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

HaskellEdit

import Data.List (insert)
 
insertsort :: Ord a => [a] -> [a]
insertsort  =  foldr insert []

OCamlEdit

In listsEdit

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 versionEdit

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 []

PascalEdit

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;

PerlEdit

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;
    }
}

PHPEdit

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;
}

PythonEdit

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 = insert_index - 1
        array[insert_index] = removed_value

Standard MLEdit

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 versionEdit

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 []

RubyEdit

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

NASMEdit

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

VBEdit

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

Fortran 90/95Edit

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