Difference between revisions of "Insertion sort"

From CodeCodex

(Python)
(C)
 
(41 intermediate revisions by 20 users not shown)
Line 3: Line 3:
  
 
==Implementations==
 
==Implementations==
===C++===
 
 
#include <vector>
 
using namespace std;
 
 
template<typename T>
 
 
void sortieren(void)
 
{
 
  int k = 0;
 
  T x ;
 
  for(unsigned int j = 0; j < m_array.size(); j++){
 
        x = m_array.at(j);
 
        k = j;
 
 
          while(k > 0 && x > m_array.at(k-1)){
 
 
          m_array.erase(m_array.begin() +k);
 
          m_array.insert(m_array.begin()+k,m_array.at(k-1));
 
          k --;
 
          }
 
        m_array.erase(m_array.begin() +k);
 
        m_array.insert(m_array.begin()+k,x);
 
    }
 
}
 
 
 
===C===
 
===C===
 +
<pre class="c++">
 +
void insertSort(int a[], size_t length) {
 +
    int i, j, value;
  
  '''void''' <u>insertSort</u>('''int''' a[], '''size_t''' length) {
+
    for(i = 1; i < length; i++) {
      '''int''' i, j, value;
+
        value = a[i];
    
+
        for (j = i - 1; j >= 0 && a[j] > value; j--) {
      '''for'''(i = 1; i < length; i++) {
+
            a[j + 1] = a[j];
          value = a[i];
+
        }
          '''for''' (j = i - 1; j >= 0 && a[j] > value; j--) {
+
        a[j+1] = value;
              a[j + 1] = a[j];
+
    }
          }
+
}
          a[j+1] = value;
+
</pre>
      }
+
 
  }
+
 
 +
If you're trying to sort arbitrary data structures, the following modification of the above code may help.  It will sort a list of void pointers (pointers to your structures) based on some external comparison function.
 +
 
 +
<pre class="c">
 +
 
 +
void sort(uint8_t (* cmp)(void *, void *), void *a[], size_t length) {
 +
    size_t i, j;
 +
    void   *cut;
 +
 
 +
    for (i = 1; i < length; i++) {
 +
        cut = a[i]; // snip out pointer
 +
 
 +
        for (j = i; j && cmp(a[j - 1], cut); j--) {
 +
            a[j] = a[j - 1]; // sift down
 +
        }
 +
 
 +
        a[j] = cut; // insert snipped pointer
 +
    }
 +
}
 +
 
 +
 
 +
// example comparison function
 +
 
 +
uint8_t compare_ints(void *x, void *y) {
 +
    // assume x and y point to integers for simplicity...
 +
    // want to return x > y
 +
 
 +
    return (*((int *) x) > *((int *) y));
 +
}
 +
 
 +
 
 +
// call: sort(compare_ints, array_of_void_pointers_to_ints, array_length);
 +
 
 +
</pre>
 +
 
 +
===C++===
 +
<pre class="cpp">
 +
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 );
 +
}
 +
</pre>
  
 
===C#===
 
===C#===
 +
<pre class="csharp">
 +
static void InsertSort(IComparable[] array)
 +
{
 +
    int i, j;
  
'''static void''' <u>InsertSort</u>('''IComparable[]''' array)
+
    for (i = 1; i < array.Length; i++)
{
+
    {
    '''int''' i, j;
+
        IComparable value = array[i];
+
        j = i - 1;
    '''for''' (i = 1; i < array.Length; i++)
+
        while ((j >= 0) && (array[j].CompareTo(value) > 0))
    {
+
        {
        '''IComparable''' value = array[i];
+
            array[j + 1] = array[j];
        j = i - 1;
+
            j=j-1;
        '''while''' ((j >= 0) && (array[j].CompareTo(value) > 0))
+
        }
        {
+
        array[j + 1] = value;
            array[j + 1] = array[j];
+
    }
            j--;
+
}
        }
+
</pre>
        array[j + 1] = value;
+
    }
+
}
+
  
 
===C# 2.0===
 
===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.
 
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''' <u>InsertSort</u>&lt;T&gt;('''IList&lt;'''T'''&gt;''' list) '''where''' T : '''IComparable&lt;'''T'''&gt;'''
+
<pre class="csharp">
{
+
static void InsertSort<T>(IList<T> list) where T : IComparable<T>
    '''int''' i, j;
+
{
+
    int i, j;
    '''for''' (i = 1; i &lt; list.Count; i++)
+
    {
+
        T value = list[i];
+
        j = i - 1;
+
        '''while''' ((j &gt;= 0) && (list[j].CompareTo(value) &gt; 0))
+
        {
+
            list[j + 1] = list[j];
+
            j--;
+
        }
+
        list[j + 1] = value;
+
    }
+
}
+
  
 +
    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;
 +
    }
 +
}
 +
</pre>
  
 +
===Common Lisp===
  
 +
<pre>
 +
(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))</pre>
  
===Pascal===
+
===Erlang===
 +
<pre>
 +
insert_sort(L) when is_list(L) ->
 +
    insert_sort(L, []).
  
PROCEDURE InsertionSort(var Menge: MengeIntegerTyp; Links, Rechts: INTEGER;)
+
insert_sort([], Sorted) -> Sorted;
VAR
+
insert_sort([H | T], Sorted) ->
  Index, Einfuegeposition, Zwischenspeicher: INTEGER;
+
    insert_sort(T, insert(H, Sorted)).
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;
+
  
 +
insert(X, []) -> [X];
 +
insert(X, Sorted) when X =< hd(Sorted) -> [X | Sorted];
 +
insert(X, [H | T]) -> [H | insert(X, T)].
 +
</pre>
  
 +
===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)
 +
 +
===Haskell===
 +
<pre class="haskell">
 +
import Data.List (insert)
 +
 +
insertsort :: Ord a => [a] -> [a]
 +
insertsort  =  foldr insert []
 +
</pre>
 +
 +
===Java===
 +
<pre class="java">
 +
static void insertionSort (int[] A) {
 +
    for (int i = 1; i < A.length; i++) {
 +
      int a = A[i];
 +
      int j;
 +
      for (j = i - 1; j >=0 && A[j] > a; j--){
 +
        A[j + 1] = A[j];
 +
      }
 +
      A[j + 1] = a;
 +
    }
 +
}
 +
</pre>
 +
 +
====Generic====
 +
<pre class="java">
 +
static <T extends Comparable<? super T>> void insertionSort (T[] A) {
 +
    for (int i = 1; i < A.length; i++) {
 +
      T a = A[i];
 +
      int j;
 +
      for (j = i - 1; j >=0 && A[j].compareTo(a) > 0; j--)
 +
        A[j + 1] = A[j];
 +
      A[j + 1] = a;
 +
    }
 +
}
 +
</pre>
  
 
===OCaml===
 
===OCaml===
Line 124: Line 200:
 
  - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
 
  - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
  
===CAML===
+
another
  
 
  let rec insertion_Sort l =
 
  let rec insertion_Sort l =
Line 136: Line 212:
 
                         else t::h::n ;;
 
                         else t::h::n ;;
  
===Common Lisp===
+
===Pascal===
 +
<pre class="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;
 +
</pre>
  
('''defun''' insert (target list)
+
===Perl===
    ('''if''' ('''null''' list)
+
1:
        ('''cons''' target '())
+
<pre class="perl">
        ('''if''' ('''<=''' target ('''first''' list))
+
sub insertionSort {
            ('''cons''' target list)
+
     my @unsorted = @{$_[0]};
            ('''cons''' ('''first''' list) (insert target ('''rest''' list))))))
+
    my @sorted  = @{$_[1]};
+
('''defun''' <u>insertSort</u> (myList)
+
     ('''if''' ('''null''' mylist)
+
        '()
+
        (insert ('''first''' myList) (insertSort ('''rest''' myList)))))
+
  
===F#===
+
    INSERTION:
 +
    for my $current ( @unsorted ) {
 +
        for my $pos ( 0 .. $#sorted ) {
 +
            if ( $sorted[$pos] >= $current ) {
 +
                splice @sorted, $pos, 0, $current; # Insert $current
 +
                next INSERTION;
 +
            }
 +
        }
  
  '''let''' '''rec''' insert x l =  '''match''' l '''with'''
+
        push @sorted, $current; # No larger value has been found in @sorted
     | []    -> [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)
+
  
===Java===
+
    return @sorted;
 +
}
  
public static void insertionSort(int data[])
+
my @unsorted = qw(1 82 73 745839 928 7346 8 6 4 8 0 6 34 102);
{
+
my @sorted  = qw(1 5);
    for (int i = 0; i < data.length; i++)  
+
    {
+
      int temp = data[i];    
+
      int j = i - 1;
+
   
+
      while (j >= 0 && temp < data[j])
+
      {
+
          data[j + 1] = data[j];
+
          data[j] = temp;
+
     
+
          j--;
+
      }
+
    }
+
}
+
  
====Java Alt====
+
@sorted = insertionSort(\@unsorted, \@sorted);
 +
</pre>
  
    '''static void''' <u>insertionSort</u> ('''int[]''' A) {
+
2:
         '''int''' j;
+
<pre class="perl">
        '''for''' ('''int''' i = 1; i < A.length; i++) {
+
sub insert_sort {
          '''int''' a = A[i];
+
    for my $i (0 .. $#_) {
          '''for''' (j = i - 1; j >=0 && A[j] > a; j--)
+
         my ($j, $val) = ($i - 1, $_[$i]);
            A[j + 1] = A[j];
+
        $_[$j-- + 1] = $_[$j] while ($j >= 0 && $_[$j] > $val);
          A[j + 1] = a;
+
        $_[$j+1] = $val;
        }
+
 
     }
 
     }
 
+
}
===Haskell===
+
</pre>
 
+
  insert :: '''Ord''' a => a -> [a] -> [a]
+
  insert item []  = [item]
+
  insert item (h:t) | item <= h = item:h:t
+
                    | '''otherwise''' = h:(insert item t)
+
+
  <u>insertsort</u> :: '''Ord''' a => [a] -> [a]
+
  insertsort []    = [] 
+
  insertsort (h:t) = insert h (insertsort t)
+
 
+
====Shorter alt====
+
The insert function is the same as above.
+
 
+
  insert :: '''Ord''' a => a -> [a] -> [a]
+
  insert item []  = [item]
+
  insert item (h:t) | item <= h = item:h:t
+
                    | '''otherwise''' = h:(insert item t)
+
+
  <u>insertsort</u> :: '''Ord''' a => [a] -> [a]
+
  insertsort  =  foldr insert []
+
 
+
====Alt====
+
insertionSort :: (Ord a) => [a] -> OrdList a
+
insertionSort [] =[]
+
insertionSort (a:as) = insert a (insertionSort as)
+
+
insert :: (Ord a) => a -> OrdList a -> OrdList a
+
insert a1 [] = [a1]
+
insert a1 (a2:as)
+
      | a1 <= a2 = a1:a2:as
+
      | otherwise = a2:insert a1 as
+
 
+
 
+
 
+
===Perl===
+
 
+
  '''sub''' <u>insert_sort</u> {
+
      '''for'''('''my''' $''i'' = 0; $''i'' <= $#_; $''i''++) {
+
          '''my''' ($''j'', $''val'') = ($''i'' - 1, $_[$''i'']);
+
          $_[$''j''-- + 1] = $_[$''j''] '''while''' ($''j'' >= 0 && $_[$''j''] > $''val'');
+
          $_[$''j''+1] = $''val'';
+
      }
+
  }
+
  
 
===PHP===
 
===PHP===
 
+
<pre class="php">
  '''for'''($j=1; $j < count($array); $j++){
+
  for($j=1; $j < count($array); $j++){
 
     $temp = $array[$j];
 
     $temp = $array[$j];
 
     $i = $j;
 
     $i = $j;
     '''while'''(($i >= 0) && ($array[$i-1] > $temp)){
+
     while(($i >= 0) && ($array[$i-1] > $temp)){
 
         $array[$i] = $array[$i-1];
 
         $array[$i] = $array[$i-1];
 
         $i--;
 
         $i--;
Line 248: Line 284:
 
  }
 
  }
  
===Python===
+
//Non-decreasing order
 +
for ($j=1; $j < count($array); $j++) {
 +
$key = $array[$j];
 +
$i = $j - 1;
 +
 +
while($i >= 0 and $array[$i] > $key) {
 +
$array[$i + 1] = $array[$i];
 +
$i--;
 +
}
 +
 +
$array[$i + 1] = $key;
 +
}
  
'''def''' <u>insertsort</u>(array):
+
//Non-increasing order
    '''for''' removed_index '''in''' range(1, len(array)):
+
for ($j=1; $j < count($array); $j++) {
        removed_value = array[removed_index]
+
$key = $array[$j];
        insert_index = removed_index
+
$i = $j - 1;
        '''while''' insert_index > 0 '''and''' array[insert_index - 1] > removed_value:
+
            array[insert_index] = array[insert_index - 1]
+
while($i >= 0 and $array[$i] < $key) {
            insert_index = insert_index - 1
+
$array[$i + 1] = $array[$i];
        array[insert_index] = removed_value
+
$i--;
 +
}
 +
 +
$array[$i + 1] = $key;
 +
}
 +
</pre>
 +
 
 +
===Python===
 +
<pre class="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
 +
</pre>
  
====Python Alt====
 
 
An alternate method:
 
An alternate method:
'''def''' <u>insertsort</u>(array):
+
<pre class="python">
    lastsortedelement = 0
+
def insertsort(array):
    '''while''' lastsortedelement < len(array)-1:
+
  for lastsortedelement in range(len(array)-1):
        checked = lastsortedelement
+
      checked = lastsortedelement
        '''while''' array[checked] > array[lastsortedelement + 1] '''and''' checked > -1:
+
      while array[checked] > array[lastsortedelement + 1] and checked >= 0:
            checked = checked - 1
+
          checked -= 1
        'Insert the number into the correct position
+
      #Insert the number into the correct position
        array[checked+1], array[checked+2 : lastsortedelement+2] = array[lastsortedelement+1], array[checked+1 : lastsortedelement+1]
+
      array[checked+1], array[checked+2 : lastsortedelement+2] = array[lastsortedelement+1], array[checked+1 : lastsortedelement+1]
        lastsortedelement = lastsortedelement + 1
+
  return array
     return array
+
</pre>
 +
 
 +
===Ruby===
 +
<pre class="ruby">
 +
def insertion_sort(array)
 +
  array.each_with_index do |el,i|
 +
    j = i - 1
 +
    while j >= 0
 +
      break if array[j] <= el
 +
      array[j + 1] = array[j]
 +
      j -= 1
 +
     end
 +
    array[j + 1] = el
 +
  end
 +
end
 +
</pre>
 +
 
 +
Another version (used builtin method and binary search):
 +
<pre class="ruby">
 +
def insertion_sort(array)
 +
  for i in 1...array.size
 +
    w = array.delete_at(i)
 +
    l, r = 0, i
 +
    while l < r
 +
      m = (l + r) / 2
 +
      array[m] < w ? l = m + 1 : r = m
 +
    end
 +
    array.insert(l,w)
 +
  end
 +
  array
 +
end
 +
</pre>
  
 
===Seed7===
 
===Seed7===
Line 350: Line 444:
 
</pre>
 
</pre>
  
[[Category:C plus plus]]
 
[[Category:Java]]
 
[[Category:Pascal]]
 
[[Category:Haskell]]
 
[[Category:Objective Caml]]
 
 
[[Category:C]]
 
[[Category:C]]
[[Category:C#]]
+
[[Category:C++]]
[[Category:CAML]]
+
[[Category:C sharp]]
 
[[Category:Common Lisp]]
 
[[Category:Common Lisp]]
[[Category:F#]]
+
[[Category:Erlang]]
 +
[[Category:F sharp]]
 +
[[Category:Haskell]]
 +
[[Category:Java]]
 +
[[Category:Objective Caml]]
 +
[[Category:Pascal]]
 
[[Category:Perl]]
 
[[Category:Perl]]
 
[[Category:PHP]]
 
[[Category:PHP]]
 
[[Category:Python]]
 
[[Category:Python]]
 +
[[Category:Ruby]]
 
[[Category:Seed7]]
 
[[Category:Seed7]]
 
[[Category:Standard ML]]
 
[[Category:Standard ML]]

Latest revision as of 21:51, 7 April 2012

Related content:

Insertion sort is similar to bubble sort, but is more efficient as it reduces element comparisons somewhat with each pass. An element is compared to all the prior elements until a lesser element is found. In other words, if an element contains a value less than all the previous elements, it compares the element to all the previous elements before going on to the next comparison. Although this algorithm is more efficient than the Bubble sort, it is still inefficient compared to many other sort algorithms since it, and bubble sort, move elements only one position at a time. However, insertion sort is a good choice for small lists (about 30 elements or fewer), and for nearly-sorted lists.

Implementations[edit]

C[edit]

void insertSort(int a[], size_t 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;
    }
}


If you're trying to sort arbitrary data structures, the following modification of the above code may help. It will sort a list of void pointers (pointers to your structures) based on some external comparison function.


void sort(uint8_t (* cmp)(void *, void *), void *a[], size_t length) {
    size_t i, j;
    void   *cut;

    for (i = 1; i < length; i++) {
        cut = a[i]; // snip out pointer

        for (j = i; j && cmp(a[j - 1], cut); j--) {
            a[j] = a[j - 1]; // sift down
        }

        a[j] = cut; // insert snipped pointer
    }
}


// example comparison function

uint8_t compare_ints(void *x, void *y) {
    // assume x and y point to integers for simplicity...
    // want to return x > y

    return (*((int *) x) > *((int *) y));
}


// call: sort(compare_ints, array_of_void_pointers_to_ints, array_length);

C++[edit]

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

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=j-1;
        }
        array[j + 1] = value;
    }
}

C# 2.0[edit]

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

Common Lisp[edit]

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

Erlang[edit]

insert_sort(L) when is_list(L) ->
    insert_sort(L, []).

insert_sort([], Sorted) -> Sorted;
insert_sort([H | T], Sorted) ->
    insert_sort(T, insert(H, Sorted)).

insert(X, []) -> [X];
insert(X, Sorted) when X =< hd(Sorted) -> [X | Sorted];
insert(X, [H | T]) -> [H | insert(X, T)].

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)

Haskell[edit]

import Data.List (insert)

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

Java[edit]

static void insertionSort (int[] A) {
    for (int i = 1; i < A.length; i++) {
      int a = A[i];
      int j;
      for (j = i - 1; j >=0 && A[j] > a; j--){
        A[j + 1] = A[j];
      }
      A[j + 1] = a;
    }
}

Generic[edit]

static <T extends Comparable<? super T>> void insertionSort (T[] A) {
    for (int i = 1; i < A.length; i++) {
      T a = A[i];
      int j;
      for (j = i - 1; j >=0 && A[j].compareTo(a) > 0; j--)
        A[j + 1] = A[j];
      A[j + 1] = a;
    }
}

OCaml[edit]

This implementation uses physical equality to avoid copying sublists that are already sorted:

# let rec sort = function
    | [] -> []
    | h1::t as list -> match sort t with
      | h2::t when h1>h2 -> h2::sort(h1::t)
      | t' -> if t==t' then list else h1::t';;
val sort : 'a list -> 'a list = <fun>

For example:

# sort [1;9;2;8;3;7;4;6;5];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

another

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

Pascal[edit]

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;

Perl[edit]

1:

sub insertionSort {
    my @unsorted = @{$_[0]};
    my @sorted   = @{$_[1]};

    INSERTION:
    for my $current ( @unsorted ) { 
        for my $pos ( 0 .. $#sorted ) {
            if ( $sorted[$pos] >= $current ) {
                splice @sorted, $pos, 0, $current; # Insert $current
                next INSERTION;
            }
        }

        push @sorted, $current; # No larger value has been found in @sorted
    }

    return @sorted;
}

my @unsorted = qw(1 82 73 745839 928 7346 8 6 4 8 0 6 34 102);
my @sorted   = qw(1 5);

@sorted = insertionSort(\@unsorted, \@sorted);

2:

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

PHP[edit]

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

//Non-decreasing order
for ($j=1; $j < count($array); $j++) { 
	$key = $array[$j];
	$i = $j - 1;
	
	while($i >= 0 and $array[$i] > $key) {
		$array[$i + 1] = $array[$i];
		$i--;
	}
	
	$array[$i + 1] = $key;
}

//Non-increasing order
for ($j=1; $j < count($array); $j++) { 
	$key = $array[$j];
	$i = $j - 1;
	
	while($i >= 0 and $array[$i] < $key) {
		$array[$i + 1] = $array[$i];
		$i--;
	}
	
	$array[$i + 1] = $key;
}

Python[edit]

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

An alternate method:

def insertsort(array):
   for lastsortedelement in range(len(array)-1):
       checked = lastsortedelement
       while array[checked] > array[lastsortedelement + 1] and checked >= 0:
           checked -= 1
       #Insert the number into the correct position
       array[checked+1], array[checked+2 : lastsortedelement+2] = array[lastsortedelement+1], array[checked+1 : lastsortedelement+1]
   return array

Ruby[edit]

def insertion_sort(array)
  array.each_with_index do |el,i|
    j = i - 1
    while j >= 0
      break if array[j] <= el
      array[j + 1] = array[j]
      j -= 1
    end
    array[j + 1] = el
  end
end

Another version (used builtin method and binary search):

def insertion_sort(array)
  for i in 1...array.size
    w = array.delete_at(i)
    l, r = 0, i
    while l < r
      m = (l + r) / 2
      array[m] < w ? l = m + 1 : r = m
    end
    array.insert(l,w)
  end
  array
end

Seed7[edit]

const proc: insertionSort (inout array integer: arr) is func
  local
    var integer: i is 0;
    var integer: j is 0;
    var integer: help is 0;
  begin
    for i range 2 to length(arr) do
      j := i;
      help := arr[i];
      while j > 1 and arr[j-1] > help do
        a[j] := a[j-1];
        decr(j);
      end while;
      a[j] := help;
    end for;
  end func;

Original source: [1]

Standard ML[edit]

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;

Turing[edit]

var nombres, limit : int
get nombres
get limit
var sure : boolean := false
var g, smaller : int := 0
var k : int := limit + 1
var last : int := limit
var first : int := 1
var last2 : int := nombres
var br : int := limit - 1
var rann, sort : array 1 .. nombres of int
for i : 1 .. nombres
    rann (i) := Rand.Int (0, limit)
    sort (i) := k
end for
if rann (1) <= limit then
    last := rann (1)
    sort (1) := rann (1)
end if
for h : 2 .. upper (rann)
    if rann (h) < last then
        for decreasing f : nombres - 1 .. 1
            sort (f + 1) := sort (f)
        end for
        sort (1) := rann (h)
        last := rann (h)
    else
        for i : 1 .. upper (rann)
            if rann (h) < sort (i) then
                for decreasing f : nombres - 1 .. i
                    sort (f + 1) := sort (f)
                end for
                sort (i) := rann (h)
                exit
            end if
        end for
    end if
end for
for b : 1 .. upper (sort)
    put " ", sort (b) ..
end for