Algorithm Implementation/Sorting/Insertion sort
Ada
[edit | edit source]Sorts an array of integers.
type Integer_Array is array (Natural range <>) of Integer;
procedure Insertion_Sort (A : in out Integer_Array) is
Value : Integer;
J : Natural;
begin
for I in A'First + 1 .. A'Last loop
Value := A(I);
J := I - 1;
while J >= A'First and then A(J) > Value loop
A(J + 1) := A(J);
J := J - 1;
end loop;
A(J + 1) := Value;
end loop;
end Insertion_Sort;
Func insertionSort( ByRef $array )
For $i = 1 to Ubound( $array ) - 1
$j = $i - 1
$temp = $array[$i]
While ( $j >= 0 ) And ( $array[$j] > $temp )
$array[$j+1] = $array[$j]
$j -= 1
WEnd
$array[$j+1] = $temp
Next
EndFunc
C/C++
[edit | edit source]In C:
#include <iostream>
using namespace std;
void insertSort(int a[], int length)
{
int i, j, value;
for(i = 0 ; 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;
}
}
In C++:
#include <iostream>
using namespace std;
template<class Iterator>
void insertion_sort( Iterator a, Iterator end )
{
std::iter_swap( a, std::min_element( a, end ) );
for ( Iterator b = a; ++b < end; a = b )
for( Iterator c = b; *c < *a; --c, --a )
std::iter_swap( a, c );
}
In C++, half insertion sort:
void halfInsertSort(int array[], int length)
{
int begin;
int end;
int middle;
int value;
for (int i = 1; i < length; ++i)
{
value = array[i];
begin = 0;
end = i - 1;
while (begin <= end)
{
middle = (begin + end) / 2;
if (value < array[middle])
{
end = middle - 1;
}
else
{
begin = middle + 1;
}
}
for (int j = i - 1; j >= begin; --j)
{
array[j + 1] = array[j];
}
array[begin] = value;
}
}
C#
[edit | edit source]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;
}
}
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;
}
}
CAML
[edit | edit source]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 ;;
(defun insert (target list)
(if (null list)
(cons target nil)
(if (<= target (first list))
(cons target list)
(cons (first list) (insert target (rest list))))))
(defun insertSort (myList)
(if (null myList)
nil
(insert (first myList) (insertSort (rest myList)))))
This implementation of Insertion sort follows closely the implementation that can be found in the GPL FORTRAN 90/95 GPL library AFNL.
! ***********************************
! *
Subroutine Insrt(X, Ipt)
! *
! ***********************************
! * Sort Array X(:) in ascendent order.
! * If present Ipt, a pointer with the
! * changes is returned in Ipt.
! ***********************************
Real (kind=4), Intent (inout) :: X(:)
Integer, Intent (out), Optional :: Ipt(:)
Real (kind=4) :: Rtmp
Integer :: I, J
If (Present(Ipt)) Then
Forall (I=1:Size(X)) Ipt(I) = I
Do I = 2, Size(X)
Rtmp = X(I)
Do J = I-1, 1, -1
If (Rtmp < X(J)) Then
X(J+1) = X(J)
CALL Swap(Ipt, J, J+1)
Else
Exit
End If
End Do
X(J+1) = Rtmp
End Do
Else
Do I = 2, Size(X)
Rtmp = X(I)
Do J = I-1, 1, -1
If (Rtmp < X(J)) Then
X(J+1) = X(J)
Else
Exit
End If
End Do
X(J+1) = Rtmp
End Do
End If
Return
End Subroutine Insrt
! ***********************************
! *
Subroutine Swap(X, I, J)
! *
! ***********************************
! * Swaps elements I and J of array X(:).
! ***********************************
Integer, Intent (inout) :: X(:)
Integer, Intent (in) :: I, J
Integer :: Itmp
Itmp = X(I)
X(I) = X(J)
X(J) = Itmp
Return
End Subroutine Swap
F#
[edit | edit source]let insertionSort l =
let rec insert x sortedList =
match sortedList with
| smallest :: sortedTail when smallest < x -> smallest :: insert x sortedTail
| _ -> x :: sortedList
List.foldBack insert l []
Go
[edit | edit source]func InsertionSort(data []int) {
for i, v := range data {
j := i
for ;j > 0 && v < data[j - 1]; j-- {
data[j] = data[j - 1]
}
data[j] = v
}
}
Java
[edit | edit source]public static void insertionsort(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
int copyNumber = numbers[i];
int j = i;
while (j > 0 && copyNumber < numbers[j-1]) {
numbers[j] = numbers[j-1];
j--;
}
numbers[j] = copyNumber;
}
}
another general implements.
public static < E extends Comparable<? super E> > void insertSort( E[] comparable )
{
for ( int i = 1; i < comparable.length; i++ )
{
E value = comparable[i];
int j = i - 1;
while ( j >= 0 && comparable[j].compareTo( value ) > 0 )
{
comparable[j + 1] = comparable[j--];
}
comparable[j + 1] = value;
}
}
// Assumes all elements are non-null and non-undefined
function insertionSort(sortMe) {
for (var i = 0, j; i < sortMe.length; ++i) {
var tmp = sortMe[i];
for (var j = i - 1; j >= 0 && sortMe[j] > tmp; --j)
sortMe[j + 1] = sortMe[j];
sortMe[j + 1] = tmp;
}
}
import Data.List (insert)
insertsort :: Ord a => [a] -> [a]
insertsort = foldr insert []
OCaml
[edit | edit source]In lists
[edit | edit source]let rec insert e = function
h::t when e <= h -> h :: insert e t
| l -> e :: l
let rec insertion_sort = function
[] -> []
| h::t -> insert h (insertion_sort t)
shorter version
[edit | edit source]The insert function is the same as above.
let rec insert e = function
h::t when e <= h -> h :: insert e t
| l ->
let insertion_sort xs = List.fold_right insert xs []
Procedure InsertionSort(var ArrayOfOrd: AnyOrdType);
var
Top, InsertionPos: integer;
Cache :string;
Begin
for Top := 1 to length(ArrayOfOrd) - 1 do
begin
Cache := ArrayOfOrd[Top];
InsertionPos := Top;
while (ArrayOfOrd[InsertionPos - 1] > Cache) and (InsertionPos > 0) do
begin
ArrayOfOrd[InsertionPos] := ArrayOfOrd[InsertionPos - 1];
dec(InsertionPos);
end;
ArrayOfOrd[InsertionPos] := Cache;
end;
End;
Linked list version
procedure insertionSort(var L:PNode);
var h, x, xs, y, z:PNode;
begin
h := NIL;
x := L;
while x <> NIL do
begin
xs := x^.next;
y := h;
z :=NIL;
while (y <> NIL)and(x^.key > y^.key)do
begin
z := y;
y := y^.next;
end;
x^.next := y;
if z <> NIL then
z^.next := x
else
h := x;
x := xs;
end;
L := h;
end;
Perl
[edit | edit source]sub insert_sort {
for(my $i = 1; $i <= $#_; $i++) {
my ($j, $val) = ($i - 1, $_[$i]);
$_[$j-- + 1] = $_[$j] while ($j >= 0 && $_[$j] > $val);
$_[$j+1] = $val;
}
}
Phix
[edit | edit source]function insertion_sort(sequence s)
object temp
integer j
for i=2 to length(s) do
temp = s[i]
j = i-1
while j>=1 and s[j]>temp do
s[j+1] = s[j]
j -= 1
end while
s[j+1] = temp
end for
return s
end function
PHP
[edit | edit source]for ($j=1; $j < count($array); $j++) {
$temp = $array[$j];
$i = $j;
while (($i >= 1) && ($array[$i-1] > $temp)) {
$array[$i] = $array[$i-1];
$i--;
}
$array[$i] = $temp;
}
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
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;
shorter version
[edit | edit source]The insert function is the same as above.
fun insert (x:real, []) = [x]
| insert (x, y::ys) =
if x <= y then x::y::ys
else y::insert(x, ys)
val insertion_sort = foldr insert []
Ruby
[edit | edit source]It sorts the original array.
def insert_sort!(list)
for i in 1..(list.length - 1)
value = list[i]
j = i - 1
while j >= 0 and list[j] > value
list[j + 1] = list[j]
j -= 1
end
list[j + 1] = value
end
end
Swift
[edit | edit source]In Swift:
func insertionSort<T: Comparable> (list: inout [T]) {
for i in 1..<list.count {
var j = i - 1
let x = list[i]
while 0 <= j && x < list[j] {
swap(&list[j+1], &list[j])
j -= 1
}
list[j+1] = x
}
}
NASM
[edit | edit source]C prototype is
void isort(int *a, int n)
Assembler routine is
isort:
%define a [ebp + 8]
%define n [ebp + 12]
enter 0, 0
pusha
mov ecx, 1
for:
mov ebx, ecx
imul ebx, 4
add ebx, a
mov ebx, [ebx]
mov edx, ecx
dec edx
while:
cmp edx, 0
jl while_quit
mov eax, edx
imul eax, 4
add eax, a
cmp ebx, [eax]
jge while_quit
mov esi, [eax]
mov dword [eax + 4], esi
dec edx
jmp while
while_quit:
mov [eax], ebx
inc ecx
cmp ecx, n
jl for
popa
leave
ret
VB
[edit | edit source]Public Sub InsertionSort(ByRef ArrayAngka() As Long)
Dim i, j As Integer
Dim t As Long
For i = 0 To (n - 1)
For j = i + 1 To 1 Step -1
If ArrayAngka(j) < ArrayAngka(j - 1) Then
Call tukar(ArrayAngka(j), ArrayAngka(j - 1))
End If
Next j
Next i
End Sub
Private Sub tukar(data1 As Long, data2 As Long)
Dim temp As Long
temp = data1
data1 = data2
data2 = temp
End Sub
And here's something a little bit quicker.
Public Sub Insertionsort(nums() As Long)
Dim i&, j&, k&, length&
length = UBound(nums)
For i = 1 To length
j = nums(i)
k = i
Do While (k > 0) And (nums(k - 1) > j)
nums(k) = nums(k - 1)
k = k - 1
Loop
nums(k) = j
Next i
End Sub