Insertion sort
From Algorithm wiki
 Related content:
|
Contents |
[edit] Introduction
- One of the simplest sorting algorithms is the insertion sort. Insertion sort consists of n - 1 passes. For pass p = 2 through n, insertion sort ensures that the elements in positions 1 through p are in sorted order. Insertion sort makes use of the fact that elements in positions 1 through p - 1 are already known to be in sorted order.
[edit] Pseudocode
[edit] Deutsch(German Language)
INSERTIONSORT(A) for j = 2 to length[A] do key = A[j] //Füge A[j] ein in die sortierte Folge A[1 .. j − 1]. i = j − 1 while i > 0 and A[i] > key do A[i + 1] = A[i] i = i − 1 A[i + 1] = key
[edit] PHP Code
function insert_sort($arr){
$count = count($arr);
for($i=1; $i<$count; $i++){
$tmp = $arr[$i];
$j = $i - 1;
while($j >= 0 && $arr[$j] > $tmp){
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
$j–-;
}
}
return $arr;
}
[edit] C++ Code
[edit] int
void insertionSort(int numbers[], int array_size)
{
int i, j, value;
for (i = 1; i < array_size; ++i)
{
value = numbers[i];
for (j = i; j > 0 && numbers[j - 1] > value; --j)
{
numbers[j] = numbers[j - 1];
}
numbers[j] = value;
}
}
[edit] template
template <typename Type> inline
void Insertion(Type *pF, Type *pL)
{
Type *pI, *pJ;
Type v;
for (pI=pF; ++pI<pL;) {
v = *pI;
if (v < *pF) {
copy_backward(pF, pI, pI+1);
*pF = v;
} else {
for (pJ=pI; v < *--pJ;) { *(pJ+1) = *pJ; }
*(pJ+1) = v;
}
}
}
[edit] C# Code
using System；
namespace InsertionSorter
{
public class InsertionSorter
{
public void Sort（int [] list）
{
for（int i=1；i＜list.Length；i++）
{
int t=list[i]；
int j=i；
while（（j＞0）&&（list[j-1]＞t））
{
list[j]=list[j-1]；
--j；
}
list[j]=t；
}
}
}
public class MainClass
{
public static void Main（）
{
int[] iArrary=new int[]{1,13,3,6,10,55,98,2,87,12,34,75,33,47}；
InsertionSorter ii=new InsertionSorter（）；
ii.Sort（iArrary）；
for（int m=0；m＜iArrary.Length；m++）
Console.Write（"{0}",iArrary[m]）；
Console.WriteLine（）；
}
}
}
[edit] Java Code
[edit] Java Code1
public void Straight_Insert_Sort(int[] array) {
for (int i = 0, temp = 0; i < array.length - 1; i++) {
for (int j = i; 0 <= j; j--) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
} else
break;
}
}
}
[edit] Java Code2
class InsertionSortAlgorithm extends SortAlgorithm {
void sort (int a[]) throws Exception {
for (int j = 1; j < a.length; j++) {
int T = a[j];
int i = j - 1;
while (i >= 0 && a[i] > T) {
a[i+1] = a[i];
i -= 1;
compex(j,i);
pause();
}
a[i+1] = T;
}
pause();
}
}
[edit] C Code
see also C++ code
[edit] C optimized code (binary search)
void insertion_sort (int* tab, size_t size)
{
int *i, *j, *p, *end = tab+size;
for (i=tab+1; i < end; i++)
{
/* binary search */
int *s_base = tab, *s_end = i-1;
while ( (j = s_base+((s_end-s_base)/2)) < s_end )
{
if (*j > *i)
{
s_end = j;
}
else if (*j <= *i)
{
s_base = j+1;
}
}
if (*j > *i)
{
int tmp = *i;
for (p = i; p > j; p--)
{
*p = *(p-1);
}
*j = tmp;
}
}
}
[edit] VB Code
Sub Insertion_Sort(ByVal array() As Integer)
Dim j, i, key As Integer
For i = 1 To array.Length - 1
key = array(i)
j = i - 1
While j > 0 And array(j) > key
array(j) = array(j - 1)
j = j - 1
End While
array(j + 1) = key
Next
End Sub
vb code not valid!!!
[edit] Perl Code
sub insertion_sort
{
my ($a) = @_;
for(my $j = 1; $j < scalar(@$a); $j++)
{
my $key = $$a[$j];
my $i = $j - 1;
while($i >= 0 && $$a[$i] > $key)
{
$$a[$i + 1] = $$a[$i];
$i--;
}
$$a[$i + 1] = $key;
}
}
[edit] Pascal/Delphi Code
procedure InsertionSort(var A:array of Integer);
var
i, j: Integer;
key: Integer;
begin
for j:=low(A)+1 to high(A) do
begin
key := A[j];
i := j - 1;
while((i >= 0)and(A[i] > key))do
begin
A[i+1] := A[i];
dec(i);
end;
A[i+1] := key;
end;
end;
other Version:
procedure insertionsort(a:array of char, arrlength:integer); var i,j,v : integer; begin for i := 2 to arrlength do begin v := a[i]; j := i; while a[j-1] > v do begin a[j] := a[j-1]; j := j - 1; end; //while a[j] := v; end; //for end; //inserationsort
[edit] Prolog Code
% ?-insertionsort([8, 2, 5, 3, 9, 1, 6, 7, 4], SL). insertionsort([], []). insertionsort([X|L], SL) :- insertionsort(L, ZSL), insert_(X, ZSL, SL). insert_(X, [Y|SL1], [Y|SL2]) :- X > Y, !, insert_(X, SL1, SL2). insert_(X, SL, [X|SL]).
[edit] Python Code
def insertionSort(array):
for j in range(1, len(array)):
i = j - 1
tmp = array[j]
while i > -1 and array[i] > tmp:
array[i+1] = array[i]
i -= 1
array[i+1] = tmp
[edit] Ruby Code
module InsertionSort
def self.sort(keys)
sort!(keys.clone)
end
def self.sort!(keys)
for j in 1...keys.size
key = keys[j]
i = j-1
while (i >= 0 and keys[i] > key)
keys[i+1] = keys[i]
i -= 1
end
keys[i+1] = key
end
keys
end
end
[edit] JavaScript Code
function insertionsort(/* ... */){
for( var i = 1; i < arguments.length; i++){
var key = arguments[i];
for (j = i; j > 0 && arguments[j - 1] > key; --j)
{
arguments[j] = arguments[j - 1];
}
arguments[j] = key;
}
var vet = new Array()
for(var i=0;i<arguments.length;i++)
vet[i] = arguments[i]
return vet
}
//Exemple:
var p = insertionsort(12,32,2,0,1,-6,5)
[edit] Basic Code
By Dave Stratford
DEF PROC_InsertionSort(Size%)
FOR I%=2 TO Size%
Temp%=data%(I%)
J%=I%
WHILE J%>1 AND Temp%<data%(J%-1)
data%(J%)=data%(J%-1)
J%=J%-1
ENDWHILE
IF J% <> I% data%(J%)=Temp%
NEXT I%
ENDPROC
