Algorithm Implementation/Sorting/Insertion sort

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

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

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

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
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 []
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
    }
}
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;
	}
}
// 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;
   }
}
import Data.List (insert)

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

In lists

edit
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

edit

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

edit

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

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

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

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