Sorting algorithms/Insertion sort: Difference between revisions
m Links, formatting, more code -> lang changes |
|||
Line 225: | Line 225: | ||
=={{header|Modula-3}}== |
=={{header|Modula-3}}== |
||
{{trans|Ada}} |
{{trans|Ada}} |
||
<lang modula3> |
<lang modula3>MODULE InsertSort; |
||
MODULE InsertSort; |
|||
PROCEDURE IntSort(VAR item: ARRAY OF INTEGER) = |
PROCEDURE IntSort(VAR item: ARRAY OF INTEGER) = |
||
Line 241: | Line 240: | ||
END; |
END; |
||
END IntSort; |
END IntSort; |
||
END InsertSort. |
END InsertSort.</lang> |
||
</lang> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
Revision as of 00:09, 1 March 2009
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(n2) 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
<lang 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; </lang>
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
<lang 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))
</lang>
D
<lang 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);
} </lang>
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
<lang 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 </lang> 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 <lang fortran> 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 </lang>
Haskell
<lang 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] </lang>
Java
<lang java5> 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; }
} </lang>
Modula-3
<lang modula3>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.</lang>
OCaml
<lang 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];;</lang>
Perl
<lang 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"; </lang> 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
<lang 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
</lang>
Insertion sort with binary search
<lang python> 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:]
</lang>
Scheme
<lang 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))</lang>
UnixPipes
selectionsort() { read a test -n "$a" && ( selectionsort | sort -nm <(echo $a) -) }
cat to.sort | selectionsort