Difference between revisions of "Insertion sort"

From CodeCodex

(OCaml)
(OCaml)
Line 110: Line 110:
  
 
===OCaml===
 
===OCaml===
The insert function inserts a new element into a sorted list. The insertion_sort function accumulates a sorted list by folding the insert function over each element in the given list:
+
  # let rec sort = function
 
+
     | [] -> []
  # let rec insert list x = match list with
+
     | h1::t as list -> match sort t with
     | [] -> [x]
+
      | h2::t when h1>h2 -> h2::sort(h1::t)
     | h :: t when h < x -> h :: insert t x
+
      | t' -> if t==t' then list else h1::t';;
    | t -> x :: t;;
+
  val sort : 'a list -> 'a list = <fun>
val insert : 'a list -> 'a -> 'a list = <fun>
+
# let insertion_sort list = List.fold_left insert []  list;;
+
  val insertion_sort : 'a list -> 'a list = <fun>
+
  
 
For example:
 
For example:
  
  # insertion_sort [1;9;2;8;3;7;4;6;5];;
+
  # sort [1;9;2;8;3;7;4;6;5];;
 
  - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
 
  - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
  

Revision as of 00:37, 14 January 2007

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

#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

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

# 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 (equal list NIL)
       (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

public static void insertionSort(int data[])
{
   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

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

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

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

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

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

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