Sorting algorithms/Insertion sort
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
An O(n^2) sorting algorithm which moves elements one at a time into the correct position. The algorithm is as follows (from the wikipedia):
insertionSort(array A) for i = 1 to length[A]-1 do value = A[i] j = i-1 while j >= 0 and A[j] > value do A[j + 1] = A[j] j = j-1 A[j+1] = value
Writing the algorithm for integers will suffice.
Ada
type Data_Array is array(Natural range <>) of Integer;
procedure Insertion_Sort(Item : in out Data_Array) is
First : Natural := Item'First;
Last : Natural := Item'Last;
J : Integer;
Value : Integer;
begin
for I in (First + 1)..Last loop
Value := Item(I);
J := I - 1;
while J in Item'range and then Item(J) > Value loop
Item(J + 1) := Item(J);
J := J - 1;
end loop;
Item(J + 1) := Value;
end loop;
end Insertion_Sort;
ALGOL 68
MODE DATA = REF CHAR; PROC in place insertion sort = (REF[]DATA item)VOID: BEGIN INT first := LWB item; INT last := UPB item; INT j; DATA value; FOR i FROM first + 1 TO last DO value := item[i]; j := i - 1; # WHILE j >= LWB item AND j <= UPB item ANDF item[j] > value DO // example of ANDF extension # WHILE ( j >= LWB item AND j <= UPB item | item[j]>value | FALSE ) DO # no extension! # item[j + 1] := item[j]; j -:= 1 OD; item[j + 1] := value OD END # in place insertion sort #; [32]CHAR data := "big fjords vex quick waltz nymph"; [UPB data]DATA ref data; FOR i TO UPB data DO ref data[i] := data[i] OD; in place insertion sort(ref data); FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line); print((data))
Output:
abcdefghiijklmnopqrstuvwxyz big fjords vex quick waltz nymph
C
<lang c>#include <stdio.h>
void Isort(int a[], int size) {
int i, j, temp; for(i=1; i<=size-1; i++) { temp = a[i]; j = i-1; while(j>=0 && a[j] > temp) { a[j+1] = a[j]; j -= 1; } a[j+1] = temp; }
}
int main (int argc, char *argv[]) {
int intArray[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1}; int i, n; n = sizeof(intArray)/sizeof(intArray[0]); Isort(intArray, n); for(i=0; i<=n-1; i++) printf("%d ", intArray[i]);
}</lang>
Common Lisp
(defun span (predicate list)
(let ((tail (member-if-not predicate list)))
(values (ldiff list tail) tail)))
(defun less-than (x)
(lambda (y) (< y x)))
(defun insert (list elt)
(multiple-value-bind (left right) (span (less-than elt) list)
(append left (list elt) right)))
(defun insertion-sort (list)
(reduce #'insert list :initial-value nil))
D
import std.stdio: writefln;
void insertionSort(T)(T[] A) {
for(int i = 1; i < A.length; i++) {
T value = A[i];
int j = i - 1;
while (j >= 0 && A[j] > value) {
A[j + 1] = A[j];
j = j - 1;
}
A[j+1] = value;
}
}
void main() {
auto a1 = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1];
insertionSort(a1);
writefln(a1);
auto a2 = [4.0,65.0,2.0,-31.0,0.0,99.0,2.0,83.0,782.0,1.0];
insertionSort(a2);
writefln(a2);
}
Forth
: insert ( start end -- start ) dup @ >r ( r: v ) \ v = a[i] begin 2dup < \ j>0 while r@ over cell- @ < \ a[j-1] > v while cell- \ j-- dup @ over cell+ ! \ a[j] = a[j-1] repeat then r> swap ! ; \ a[j] = v : sort ( array len -- ) 1 ?do dup i cells + insert loop drop ; create test 7 , 3 , 0 , 2 , 9 , 1 , 6 , 8 , 4 , 5 , test 10 sort test 10 cells dump
Fortran
SUBROUTINE Insertion_Sort(a)
REAL, INTENT(in out), DIMENSION(:) :: a
REAL :: temp
INTEGER :: i, j
DO i = 2, SIZE(a)
j = i - 1
temp = a(i)
DO WHILE (j>=1 .AND. a(j)>temp)
a(j+1) = a(j)
j = j - 1
END DO
a(j+1) = temp
END DO
END SUBROUTINE Insertion_Sort
In Fortran 90 and above the intrinsic function CSHIFT can be used to shift the elements in the array but in practice is slower than the above example
DO i = 2, SIZE(a)
j = i - 1
DO WHILE (j>=1 .AND. a(j) > a(i))
j = j - 1
END DO
a(j+1:i) = cshift(a(j+1:i),-1)
END DO
Haskell
insert x [] = [x]
insert x (y:ys) | x <= y = x:y:ys
insert x (y:ys) | otherwise = y:(insert x ys)
insertionSort :: Ord a => [a] -> [a]
insertionSort = foldr insert []
-- Example use:
-- *Main> insertionSort [6,8,5,9,3,2,1,4,7]
-- [1,2,3,4,5,6,7,8,9]
Java
public static void insertSort(int[] A){
for(int i = 1; i < A.length; i++){
int value = A[i];
int j = i - 1;
while(j >= 0 && A[j] > value){
A[j + 1] = A[j];
j = j - 1;
}
A[j + 1] = value;
}
}
Modula-3
MODULE InsertSort;
PROCEDURE IntSort(VAR item: ARRAY OF INTEGER) =
VAR j, value: INTEGER;
BEGIN
FOR i := FIRST(item) + 1 TO LAST(item) DO
value := item[i];
j := i - 1;
WHILE j >= FIRST(item) AND item[j] > value DO
item[j + 1] := item[j];
DEC(j);
END;
item[j + 1] := value;
END;
END IntSort;
END InsertSort.
OCaml
let rec insert x = function
[] -> [x]
| y :: ys ->
if x <= y then x :: y :: ys
else y :: insert x ys
let insertion_sort lst = List.fold_right insert lst [];;
insertion_sort [6;8;5;9;3;2;1;4;7];;
Perl
sub insertion_sort {
$arr = shift;
for ($i = 0; $i <= $#{$arr}; $i++) {
$j = $i - 1;
$key = $arr->[$i];
while ($arr->[$j] > $key && $j >= 0) {
$arr->[$j + 1] = $arr->[$j];
$j -= 1;
}
$arr->[$j + 1] = $key;
}
}
$a = [4, 65, 2, -31, 0, 99, 83, 782, 1];
insertion_sort($a);
print join(' ', @{$a}), "\n";
Output:
-31 0 1 2 4 65 83 99 782
Prolog
insert_sort(L1,L2) :- insert_sort_intern(L1,[],L2). insert_sort_intern([],L,L). insert_sort_intern([H|T],L1,L) :- insert(L1,H,L2), insert_sort_intern(T,L2,L). insert([],X,[X]). insert([H|T],X,[X,H|T]) :- X =< H, !. insert([H|T],X,[H|T2]) :- insert(T,X,T2). % Example use: % ?- insert_sort([2,23,42,3,10,1,34,5],L). % L = [1,2,3,5,10,23,34,42] ? % yes
Python
def insertion_sort(l):
for i in xrange(1, len(l)):
j = i-1
key = l[i]
while (l[j] > key) and (j >= 0):
l[j+1] = l[j]
j -= 1
l[j+1] = key
Insertion sort with binary search
def insertion_sort_bin(seq):
for i in range(1, len(seq)):
key = seq[i]
# invariant: ``seq[:i]`` is sorted
# find the least `low' such that ``seq[low]`` is not less then `key'.
# Binary search in sorted sequence ``seq[low:up]``:
low, up = 0, i
while up > low:
middle = (low + up) // 2
if seq[middle] < key:
low = middle + 1
else:
up = middle
# insert key at position ``low``
seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]
Scheme
(define (insert x lst)
(if (null? lst)
(list x)
(let ((y (car lst))
(ys (cdr lst)))
(if (<= x y)
(cons x lst)
(cons y (insert x ys))))))
(define (insertion-sort lst)
(if (null? lst)
'()
(insert (car lst)
(insertion-sort (cdr lst)))))
(insertion-sort '(6 8 5 9 3 2 1 4 7))
UnixPipes
selectionsort() { read a test -n "$a" && ( selectionsort | sort -nm <(echo $a) -) }
cat to.sort | selectionsort