Sorting algorithms/Insertion sort: Difference between revisions
(moved REALbasic to BASIC; changed RB markup to VB; added QBasic) |
(Added Scala) |
||
Line 529: | Line 529: | ||
ary.insertionsort! |
ary.insertionsort! |
||
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang> |
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang> |
||
=={{header|Scala}}== |
|||
<lang scala>def insert(list: List[Int], value: Int) = list.span(_ < value) match { |
|||
case (lower, upper) => lower ::: value :: upper |
|||
} |
|||
def insertSort(list: List[Int]) = list.foldLeft(List[Int]())(insert)</lang> |
|||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
Revision as of 14:12, 10 November 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 consists of inserting one element at a time into the previously sorted part of the array, moving higher ranked elements up as necessary. To start off, the first (or smallest, or any arbitrary) element of the unsorted array is considered to be the sorted part.
Although insertion sort is an O(n2) algorithm, its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases (i) small n, (ii) as the final finishing-off algorithm for O(n logn) algorithms such as mergesort and quicksort.
The algorithm is as follows (from the wikipedia):
function insertionSort(array A) for i from 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 done A[j+1] = value done
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
AutoHotkey
contributed by Laszlo on the ahk forum <lang AutoHotkey>MsgBox % InsertionSort("") MsgBox % InsertionSort("xxx") MsgBox % InsertionSort("3,2,1") MsgBox % InsertionSort("dog,000000,xx,cat,pile,abcde,1,cat,zz,xx,z")
InsertionSort(var) { ; SORT COMMA SEPARATED LIST
StringSplit a, var, `, ; make array, size = a0 Loop % a0-1 { i := A_Index+1, v := a%i%, j := i-1 While j>0 and a%j%>v u := j+1, a%u% := a%j%, j-- u := j+1, a%u% := v } Loop % a0 ; construct string from sorted array sorted .= "," . a%A_Index% Return SubStr(sorted,2) ; drop leading comma
}</lang>
AWK
Sort standard input (storing lines into an array) and output to standard output <lang awk>{
line[NR] = $0
} END { # sort it with insertion sort
for(i=1; i <= NR; i++) { value = line[i] j = i - 1 while( ( j > 0) && ( line[j] > value ) ) { line[j+1] = line[j] j-- } line[j+1] = value } #print it for(i=1; i <= NR; i++) { print line[i] }
}</lang>
BASIC
This version (which is a translation of the REALbasic version immediately below) should work on any BASIC that can accept arrays as function arguments. <lang qbasic>DECLARE SUB InsertionSort (theList() AS INTEGER)
DIM n(10) AS INTEGER, L AS INTEGER, o AS STRING FOR L = 0 TO 10
n(L) = INT(RND * 32768)
NEXT InsertionSort n() FOR L = 1 TO 10
PRINT n(L); ";";
NEXT
SUB InsertionSort (theList() AS INTEGER)
DIM insertionElementIndex AS INTEGER FOR insertionElementIndex = 1 TO UBOUND(theList) DIM insertionElement AS INTEGER insertionElement = theList(insertionElementIndex) DIM j AS INTEGER j = insertionElementIndex - 1 DO WHILE (j >= 0) 'necessary for BASICs without short-circuit evaluation IF (insertionElement < theList(j)) THEN theList(j + 1) = theList(j) j = j - 1 ELSE EXIT DO END IF LOOP theList(j + 1) = insertionElement NEXT
END SUB</lang>
Sample output:
1486 ; 9488 ; 9894 ; 17479 ; 18989 ; 23119 ; 23233 ; 24927 ; 25386 ; 26689 ;
<lang vb> Sub InsertionSort(theList() as Integer)
for insertionElementIndex as Integer = 1 to UBound(theList) dim insertionElement as Integer = theList(insertionElementIndex) dim j as Integer = insertionElementIndex - 1 while (j >= 0) and (insertionElement < theList(j)) theList(j + 1) = theList(j) j = j - 1 wend theList(j + 1) = insertionElement next End Sub</lang>
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>
Clojure
Translated from the Haskell example: <lang lisp> (defn in-sort! [data]
(letfn [(insert ([raw x](insert [] raw x))
([sorted [y & raw] x] (if (nil? y) (conj sorted x) (if (<= x y ) (concat sorted [x,y] raw) (recur (conj sorted y) raw x )))))]
(reduce insert [] data)))
- Usage
- (in-sort! [6,8,5,9,3,2,1,4,7])
- Returns
- [1 2 3 4 5 6 7 8 9]
</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>
E
A direct conversion of the pseudocode.
<lang e>def insertionSort(array) {
for i in 1..!(array.size()) { def value := array[i] var j := i-1 while (j >= 0 && array[j] > value) { array[j + 1] := array[j] j -= 1 } array[j+1] := value }
}</lang>
Test case:
<lang e>? def a := [71, 53, 22, 24, 83, 54, 39, 78, 65, 26, 60, 75, 67, 27, 52, 59, 93, 62, 85, 99, 88, 10, 91, 85, 13, 17, 14, 96, 55, 10, 61, 94, 27, 50, 75, 40, 47, 63, 10, 23].diverge() > insertionSort(a) > a
- value: [10, 10, 10, 13, 14, 17, 22, 23, 24, 26, 27, 27, 39, 40, 47, 50, 52, 53, 54, 55, 59, 60, 61, 62, 63, 65, 67, 71, 75, 75, 78, 83, 85, 85, 88, 91, 93, 94, 96, 99].diverge()</lang>
Erlang
<lang Erlang> -module(sort). -export([insertion/1]).
insertion(L) -> lists:foldl(fun insert/2, [], L).
insert(X,[]) -> [X]; insert(X,L=[H|_]) when X =< H -> [X|L]; insert(X,[H|T]) -> [H|insert(X, T)]. </lang>
And the calls: <lang erlang> 1> c(sort). {ok,sort} 2> sort:insertion([5,3,9,4,1,6,8,2,7]). [1,2,3,4,5,6,7,8,9] </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>
J
Solution inspired by the Common LISP solution: <lang J>
isort=:((>: # ]) , [ , < #])/
</lang> Example of use: <lang J>
isort 32 4 1 34 95 3 2 120 _38
_38 1 2 3 4 32 34 95 120 </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
PL/I
<lang PL/I>
INSSORT: PROCEDURE (A,N); DCL (A(*)) FIXED BIN(31), N FIXED BIN(31) NONASGN; DCL (I,J,V) FIXED BIN(31); DO I=2 TO N; V=A(I); J=I-1; DO WHILE (J > 0 & A(J) > V); A(J+1)=A(J); J-=1; END; A(J+1)=V; END; RETURN; END INSSORT;
</lang>
Prolog
<lang 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).</lang> % 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>
R
Direct translation of pseudocode. <lang r> insertionsort <- function(x) {
for(i in 2:(length(x))) { value <- x[i] j <- i - 1 while(j >= 1 && x[j] > value) { x[j+1] <- x[j] j <- j-1 } x[j+1] <- value } x
} insertionsort(c(4, 65, 2, -31, 0, 99, 83, 782, 1)) # -31 0 1 2 4 65 83 99 782 </lang>
Ruby
<lang ruby>class Array
def insertionsort! 1.upto(length - 1) do |i| value = self[i] j = i - 1 while j >= 0 and self[j] > value self[j+1] = self[j] j -= 1 end self[j+1] = value end self end
end ary = [7,6,5,9,8,4,3,1,2,0] ary.insertionsort!
- => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang>
Scala
<lang scala>def insert(list: List[Int], value: Int) = list.span(_ < value) match {
case (lower, upper) => lower ::: value :: upper
} def insertSort(list: List[Int]) = list.foldLeft(List[Int]())(insert)</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>
Seed7
<lang seed7>const proc: insertionSort (inout array elemType: arr) is func
local var integer: i is 0; var integer: j is 0; var elemType: help is elemType.value; begin for i range 2 to length(arr) do j := i; help := arr[i]; while j > 1 and arr[pred(j)] > help do arr[j] := arr[pred(j)]; decr(j); end while; arr[j] := help; end for; end func;
</lang>
Original source: [1]
Standard ML
<lang sml>fun insertion_sort cmp = let
fun insert (x, []) = [x] | insert (x, y::ys) = case cmp (x, y) of GREATER => y :: insert (x, ys) | _ => x :: y :: ys
in
foldl insert []
end;
insertion_sort Int.compare [6,8,5,9,3,2,1,4,7];</lang>
Tcl
<lang tcl>package require Tcl 8.5
proc insertionsort {m} {
for {set i 1} {$i < [llength $m]} {incr i} { set val [lindex $m $i] set j [expr {$i - 1}] while {$j >= 0 && [lindex $m $j] > $val} { lset m [expr {$j + 1}] [lindex $m $j] incr j -1 } lset m [expr {$j + 1}] $val } return $m
}
puts [insertionsort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</lang>
UnixPipes
selectionsort() { read a test -n "$a" && ( selectionsort | sort -nm <(echo $a) -) }
cat to.sort | selectionsort
Ursala
<lang Ursala>
- import nat
insort = ~&i&& @hNCtX ~&r->lx ^\~&rt nleq-~rlrSPrhlPrSCPTlrShlPNCTPQ@rhPlD </lang> test program: <lang Ursala>
- cast %nL
example = insort <45,82,69,82,104,58,88,112,89,74> </lang> output:
<45,58,69,74,82,82,88,89,104,112>