Algorithm Implementation/Sorting/Insertion sort

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search
Wikipedia-logo.png

Wikipedia has related information at
Insertion sort


Contents

[edit] 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 A(J) > Value loop
         A(J + 1) := A(J);
         J := J - 1;
      end loop;
      A(J + 1) := Value;
   end loop;   
end Insertion_Sort;

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

[edit] C/C++

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

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 )
            std::iter_swap((j - 1), j);
}

C++ programmers may use the versions above, or better yet std::__insertion_sort available after including the header file: <algorithm>

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

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

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

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

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

[edit] F#

 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)

[edit] Java

public static int[] 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;
    }
    return numbers;
}

[edit] JavaScript

function insertionSort(sortMe) {
   for (i=0; 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;
   }
}

[edit] Haskell

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

[edit] OCaml

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

[edit] 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                -> 
rabi gandoooooooooolet insertion_sort xs = List.fold_right insert xs []

[edit] Pascal

PROCEDURE InsertionSort(var Menge: MengeIntegerTyp; Links, Rechts: INTEGER;)
VAR
 Index, Einfuegeposition, Zwischenspeicher: INTEGER;
BEGIN
  FOR Index := Links + 1 TO Rechts DO
  BEGIN
    Zwischenspeicher := Menge[Index];
    Einfuegeposition := Index;
    WHILE ((Menge[Einfugeposition - 1] > Zwischenspeicher) AND
           (Einfuegeposition > Links)) DO
    BEGIN
      Menge[Einfuegeposition] := Menge[Einfuegeposition - 1];
      Einfuegeposition := Einfuegeposition - 1;
    END;
    Menge[Einfuegeposition] := Zwischenspeicher;
  END;
END;

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

[edit] PHP

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

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

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

[edit] shorter version

The insert function is the same as above.


GeSHi Error: GeSHi could not find the language sml (using path /usr/local/apache/common-local/wmf-deployment/lib/GeSHi-1.0.8.4/geshi/) (code 2)

You need to specify a language like this: <source lang="html4strict">...</source>

Supported languages for syntax highlighting:

abap, actionscript, actionscript3, ada, apache, applescript, apt_sources, asm, asp, autoit, avisynth, bash, basic4gl, bf, bibtex, blitzbasic, bnf, boo, c, c_mac, caddcl, cadlisp, cfdg, cfm, cil, cmake, cobol, cpp, cpp-qt, csharp, css, d, dcs, delphi, diff, div, dos, dot, eiffel, email, erlang, fo, fortran, freebasic, genero, gettext, glsl, gml, gnuplot, groovy, haskell, hq9plus, html4strict, idl, ini, inno, intercal, io, java, java5, javascript, kixtart, klonec, klonecpp, latex, lisp, locobasic, lolcode, lotusformulas, lotusscript, lscript, lsl2, lua, m68k, make, matlab, mirc, modula3, mpasm, mxml, mysql, nsis, oberon2, objc, ocaml, ocaml-brief, oobas, oracle11, oracle8, pascal, per, perl, php, php-brief, pic16, pixelbender, plsql, povray, powershell, progress, prolog, properties, providex, python, qbasic, rails, rebol, reg, robots, ruby, sas, scala, scheme, scilab, sdlbasic, smalltalk, smarty, sql, tcl, teraterm, text, thinbasic, tsql, typoscript, vb, vbnet, verilog, vhdl, vim, visualfoxpro, visualprolog, whitespace, whois, winbatch, xml, xorg_conf, xpp, z80

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

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

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

[edit] 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
Retrieved from "http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Insertion_sort"
In other languages