Difference between revisions of "Insertion sort"

From CodeCodex

(Java)
(highlightsyntax -> pre)
Line 4: Line 4:
 
==Implementations==
 
==Implementations==
 
===C++===
 
===C++===
<highlightsyntax language="cpp">
+
<pre class="cpp">
 
template< typename Iterator >
 
template< typename Iterator >
 
void insertion_sort( Iterator First, Iterator Last )
 
void insertion_sort( Iterator First, Iterator Last )
Line 18: Line 18:
 
             std::iter_swap( (j - 1), j );
 
             std::iter_swap( (j - 1), j );
 
}
 
}
</highlightsyntax>
+
</pre>
 +
 
 
===C===
 
===C===
<highlightsyntax language="c">
+
<pre class="c">
 
void insertSort(int a[], size_t length) {
 
void insertSort(int a[], size_t length) {
 
     int i, j, value;
 
     int i, j, value;
Line 32: Line 33:
 
     }
 
     }
 
}
 
}
</highlightsyntax>
+
</pre>
 +
 
 
===C#===
 
===C#===
<highlightsyntax language="csharp">
+
<pre class="csharp">
 
static void InsertSort(IComparable[] array)
 
static void InsertSort(IComparable[] array)
 
{
 
{
Line 51: Line 53:
 
     }
 
     }
 
}
 
}
</highlightsyntax>
+
</pre>
  
 
===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.
  
<highlightsyntax language="csharp">
+
<pre class="csharp">
 
static void InsertSort<T>(IList<T> list) where T : IComparable<T>
 
static void InsertSort<T>(IList<T> list) where T : IComparable<T>
 
{
 
{
Line 73: Line 75:
 
     }
 
     }
 
}
 
}
</highlightsyntax>
+
</pre>
  
 
===Pascal===
 
===Pascal===
<highlightsyntax language="pascal">
+
<pre class="pascal">
 
PROCEDURE InsertionSort(var Menge: MengeIntegerTyp; Links, Rechts: INTEGER;)
 
PROCEDURE InsertionSort(var Menge: MengeIntegerTyp; Links, Rechts: INTEGER;)
 
VAR
 
VAR
Line 94: Line 96:
 
   END;
 
   END;
 
END;
 
END;
</highlightsyntax>
+
</pre>
 
+
 
+
  
 
===OCaml===
 
===OCaml===
Line 150: Line 150:
  
 
===Java===
 
===Java===
<highlightsyntax language="java122">
+
<pre class="java">
 
static void insertionSort (int[] A) {
 
static void insertionSort (int[] A) {
 
     for (int i = 1; i < A.length; i++) {
 
     for (int i = 1; i < A.length; i++) {
Line 161: Line 161:
 
     }
 
     }
 
}
 
}
</highlightsyntax>
+
</pre>
  
 
====Generic====
 
====Generic====
<highlightsyntax language="java122">
+
<pre class="java">
 
static <T extends Comparable<? super T>> void insertionSort (T[] A) {
 
static <T extends Comparable<? super T>> void insertionSort (T[] A) {
 
     for (int i = 1; i < A.length; i++) {
 
     for (int i = 1; i < A.length; i++) {
Line 174: Line 174:
 
     }
 
     }
 
}
 
}
</highlightsyntax>
+
</pre>
  
 
===Haskell===
 
===Haskell===
<highlightsyntax language="haskell">
+
<pre class="haskell">
 
import Data.List (insert)
 
import Data.List (insert)
  
 
insertsort :: Ord a => [a] -> [a]
 
insertsort :: Ord a => [a] -> [a]
 
insertsort  =  foldr insert []
 
insertsort  =  foldr insert []
</highlightsyntax>
+
</pre>
  
 
===Perl===
 
===Perl===
 
1:
 
1:
<highlightsyntax language="perl">
+
<pre class="perl">
 
sub insertionSort {
 
sub insertionSort {
 
     my @unsorted = @{$_[0]};
 
     my @unsorted = @{$_[0]};
Line 210: Line 210:
  
 
@sorted = insertionSort(\@unsorted, \@sorted);
 
@sorted = insertionSort(\@unsorted, \@sorted);
</highlightsyntax>
+
</pre>
  
 
2:
 
2:
<highlightsyntax language="perl">
+
<pre class="perl">
 
sub insert_sort {
 
sub insert_sort {
 
     for my $i (0 .. $#_) {
 
     for my $i (0 .. $#_) {
Line 221: Line 221:
 
     }
 
     }
 
}
 
}
</highlightsyntax>
+
</pre>
  
 
===PHP===
 
===PHP===
<highlightsyntax language="php">
+
<pre class="php">
 
  for($j=1; $j < count($array); $j++){
 
  for($j=1; $j < count($array); $j++){
 
     $temp = $array[$j];
 
     $temp = $array[$j];
Line 234: Line 234:
 
     $array[$i] = $temp;
 
     $array[$i] = $temp;
 
  }
 
  }
 
 
  
 
//Non-decreasing order
 
//Non-decreasing order
Line 262: Line 260:
 
$array[$i + 1] = $key;
 
$array[$i + 1] = $key;
 
}
 
}
</highlightsyntax>
+
</pre>
  
 
===Python===
 
===Python===
<highlightsyntax language="python">
+
<pre class="python">
 
def insertsort(array):
 
def insertsort(array):
 
     for removed_index in range(1, len(array)):
 
     for removed_index in range(1, len(array)):
Line 274: Line 272:
 
             insert_index -= 1
 
             insert_index -= 1
 
         array[insert_index] = removed_value
 
         array[insert_index] = removed_value
</highlightsyntax>
+
</pre>
  
====Python Alt====
 
 
An alternate method:
 
An alternate method:
<highlightsyntax language="python">
+
<pre class="python">
 
def insertsort(array):
 
def insertsort(array):
 
   for lastsortedelement in range(len(array)-1):
 
   for lastsortedelement in range(len(array)-1):
Line 287: Line 284:
 
       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]
 
   return array
 
   return array
</highlightsyntax>
+
</pre>
  
 
===Ruby===
 
===Ruby===
<pre>
+
<pre class="ruby">
 
def insertion_sort(array)
 
def insertion_sort(array)
 
   array.each_with_index do |el,i|
 
   array.each_with_index do |el,i|
Line 305: Line 302:
  
 
Another version (used builtin method and binary search):
 
Another version (used builtin method and binary search):
<pre>
+
<pre class="ruby">
 
def insertion_sort(array)
 
def insertion_sort(array)
 
   for i in 1...array.size
 
   for i in 1...array.size

Revision as of 15:10, 12 December 2010

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

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

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

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

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

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;

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]

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

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

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

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

Haskell

import Data.List (insert)

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

Perl

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

 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

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

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

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