Sorting algorithms/Insertion sort: Difference between revisions
(→{{header|TI-83 BASIC}}: Added ti83b) |
(→{{header|E}}: {{Lines_too_long}}) |
||
| Line 246: | Line 246: | ||
}</lang> |
}</lang> |
||
=={{header|E}}== |
=={{header|E}}== |
||
{{Lines_too_long}} |
|||
A direct conversion of the pseudocode. |
A direct conversion of the pseudocode. |
||
Revision as of 22:20, 29 January 2010
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
<lang algol68>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))</lang> Output: <lang algol68>abcdefghiijklmnopqrstuvwxyz big fjords vex quick waltz nymph</lang>
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
<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</lang>
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>import Data.List (insert)
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>
Oz
Direct translation of pseudocode. In-place sorting of mutable arrays. <lang oz>declare
proc {InsertionSort A}
Low = {Array.low A}
High = {Array.high A}
in
for I in Low+1..High do
Value = A.I
J = {NewCell I-1}
in
for while:@J >= Low andthen A.@J > Value do
A.(@J+1) := A.@J
J := @J - 1
end
A.(@J+1) := Value
end
end
Arr = {Tuple.toArray unit(3 1 4 1 5 9 2 6 5)}
in
{InsertionSort Arr}
{Show {Array.toRecord unit Arr}}</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 pli>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>
TI-83 BASIC
Store input in L1, run prgmSORTINS, get output in L2.
:L1→L2 :0→A :Lbl L :A+1→A :A→B :While B>0 :If L2(B)<L2(B+1) :Goto B :L2(B)→C :L2(B+1)→L2(B) :C→L2(B+1) :B-1→B :End :Lbl B :If A<(dim(L2)-1) :Goto L :DelVar A :DelVar B :DelVar C :Stop
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
<lang bash>selectionsort() {
read a test -n "$a" && ( selectionsort | sort -nm <(echo $a) -)
}</lang> <lang bash>cat to.sort | selectionsort</lang>
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>