Difference between revisions of "Insertion sort"

From CodeCodex

(C++)
m
Line 4: Line 4:
 
==Implementations==
 
==Implementations==
 
===C++===
 
===C++===
+
<highlightsyntax language="cpp">
'''template'''< '''typename''' Iterator >
+
template< typename Iterator >
'''void''' insertion_sort( Iterator First, Iterator Last )
+
void insertion_sort( Iterator First, Iterator Last )
{
+
{
    Iterator min = First;
+
    Iterator min = First;
    '''for'''( Iterator i = First + 1; i < Last; ++i )
+
    for( Iterator i = First + 1; i < Last; ++i )
        '''if''' ( *i < *min )
+
        if ( *i < *min )
            min = i;
+
            min = i;
+
    std::iter_swap( First, min );
+
    '''while'''( ++First < Last )
+
        '''for'''( Iterator j = First; *j < *(j - 1); --j )
+
            std::iter_swap( (j - 1), j );
+
}
+
  
 +
    std::iter_swap( First, min );
 +
    while( ++First < Last )
 +
        for( Iterator j = First; *j < *(j - 1); --j )
 +
            std::iter_swap( (j - 1), j );
 +
}
 +
</highlightsyntax>
 
===C===
 
===C===
 +
<highlightsyntax language="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;
+
</highlightsyntax>
      }
+
  }
+
 
+
 
===C#===
 
===C#===
 +
<highlightsyntax language="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--;
        '''while''' ((j >= 0) && (array[j].CompareTo(value) > 0))
+
        }
        {
+
        array[j + 1] = value;
            array[j + 1] = array[j];
+
    }
            j--;
+
}
        }
+
</highlightsyntax>
        array[j + 1] = value;
+
    }
+
}
+
  
 
===C# 2.0===
 
===C# 2.0===
 
+
<highlightsyntax language="csharp">
 
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;'''
+
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;
 +
    }
 +
}
 +
</highlightsyntax>
  
  
  
 
===Pascal===
 
===Pascal===
 
+
<highlightsyntax language="pascal">
PROCEDURE InsertionSort(var Menge: MengeIntegerTyp; Links, Rechts: INTEGER;)
+
PROCEDURE InsertionSort(var Menge: MengeIntegerTyp; Links, Rechts: INTEGER;)
VAR
+
VAR
  Index, Einfuegeposition, Zwischenspeicher: INTEGER;
+
Index, Einfuegeposition, Zwischenspeicher: INTEGER;
BEGIN
+
BEGIN
  FOR Index := Links + 1 TO Rechts DO
+
  FOR Index := Links + 1 TO Rechts DO
  BEGIN
+
  BEGIN
    Zwischenspeicher := Menge[Index];
+
    Zwischenspeicher := Menge[Index];
    Einfuegeposition := Index;
+
    Einfuegeposition := Index;
    WHILE ((Menge[Einfugeposition - 1] > Zwischenspeicher) AND
+
    WHILE ((Menge[Einfugeposition - 1] > Zwischenspeicher) AND
            (Einfuegeposition > Links)) DO
+
          (Einfuegeposition > Links)) DO
    BEGIN
+
    BEGIN
      Menge[Einfuegeposition] := Menge[Einfuegeposition - 1];
+
      Menge[Einfuegeposition] := Menge[Einfuegeposition - 1];
      Einfuegeposition := Einfuegeposition - 1;
+
      Einfuegeposition := Einfuegeposition - 1;
    END;
+
    END;
    Menge[Einfuegeposition] := Zwischenspeicher;
+
    Menge[Einfuegeposition] := Zwischenspeicher;
  END;
+
  END;
END;
+
END;
 
+
</highlightsyntax>
  
  
Line 151: Line 152:
  
 
===Java===
 
===Java===
 
+
<highlightsyntax language="language">
public static void insertionSort(int data[])
+
static void insertionSort (int[] A) {
{
+
     for (int i = 1; i < A.length; i++) {
     for (int i = 0; i < data.length; i++)  
+
      int a = A[i];
    {
+
      int j;
      int temp = data[i];    
+
      for (j = i - 1; j >=0 && A[j] > a; j--)
      int j = i - 1;
+
        A[j + 1] = A[j];
   
+
      A[j + 1] = a;
      while (j >= 0 && temp < data[j])
+
      {
+
          data[j + 1] = data[j];
+
          data[j] = temp;
+
     
+
          j--;
+
      }
+
 
     }
 
     }
}
+
}
 +
</highlightsyntax>
  
====Java Alt====
+
====Generic====
 
+
<highlightsyntax language="language">
    '''static void''' <u>insertionSort</u> ('''int[]''' A) {
+
static <T extends Comparable<T>> void insertionSort (T[] A) {
        '''int''' j;
+
    for (int i = 1; i < A.length; i++) {
        '''for''' ('''int''' i = 1; i < A.length; i++) {
+
      T a = A[i];
          '''int''' a = A[i];
+
      int j;
          '''for''' (j = i - 1; j >=0 && A[j] > a; j--)
+
      for (j = i - 1; j >=0 && A[j].compareTo(a) > 0; j--)
            A[j + 1] = A[j];
+
        A[j + 1] = A[j];
          A[j + 1] = a;
+
      A[j + 1] = a;
        }
+
 
     }
 
     }
 +
}
 +
</highlightsyntax>
  
 
===Haskell===
 
===Haskell===
 +
<highlightsyntax language="haskell">
 +
insert :: Ord a => a -> [a] -> [a]
 +
insert item []  = [item]
 +
insert item (h:t) | item <= h = item:h:t
 +
                  | otherwise = h:(insert item t)
  
  insert :: '''Ord''' a => a -> [a] -> [a]
+
insertsort :: Ord a => [a] -> [a]
  insert item []  = [item]
+
insertsort  =  foldr insert []
  insert item (h:t) | item <= h = item:h:t
+
</highlightsyntax>
                    | '''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===
 
===Perl===
Line 245: Line 217:
  
 
2:
 
2:
 
+
<highlightsyntax language="perl">
  '''sub''' <u>insert_sort</u> {
+
sub insert_sort {
      '''for'''('''my''' $''i'' = 0; $''i'' <= $#_; $''i''++) {
+
    for(my $i = 0; $i <= $#_; $i++) {
          '''my''' ($''j'', $''val'') = ($''i'' - 1, $_[$''i'']);
+
        my ($j, $val) = ($i - 1, $_[$i]);
          $_[$''j''-- + 1] = $_[$''j''] '''while''' ($''j'' >= 0 && $_[$''j''] > $''val'');
+
        $_[$j-- + 1] = $_[$j] while ($j >= 0 && $_[$j] > $val);
          $_[$''j''+1] = $''val'';
+
        $_[$j+1] = $val;
      }
+
    }
  }
+
}
 +
</highlightsyntax>
  
 
===PHP===
 
===PHP===
Line 296: Line 269:
  
 
===Python===
 
===Python===
 
+
<highlightsyntax language="python">
'''def''' <u>insertsort</u>(array):
+
def insertsort(array):
    '''for''' removed_index '''in''' range(1, len(array)):
+
    for removed_index in range(1, len(array)):
        removed_value = array[removed_index]
+
        removed_value = array[removed_index]
        insert_index = removed_index
+
        insert_index = removed_index
        '''while''' insert_index > 0 '''and''' array[insert_index - 1] > removed_value:
+
        while insert_index > 0 and array[insert_index - 1] > removed_value:
            array[insert_index] = array[insert_index - 1]
+
            array[insert_index] = array[insert_index - 1]
            insert_index = insert_index - 1
+
            insert_index -= 1
        array[insert_index] = removed_value
+
        array[insert_index] = removed_value
 +
</highlightsyntax>
  
 
====Python Alt====
 
====Python Alt====
 
An alternate method:
 
An alternate method:
'''def''' <u>insertsort</u>(array):
+
<highlightsyntax language="python">
    lastsortedelement = 0
+
def insertsort(array):
    '''while''' lastsortedelement < len(array)-1:
+
  lastsortedelement = 0
        checked = lastsortedelement
+
  while lastsortedelement < len(array)-1:
        '''while''' array[checked] > array[lastsortedelement + 1] '''and''' checked > -1:
+
      checked = lastsortedelement
            checked = checked - 1
+
      while array[checked] > array[lastsortedelement + 1] and checked > -1:
        'Insert the number into the correct position
+
          checked = checked - 1
        array[checked+1], array[checked+2 : lastsortedelement+2] = array[lastsortedelement+1], array[checked+1 : lastsortedelement+1]
+
      'Insert the number into the correct position
        lastsortedelement = lastsortedelement + 1
+
      array[checked+1], array[checked+2 : lastsortedelement+2] = array[lastsortedelement+1], array[checked+1 : lastsortedelement+1]
    return array
+
      lastsortedelement = lastsortedelement + 1
 +
  return array
 +
</highlightsyntax>
  
 
===Seed7===
 
===Seed7===

Revision as of 08:44, 20 August 2008

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

C++

<highlightsyntax language="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 );

} </highlightsyntax>

C

<highlightsyntax language="c"> 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;
   }

} </highlightsyntax>

C#

<highlightsyntax language="csharp"> 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;
   }

} </highlightsyntax>

C# 2.0

<highlightsyntax language="csharp"> 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;
   }

} </highlightsyntax>


Pascal

<highlightsyntax language="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; </highlightsyntax>


OCaml

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]

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 '())
       (if (<= target (first list))
            (cons target list)
            (cons (first list) (insert target (rest list))))))

(defun insertSort (myList)
   (if (null mylist)
       '()
       (insert (first myList) (insertSort (rest myList)))))

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)

Java

<highlightsyntax language="language"> 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;
   }

} </highlightsyntax>

Generic

<highlightsyntax language="language"> static <T extends Comparable<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;
   }

} </highlightsyntax>

Haskell

<highlightsyntax language="haskell"> insert :: Ord a => a -> [a] -> [a] insert item [] = [item] insert item (h:t) | item <= h = item:h:t

                 | otherwise = h:(insert item t)

insertsort :: Ord a => [a] -> [a] insertsort = foldr insert [] </highlightsyntax>

Perl

1: <highlightsyntax language="perl"> 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); </highlightsyntax>

2: <highlightsyntax language="perl"> sub insert_sort {

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

} </highlightsyntax>

PHP

<highlightsyntax language="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;
}


//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 = $i - 1; }

$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 = $i - 1; }

$array[$i + 1] = $key; } </highlightsyntax>

Python

<highlightsyntax language="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

</highlightsyntax>

Python Alt

An alternate method: <highlightsyntax language="python"> def insertsort(array):

  lastsortedelement = 0
  while lastsortedelement < len(array)-1:
      checked = lastsortedelement
      while array[checked] > array[lastsortedelement + 1] and checked > -1:
          checked = 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]
      lastsortedelement = lastsortedelement + 1
  return array

</highlightsyntax>

Seed7

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

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

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