Sorting algorithms/Insertion sort: Difference between revisions
Line 1,851: | Line 1,851: | ||
=={{header|Rebol}}== |
=={{header|Rebol}}== |
||
<lang Rebol> |
<lang Rebol> |
||
; This program works with Rebol version R2 and R3, to make it work with Red |
|||
; change the word func to function |
|||
insertion-sort: func [ |
insertion-sort: func [ |
||
a [block!] |
a [block!] |
||
/local i [integer!] j [integer!] n [integer!] |
/local i [integer!] j [integer!] n [integer!] |
||
value [integer! string!] |
value [integer! string! date!] |
||
][ |
][ |
||
i: 2 |
i: 2 |
||
Line 1,875: | Line 1,877: | ||
probe insertion-sort [4 2 1 6 9 3 8 7] |
probe insertion-sort [4 2 1 6 9 3 8 7] |
||
probe insertion-sort [ "---Monday's Child Is Fair of Face (by Mother Goose)---" |
|||
"Monday's child is fair of face;" |
|||
"Tuesday's child is full of grace;" |
|||
"Wednesday's child is full of woe;" |
|||
"Thursday's child has far to go;" |
|||
"Friday's child is loving and giving;" |
|||
"Saturday's child works hard for a living;" |
|||
"But the child that is born on the Sabbath day" |
|||
"Is blithe and bonny, good and gay."] |
|||
; just by adding the date! type to the local variable value the same function can sort dates. |
|||
probe insertion-sort [12-Jan-2015 11-Jan-2015 11-Jan-2016 12-Jan-2014] |
|||
</lang> |
</lang> |
||
{{out}} |
|||
<pre> |
|||
[1 2 3 4 6 7 8 9] |
|||
[{---Monday's Child Is Fair of Face (by Mother Goose)---} |
|||
"But the child that is born on the Sabbath day" |
|||
"Friday's child is loving and giving;" |
|||
"Is blithe and bonny, good and gay." |
|||
"Monday's child is fair of face;" |
|||
"Saturday's child works hard for a living;" |
|||
"Thursday's child has far to go;" |
|||
"Tuesday's child is full of grace;" |
|||
"Wednesday's child is full of woe;" |
|||
] |
|||
[12-Jan-2014 11-Jan-2015 12-Jan-2015 11-Jan-2016] |
|||
</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
Revision as of 15:47, 27 January 2015
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
This page uses content from Wikipedia. The original article was at Insertion sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
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 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.
ACL2
<lang Lisp>(defun insert (x xs)
(cond ((endp xs) (list x)) ((< x (first xs)) (cons x xs)) (t (cons (first xs) (insert x (rest xs))))))
(defun isort (xs)
(if (endp xs) nil (insert (first xs) (isort (rest xs)))))</lang>
ActionScript
<lang ActionScript>function insertionSort(array:Array) { for(var i:int = 1; i < array.length;i++) { var value = array[i]; var j:int = i-1; while(j >= 0 && array[j] > value) { array[j+1] = array[j]; j--; } array[j+1] = value; } return array; }</lang>
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; Value : Integer; J : 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:
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 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>
- Output:
1486 ; 9488 ; 9894 ; 17479 ; 18989 ; 23119 ; 23233 ; 24927 ; 25386 ; 26689 ;
BBC BASIC
Note that the array index is assumed to start at zero. <lang bbcbasic> DIM test(9)
test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 PROCinsertionsort(test(), 10) FOR i% = 0 TO 9 PRINT test(i%) ; NEXT PRINT END DEF PROCinsertionsort(a(), n%) LOCAL i%, j%, t FOR i% = 1 TO n%-1 t = a(i%) j% = i% WHILE j%>0 AND t<a(ABS(j%-1)) a(j%) = a(j%-1) j% -= 1 ENDWHILE a(j%) = t NEXT ENDPROC</lang>
- Output:
-31 0 1 2 2 4 65 83 99 782
C
<lang c>#include <stddef.h>
static void insertion_sort(int *a, const size_t n) {
size_t i, j; int value; for (i = 1; i < n; i++) { value = a[i]; for (j = i; j > 0 && value < a[j - 1]; j--) { a[j] = a[j - 1]; } a[j] = value; }
}
int main(void) {
int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1}; insertion_sort(a, sizeof a / sizeof a[0]); return 0;
}</lang>
C++
Uses C++11. Compile with
g++ -std=c++11 insertion.cpp
Uses binary search via std::upper_bound() to find the insertion position in logarithmic time and then performs the insertion via std::rotate() in linear time. <lang cpp>#include <algorithm>
- include <iostream>
- include <iterator>
template <typename RandomAccessIterator, typename Predicate> void insertion_sort(RandomAccessIterator begin, RandomAccessIterator end,
Predicate p) { for (auto i = begin; i != end; ++i) { std::rotate(std::upper_bound(begin, i, *i, p), i, i + 1); }
}
template <typename RandomAccessIterator> void insertion_sort(RandomAccessIterator begin, RandomAccessIterator end) {
insertion_sort( begin, end, std::less< typename std::iterator_traits<RandomAccessIterator>::value_type>());
}
int main() {
int a[] = { 100, 2, 56, 200, -52, 3, 99, 33, 177, -199 }; insertion_sort(std::begin(a), std::end(a)); copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " ")); std::cout << "\n";
}</lang>
- Output:
-199 -52 2 3 33 56 99 100 177 200
C#
<lang csharp>namespace Sort {
using System;
static class InsertionSort<T> where T : IComparable { public static void Sort(T[] entries) { Sort(entries, 0, entries.Length - 1); }
public static void Sort(T[] entries, Int32 first, Int32 last) { for (var i = first + 1; i <= last; i++) { var entry = entries[i]; var j = i;
while (j > first && entries[j - 1].CompareTo(entry) > 0) entries[j] = entries[--j];
entries[j] = entry; } } }
}</lang> Example: <lang csharp> using Sort;
using System;
class Program { static void Main(String[] args) { var entries = new Int32[] { 3, 9, 4, 6, 8, 1, 7, 2, 5 }; InsertionSort<Int32>.Sort(entries); Console.WriteLine(String.Join(" ", entries)); } }</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>
CMake
<lang cmake># insertion_sort(var [value1 value2...]) sorts a list of integers. function(insertion_sort var)
math(EXPR last "${ARGC} - 1") # Sort ARGV[1..last]. foreach(i RANGE 2 ${last}) # Extend the sorted area to ARGV[1..i]. set(b ${i}) set(v ${ARGV${b}}) # Insert v == ARGV[b] in sorted order. While b > 1, check if b is # too high, then decrement b. After loop, set ARGV[b] = v. while(b GREATER 1) math(EXPR a "${b} - 1") set(u ${ARGV${a}}) # Now u == ARGV[a]. Pretend v == ARGV[b]. Compare. if(u GREATER ${v}) # ARGV[a] and ARGV[b] are in wrong order. Fix by moving ARGV[a] # to ARGV[b], making room for later insertion of v. set(ARGV${b} ${u}) else() break() endif() math(EXPR b "${b} - 1") endwhile() set(ARGV${b} ${v}) endforeach(i)
set(answer) foreach(i RANGE 1 ${last}) list(APPEND answer ${ARGV${i}}) endforeach(i) set("${var}" "${answer}" PARENT_SCOPE)
endfunction(insertion_sort)</lang>
<lang cmake>insertion_sort(result 33 11 44 22 66 55) message(STATUS "${result}") # -- 11;22;33;44;55;66</lang>
COBOL
This exerpt contains just enough of the procedure division to show the sort itself. The appropriate data division entries can be inferred. See also the entry for the Bubble sort for a full program. <lang COBOL> C-PROCESS SECTION.
PERFORM E-INSERTION VARYING WB-IX-1 FROM 1 BY 1 UNTIL WB-IX-1 > WC-SIZE.
...
E-INSERTION SECTION. E-000. MOVE WB-ENTRY(WB-IX-1) TO WC-TEMP. SET WB-IX-2 TO WB-IX-1.
PERFORM F-PASS UNTIL WB-IX-2 NOT > 1 OR WC-TEMP NOT < WB-ENTRY(WB-IX-2 - 1).
IF WB-IX-1 NOT = WB-IX-2 MOVE WC-TEMP TO WB-ENTRY(WB-IX-2).
E-999. EXIT.
F-PASS SECTION. F-000. MOVE WB-ENTRY(WB-IX-2 - 1) TO WB-ENTRY(WB-IX-2). SET WB-IX-2 DOWN BY 1.
F-999. EXIT.</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>
<lang lisp>(defun insertion-sort (sequence &optional (predicate #'<))
(if (cdr sequence) (insert (car sequence) ;; insert the current item into (insertion-sort (cdr sequence) ;; the already-sorted predicate) ;; remainder of the list predicate) sequence)) ; a list of one element is already sorted
(defun insert (item sequence predicate)
(cond ((null sequence) (list item)) ((funcall (complement predicate) ;; if the first element of the list (car sequence) ;; isn't better than the item, item) ;; cons the item onto (cons item sequence)) ;; the front of the list (t (cons (car sequence) ;; otherwise cons the first element onto the front of (insert item ;; the list of the item sorted with the rest of the list (cdr sequence) predicate)))))</lang>
D
<lang d>void insertionSort(T)(T[] data) pure nothrow @safe @nogc {
foreach (immutable i, value; data[1 .. $]) { auto j = i + 1; for ( ; j > 0 && value < data[j - 1]; j--) data[j] = data[j - 1]; data[j] = value; }
}
void main() {
import std.stdio; auto items = [28, 44, 46, 24, 19, 2, 17, 11, 25, 4]; items.insertionSort; items.writeln;
}</lang>
- Output:
[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]
Higher Level Version
<lang d>import std.stdio, std.range, std.algorithm, std.traits;
void insertionSort(R)(R arr) if (hasLength!R && isRandomAccessRange!R && hasSlicing!R) {
foreach (immutable i; 1 .. arr.length) bringToFront(arr[0 .. i].assumeSorted.upperBound(arr[i]), arr[i .. i + 1]);
}
void main() {
import std.random, std.container;
auto arr1 = [28, 44, 46, 24, 19, 2, 17, 11, 25, 4]; arr1.insertionSort; assert(arr1.isSorted); writeln("arr1 sorted: ", arr1);
auto arr2 = Array!int([28, 44, 46, 24, 19, 2, 17, 11, 25, 4]); arr2[].insertionSort; assert(arr2[].isSorted); writeln("arr2 sorted: ", arr2[]);
// Random data test. int[10] buf; foreach (immutable _; 0 .. 100_000) { auto arr3 = buf[0 .. uniform(0, $)]; foreach (ref x; arr3) x = uniform(-6, 6); arr3.insertionSort; assert(arr3.isSorted); }
}</lang>
- Output:
arr1 sorted: [2, 4, 11, 17, 19, 24, 25, 28, 44, 46] arr2 sorted: [2, 4, 11, 17, 19, 24, 25, 28, 44, 46]
Delphi
Array sort
Dynamic array is a 0-based array of variable length
Static array is an arbitrary-based array of fixed length <lang Delphi>program TestInsertionSort;
{$APPTYPE CONSOLE}
{.$DEFINE DYNARRAY} // remove '.' to compile with dynamic array
type
TItem = Integer; // declare ordinal type for array item
{$IFDEF DYNARRAY}
TArray = array of TItem; // dynamic array
{$ELSE}
TArray = array[0..15] of TItem; // static array
{$ENDIF}
procedure InsertionSort(var A: TArray); var
I, J: Integer; Item: TItem;
begin
for I:= 1 + Low(A) to High(A) do begin Item:= A[I]; J:= I - 1; while (J >= Low(A)) and (A[J] > Item) do begin A[J + 1]:= A[J]; Dec(J); end; A[J + 1]:= Item; end;
end;
var
A: TArray; I: Integer;
begin {$IFDEF DYNARRAY}
SetLength(A, 16);
{$ENDIF}
for I:= Low(A) to High(A) do A[I]:= Random(100); for I:= Low(A) to High(A) do Write(A[I]:3); Writeln; InsertionSort(A); for I:= Low(A) to High(A) do Write(A[I]:3); Writeln; Readln;
end.</lang>
- Output:
0 3 86 20 27 67 31 16 37 42 8 47 7 84 5 29 0 3 5 7 8 16 20 27 29 31 37 42 47 67 84 86
String sort
// string is 1-based variable-length array of Char <lang Delphi>procedure InsertionSort(var S: string); var
I, J, L: Integer; Ch: Char;
begin
L:= Length(S); for I:= 2 to L do begin Ch:= S[I]; J:= I - 1; while (J > 0) and (S[J] > Ch) do begin S[J + 1]:= S[J]; Dec(J); end; S[J + 1]:= Ch; end;
end;</lang>
// in : S = 'the quick brown fox jumps over the lazy dog' // out: S = ' abcdeeefghhijklmnoooopqrrsttuuvwxyz'
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>
Eiffel
This solution is shown in the routine sort
of the class MY_SORTED_SET
.
For a more complete explanation of the Eiffel sort examples, see the Bubble sort.
<lang eiffel>class
MY_SORTED_SET [G -> COMPARABLE]
inherit
TWO_WAY_SORTED_SET [G] redefine sort end
create
make
feature
sort -- Insertion sort local l_j: INTEGER l_value: like item do across 2 |..| count as ii loop from l_j := ii.item - 1 l_value := Current.i_th (ii.item) until l_j < 1 or Current.i_th (l_j) <= l_value loop Current.i_th (l_j + 1) := Current.i_th (l_j) l_j := l_j - 1 end Current.i_th (l_j + 1) := l_value end end
end</lang>
Emacs Lisp
<lang lisp>
(defun min-or-max-of-2-numbers (n1 n2 rel)
"n1 and n2 are two numbers, rel can be '< or '> according to
what sort of sorting is wanted, this function returns the greater or smaller number n1 or n2"
(cond ((eval (list rel n1 n2)) n1) (t n2)))
(defun min-or-max-of-a-list (lon rel)
"lon is a list of numbers, rel is '< or '>, this fonction
returns the higher or lower number of the list"
(if (cdr lon) (min-or-max-of-2-numbers (car lon)
(min-or-max-of-a-list (cdr lon) rel) rel)
(car lon)))
(defun remove-number-from-list (n lon)
"lon is a list of numbers, n is a number belonging to the list,
this function returns the same list but the number n. If n is present twice or more, it will be removed only once"
(if lon (cond ((= (car lon) n) (cdr lon)) (t (cons (car lon) (remove-number-from-list n (cdr lon))))) nil))
(defun sort-insertion (lon rel)
"lon is a list of numbers, rel can be '< or '>, this function
returns a list containing the same elements but which is sorted according to rel"
(if lon (cons (min-or-max-of-a-list lon rel)
(sort-insertion (remove-number-from-list (min-or-max-of-a-list lon rel) lon) rel))
nil))
- let's try it
(sort-insertion (list 1 2 3 9 8 7 25 12 3 2 1) '>)
</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>
Euphoria
<lang euphoria>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 compare(s[j],temp) > 0 do s[j+1] = s[j] j -= 1 end while s[j+1] = temp end for return s
end function
include misc.e constant s = {4, 15, "delta", 2, -31, 0, "alfa", 19, "gamma", 2, 13, "beta", 782, 1}
puts(1,"Before: ") pretty_print(1,s,{2}) puts(1,"\nAfter: ") pretty_print(1,insertion_sort(s),{2})</lang>
- Output:
Before: { 4, 15, "delta", 2, -31, 0, "alfa", 19, "gamma", 2, 13, "beta", 782, 1 } After: { -31, 0, 1, 2, 2, 4, 13, 15, 19, 782, "alfa", "beta", "delta", "gamma" }
F#
<lang fsharp> // This function performs an insertion sort with an array. // The input parameter is a generic array (any type that can perform comparison). // As is typical of functional programming style the input array is not modified; // a copy of the input array is made and modified and returned. let insertionSort (A: _ array) =
let B = Array.copy A for i = 1 to B.Length - 1 do let mutable value = B.[i] let mutable j = i - 1 while (j >= 0 && B.[j] > value) do B.[j+1] <- B.[j] j <- j - 1 B.[j+1] <- value B // the array B is returned
</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>PURE 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 ISO 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>
Alternate Fortran 77 version
<lang fortran> SUBROUTINE SORT(N,A)
IMPLICIT NONE INTEGER N,I,J DOUBLE PRECISION A(N),X DO 30 I=2,N X=A(I) J=I 10 J=J-1 IF(J.EQ.0 .OR. A(J).LE.X) GO TO 20 A(J+1)=A(J) GO TO 10 20 A(J+1)=X 30 CONTINUE END</lang>
GAP
<lang gap>InsertionSort := function(L)
local n, i, j, x; n := Length(L); for i in [ 2 .. n ] do x := L[i]; j := i - 1; while j >= 1 and L[j] > x do L[j + 1] := L[j]; j := j - 1; od; L[j + 1] := x; od;
end;
s := "BFKRIMPOQACNESWUTXDGLVZHYJ"; InsertionSort(s); s;
- "ABCDEFGHIJKLMNOPQRSTUVWXYZ"</lang>
Go
<lang go>package main
import "fmt"
func insertionSort(a []int) {
for i := 1; i < len(a); i++ { value := a[i] j := i - 1 for j >= 0 && a[j] > value { a[j+1] = a[j] j = j - 1 } a[j+1] = value }
}
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84} fmt.Println("unsorted:", list)
insertionSort(list) fmt.Println("sorted! ", list)
}</lang>
- Output:
unsorted: [31 41 59 26 53 58 97 93 23 84] sorted! [23 26 31 41 53 58 59 84 93 97]
A generic version that takes any container that conforms to sort.Interface
:
<lang go>package main
import (
"fmt" "sort"
)
func insertionSort(a sort.Interface) {
for i := 1; i < a.Len(); i++ { for j := i; j > 0 && a.Less(j, j-1); j-- { a.Swap(j-1, j) } }
}
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84} fmt.Println("unsorted:", list)
insertionSort(sort.IntSlice(list)) fmt.Println("sorted! ", list)
}</lang>
- Output:
unsorted: [31 41 59 26 53 58 97 93 23 84] sorted! [23 26 31 41 53 58 59 84 93 97]
Using binary search to locate the place to insert: <lang go>package main
import (
"fmt" "sort"
)
func insertionSort(a []int) {
for i := 1; i < len(a); i++ { value := a[i] j := sort.Search(i, func(k int) bool { return a[k] > value }) copy(a[j+1:i+1], a[j:i]) a[j] = value }
}
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84} fmt.Println("unsorted:", list)
insertionSort(list) fmt.Println("sorted! ", list)
}</lang>
- Output:
unsorted: [31 41 59 26 53 58 97 93 23 84] sorted! [23 26 31 41 53 58 59 84 93 97]
Groovy
Solution: <lang groovy>def insertionSort = { list ->
def size = list.size() (1..<size).each { i -> def value = list[i] def j = i - 1 for (; j >= 0 && list[j] > value; j--) { print "."; list[j+1] = list[j] } print "."; list[j+1] = value } list
}</lang>
Test: <lang groovy>println (insertionSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4])) println (insertionSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))</lang>
- Output:
..................................................................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99] ...............................................................................................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]
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>
HicEst
<lang hicest>DO i = 2, LEN(A)
value = A(i) j = i - 1 1 IF( j > 0 ) THEN IF( A(j) > value ) THEN A(j+1) = A(j) j = j - 1 GOTO 1 ! no WHILE in HicEst ENDIF ENDIF A(j+1) = value
ENDDO</lang>
Icon and Unicon
<lang Icon>procedure main() #: demonstrate various ways to sort a list and string
demosort(insertionsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
procedure insertionsort(X,op) #: return sorted X local i,temp
op := sortop(op,X) # select how and what we sort every i := 2 to *X do { temp := X[j := i] while op(temp,X[1 <= (j -:= 1)]) do X[j+1] := X[j] X[j+1] := temp } return X
end</lang>
Note: This example relies on the supporting procedures 'sortop', and 'demosort' in Bubble Sort. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.
- abbreviated:
Sorting Demo using procedure insertionsort on list : [ 3 14 1 5 9 2 6 3 ] with op = &null: [ 1 2 3 3 5 6 9 14 ] (0 ms) ... on string : "qwerty" with op = &null: "eqrtwy" (0 ms)
Io
<lang io> List do(
insertionSortInPlace := method( for(j, 1, size - 1, key := at(j) i := j - 1
while(i >= 0 and at(i) > key, atPut(i + 1, at(i)) i = i - 1 ) atPut(i + 1, key) ) )
)
lst := list(7, 6, 5, 9, 8, 4, 3, 1, 2, 0) lst insertionSortInPlace println # ==> list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)</lang>
A shorter, but slightly less efficient, version: <lang io>List do(
insertionSortInPlace := method( # In fact, we could've done slice(1, size - 1) foreach(...) # but creating a new list in memory can only make it worse. foreach(idx, key, newidx := slice(0, idx) map(x, x > key) indexOf(true) if(newidx, insertAt(removeAt(idx), newidx)) ) self)
)
lst := list(7, 6, 5, 9, 8, 4, 3, 1, 2, 0) lst insertionSortInPlace println # ==> list(0, 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>
Using some built-in algorithms (warning: not stable, due to the lack of an "upper bound" binary search function)
<lang java5>public static <E extends Comparable<? super E>> void insertionSort(List<E> a) {
for (int i = 1; i < a.size(); i++) { int j = Math.abs(Collections.binarySearch(a.subList(0, i), a.get(i)) + 1); Collections.rotate(a.subList(j, i+1), j - i); }
} public static <E extends Comparable<? super E>> void insertionSort(E[] a) {
for (int i = 1; i < a.length; i++) { E x = a[i]; int j = Math.abs(Arrays.binarySearch(a, 0, i, x) + 1); System.arraycopy(a, j, a, j+1, i-j); a[j] = x; }
}</lang>
JavaScript
<lang javascript> function insertionSort (a) {
for (var i = 0; i < a.length; i++) { var k = a[i]; for (var j = i; j > 0 && k < a[j - 1]; j--) a[j] = a[j - 1]; a[j] = k; } return a;
}
var a = [4, 65, 2, -31, 0, 99, 83, 782, 1]; insertionSort(a); document.write(a.join(" "));</lang>
jq
The insertion sort can be expressed directly in jq as follows: <lang jq>def insertion_sort:
reduce .[] as $x ([]; insert($x));</lang>where insert/1 inserts its argument into its input, which can, by construction, be assumed here to be sorted. This algorithm will work in jq for any JSON array.
The following solution uses an "industrial strength" implementation of bsearch (binary search) that requires the following control structure: <lang jq># As soon as "condition" is true, then emit . and stop: def do_until(condition; next):
def u: if condition then . else (next|u) end; u;</lang>
bsearch is the only non-trivial part of this solution, and so we include its complete specification:
Assuming the input array is sorted, bsearch/1 returns the index of the target if the target is in the input array; and otherwise (-1 - ix), where ix is the insertion point that would leave the array sorted.
If the input is not sorted, bsearch will terminate but with irrelevant results.<lang jq>def bsearch(target):
if length == 0 then -1 elif length == 1 then if target == .[0] then 0 elif target < .[0] then -1 else -2 end else . as $in # state variable: [start, end, answer] # where start and end are the upper and lower offsets to use. | [0, length-1, null] | do_until( .[0] > .[1] ; (if .[2] != null then (.[1] = -1) # i.e. break else ( ( (.[1] + .[0]) / 2 ) | floor ) as $mid | $in[$mid] as $monkey | if $monkey == target then (.[2] = $mid) # success elif .[0] == .[1] then (.[1] = -1) # failure elif $monkey < target then (.[0] = ($mid + 1)) else (.[1] = ($mid - 1)) end end )) | if .[2] == null then # compute the insertion point if $in[ .[0] ] < target then (-2 -.[0]) else (-1 -.[0]) end else .[2] end end;
- insert x assuming input is sorted
def insert(x):
if length == 0 then [x] else bsearch(x) as $i | ( if $i < 0 then -(1+$i) else $i end ) as $i | .[0:$i] + [x] + .[$i:] end ;
def insertion_sort:
reduce .[] as $x ([]; insert($x));</lang>
Example:<lang jq>[1, 2, 1, 1.1, -1.1, null, [null], {"null":null}] | insertion_sort</lang>
- Output:
[null,-1.1,1,1,1.1,2,[null],{"null":null}]
Liberty BASIC
<lang lb> itemCount = 20
dim A(itemCount) for i = 1 to itemCount A(i) = int(rnd(1) * 100) next i
print "Before Sort" gosub [printArray]
'--- Insertion sort algorithm
for i = 2 to itemCount value = A(i) j = i-1 while j >= 0 and A(j) > value A(j+1) = A(j) j = j-1 wend A(j+1) = value next
'--- end of (Insertion sort algorithm)
print "After Sort" gosub [printArray]
end
[printArray]
for i = 1 to itemCount print using("###", A(i)); next i print
return</lang>
Lua
<lang lua>function bins(tb, val, st, en)
local st, en = st or 1, en or #tb local mid = math.floor((st + en)/2) if en == st then return tb[st] > val and st or st+1 else return tb[mid] > val and bins(tb, val, st, mid) or bins(tb, val, mid+1, en) end
end function isort(t)
local ret = {t[1], t[2]} for i = 3, #t do table.insert(ret, bins(ret, t[i]), t[i]) end return ret
end
print(unpack(isort{4,5,2,7,8,3}))</lang>
Mathematica
<lang Mathematica>insertionSort[a_List] := Module[{A = a},
For[i = 2, i <= Length[A], i++, value = Ai; j = i - 1; While[j >= 1 && Aj > value, Aj + 1 = Aj; j--;]; Aj + 1 = value;];
A ]</lang>
insertionSort@{ 2, 1, 3, 5} {1, 2, 3, 5}
MATLAB / Octave
This is a direct translation of the pseudo-code above, except that it has been modified to compensate for MATLAB's 1 based arrays. <lang MATLAB>function list = insertionSort(list)
for i = (2:numel(list)) value = list(i); j = i - 1; while (j >= 1) && (list(j) > value) list(j+1) = list(j); j = j-1; end list(j+1) = value; end %for
end %insertionSort</lang>
Sample Usage: <lang MATLAB>>> insertionSort([4 3 1 5 6 2])
ans =
1 2 3 4 5 6</lang>
Maxima
<lang maxima>insertion_sort(u) := block(
[n: length(u), x, j], for i from 2 thru n do ( x: u[i], j: i - 1, while j >= 1 and u[j] > x do ( u[j + 1]: u[j], j: j - 1 ), u[j + 1]: x )
)$</lang>
MAXScript
<lang MAXScript> fn inSort arr = ( arr = deepcopy arr for i = 1 to arr.count do ( j = i while j > 1 and arr[j-1] > arr[j] do ( swap arr[j] arr[j-1] j -= 1 ) ) return arr ) </lang> Output: <lang MAXScript> b = for i in 1 to 20 collect random 1 40
- (2, 28, 35, 31, 27, 24, 2, 22, 15, 34, 9, 10, 22, 40, 26, 5, 23, 6, 18, 33)
a = insort b
- (2, 2, 5, 6, 9, 10, 15, 18, 22, 22, 23, 24, 26, 27, 28, 31, 33, 34, 35, 40)
</lang>
ML
mLite
<lang ocaml>fun insertion_sort L = let fun insert (x,[]) = [x] | (x, y :: ys) = if x <= y then x :: y :: ys else y :: insert (x, ys) in foldr (insert,[]) L end;
println ` insertion_sort [6,8,5,9,3,2,1,4,7]; </lang> Output
[1, 2, 3, 4, 5, 6, 7, 8, 9]
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>
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>
Nemerle
From the psuedocode. <lang Nemerle>using System.Console; using Nemerle.English;
module InsertSort {
public static Sort(this a : array[int]) : void { mutable value = 0; mutable j = 0; foreach (i in [1 .. (a.Length - 1)]) { value = a[i]; j = i - 1; while (j >= 0 and a[j] > value) { a[j + 1] = a[j]; j = j - 1; } a[j + 1] = value; } } Main() : void { def arr = array[1, 4, 8, 3, 8, 3, 5, 2, 6]; arr.Sort(); foreach (i in arr) Write($"$i "); }
}</lang>
NetRexx
<lang NetRexx>/* NetRexx */ options replace format comments java crossref savelog symbols binary
import java.util.List
placesList = [String -
"UK London", "US New York", "US Boston", "US Washington" - , "UK Washington", "US Birmingham", "UK Birmingham", "UK Boston" -
]
lists = [ -
placesList - , insertionSort(String[] Arrays.copyOf(placesList, placesList.length)) -
]
loop ln = 0 to lists.length - 1
cl = lists[ln] loop ct = 0 to cl.length - 1 say cl[ct] end ct say end ln
return
method insertionSort(A = String[]) public constant binary returns String[]
rl = String[A.length] al = List insertionSort(Arrays.asList(A)) al.toArray(rl)
return rl
method insertionSort(A = List) public constant binary returns ArrayList
loop i_ = 1 to A.size - 1 value = A.get(i_) j_ = i_ - 1 loop label j_ while j_ >= 0 if (Comparable A.get(j_)).compareTo(Comparable value) <= 0 then leave j_ A.set(j_ + 1, A.get(j_)) j_ = j_ - 1 end j_ A.set(j_ + 1, value) end i_
return ArrayList(A)
</lang>
- Output:
UK London US New York US Boston US Washington UK Washington US Birmingham UK Birmingham UK Boston UK Birmingham UK Boston UK London UK Washington US Birmingham US Boston US New York US Washington
Nim
<lang nim>proc insertSort[T](a: var openarray[T]) =
for i in 1 .. <a.len: let value = a[i] var j = i while j > 0 and value < a[j-1]: a[j] = a[j-1] dec j a[j] = value
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782] insertSort a echo a</lang>
- Output:
@[-31, 0, 2, 2, 4, 65, 83, 99, 782]
Objeck
<lang objeck> bundle Default {
class Insert { function : Main(args : String[]) ~ Nil { values := [9, 7, 10, 2, 9, 7, 4, 3, 10, 2, 7, 10]; InsertionSort(values); each(i : values) { values[i]->PrintLine(); }; } function : InsertionSort (a : Int[]) ~ Nil { each(i : a) { value := a[i]; j := i - 1; while(j >= 0 & a[j] > value) { a[j + 1] := a[j]; j -= 1; }; a[j + 1] := value; }; } }
} </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>
Qi
Based on the scheme version. <lang qi>(define insert
X [] -> [X] X [Y|Ys] -> [X Y|Ys] where (<= X Y) X [Y|Ys] -> [Y|(insert X Ys)])
(define insertion-sort
[] -> [] [X|Xs] -> (insert X (insertion-sort Xs)))
(insertion-sort [6 8 5 9 3 2 1 4 7]) </lang>
PARI/GP
<lang parigp>insertionSort(v)={
for(i=1,#v-1, my(j=i-1,x=v[i]); while(j && v[j]>x, v[j+1]=v[j]; j-- ); v[j+1]=x ); v
};</lang>
Pascal
See Delphi
Perl
<lang perl> sub insertion_sort {
my (@list) = @_; foreach my $i (1 .. $#list) { my $j = $i; my $k = $list[$i]; while ( $j > 0 && $k < $list[$j - 1]) { $list[$j] = $list[$j - 1]; $j--; } $list[$j] = $k; } return @list;
}
my @a = insertion_sort(4, 65, 2, -31, 0, 99, 83, 782, 1); print "@a\n"; </lang>
- Output:
-31 0 1 2 4 65 83 99 782
Perl 6
<lang perl6>sub insertion_sort ( @a is copy ) {
for 1 .. @a.end -> $i { my $value = @a[$i]; my $j; loop ( $j = $i-1; $j >= 0 and @a[$j] > $value; $j-- ) { @a[$j+1] = @a[$j]; } @a[$j+1] = $value; } return @a;
}
my @data = 22, 7, 2, -5, 8, 4; say 'input = ' ~ @data; say 'output = ' ~ @data.&insertion_sort; </lang>
- Output:
input = 22 7 2 -5 8 4 output = -5 2 4 7 8 22
PHP
<lang php>function insertionSort(&$arr){ for($i=0;$i<count($arr);$i++){ $val = $arr[$i]; $j = $i-1; while($j>=0 && $arr[$j] > $val){ $arr[$j+1] = $arr[$j]; $j--; } $arr[$j+1] = $val; } }
$arr = array(4,2,1,6,9,3,8,7); insertionSort($arr); echo implode(',',$arr);</lang>
1,2,3,4,6,7,8,9
PicoLisp
<lang PicoLisp>(de insertionSort (Lst)
(for (I (cdr Lst) I (cdr I)) (for (J Lst (n== J I) (cdr J)) (T (> (car J) (car I)) (rot J (offset I J)) ) ) ) Lst )</lang>
- Output:
: (insertionSort (5 3 1 7 4 1 1 20)) -> (1 1 1 3 4 5 7 20)
PL/I
<lang pli> INSSORT: PROCEDURE (A);
DCL A(*) FIXED BIN(31); DCL (I, J, V, N) FIXED BIN(31);
N = HBOUND(A,1); M = LBOUND(A,1); DO I=M+1 TO N; V=A(I); J=I-1; DO WHILE (J > M-1); if A(J) <= V then leave; A(J+1)=A(J); 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
Functional approach
Works with SWI-Prolog.
Insertion sort inserts elements of a list in a sorted list. So we can use foldl to sort a list.
<lang Prolog>% insertion sort
isort(L, LS) :-
foldl(insert, [], L, LS).
% foldl(Pred, Init, List, R).
foldl(_Pred, Val, [], Val).
foldl(Pred, Val, [H | T], Res) :-
call(Pred, Val, H, Val1),
foldl(Pred, Val1, T, Res).
% insertion in a sorted list insert([], N, [N]).
insert([H | T], N, [N, H|T]) :- N =< H, !.
insert([H | T], N, [H|L1]) :- insert(T, N, L1). </lang> Example use:
?- isort([2,23,42,3,10,1,34,5],L). L = [1,2,3,5,10,23,34,42]
PureBasic
<lang PureBasic>Procedure insertionSort(Array a(1))
Protected low, high Protected firstIndex, lastIndex = ArraySize(a()) If lastIndex > firstIndex + 1 low = firstIndex + 1 While low <= lastIndex high = low While high > firstIndex If a(high) < a(high - 1) Swap a(high), a(high - 1) Else Break EndIf high - 1 Wend low + 1 Wend EndIf
EndProcedure</lang>
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>
This is also built-in to the standard library:
<lang python>import bisect def insertion_sort_bin(seq):
for i in range(1, len(seq)): bisect.insort(seq, seq.pop(i), 0, i)</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>
R has native vectorized operations which allow the following, more efficient implementation.
<lang r> insertion_sort <- function(x) {
for (j in 2:length(x)) { key <- x[j] bp <- which.max(x[1:j] > key) # 'bp' stands for breakpoint if (bp == 1) { if (key < ar[1]){ x <- c(key, ar[-j]) } } else { x <- x[-j] x <- c(ar[1:bp - 1], key, x[bp : (s-1)]) } return(x) }
} </lang>
Racket
This implementation makes use of the pattern matching facilities in the Racket distribution.
<lang racket>
- lang racket
(define (sort < l)
(define (insert x y) (match* (x y) [(x '()) (list x)] [(x (cons y ys)) (cond [(< x y) (list* x y ys)] [else (cons y (insert x ys))])])) (foldl insert '() l))</lang>
Rascal
<lang rascal>import List;
public list[int] insertionSort(a){ for(i <- [0..size(a)-1]){ v = a[i]; j = i-1; while(j >= 0 && a[j] > v){ a[j+1] = a[j]; j -= 1;
}
a[j+1] = v;
}
return a; }</lang>
- Output:
<lang rascal>rascal>rascal>insertionSort([4, 65, 2, -31, 0, 99, 83, 782, 1]) list[int]: [-31,0,1,2,4,65,83,99,782]</lang>
REALbasic
<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>
Rebol
<lang Rebol>
- This program works with Rebol version R2 and R3, to make it work with Red
- change the word func to function
insertion-sort: func [ a [block!] /local i [integer!] j [integer!] n [integer!] value [integer! string! date!] ][ i: 2 n: length? a
while [i <= n][
value: a/:i
j: i while [ all [ 1 < j value < a/(j - 1) ]][
a/:j: a/(j - 1) j: j - 1
] a/:j: value
i: i + 1 ] a ]
probe insertion-sort [4 2 1 6 9 3 8 7]
probe insertion-sort [ "---Monday's Child Is Fair of Face (by Mother Goose)---"
"Monday's child is fair of face;" "Tuesday's child is full of grace;" "Wednesday's child is full of woe;" "Thursday's child has far to go;" "Friday's child is loving and giving;" "Saturday's child works hard for a living;" "But the child that is born on the Sabbath day" "Is blithe and bonny, good and gay."]
- just by adding the date! type to the local variable value the same function can sort dates.
probe insertion-sort [12-Jan-2015 11-Jan-2015 11-Jan-2016 12-Jan-2014] </lang>
- Output:
[1 2 3 4 6 7 8 9] [{---Monday's Child Is Fair of Face (by Mother Goose)---} "But the child that is born on the Sabbath day" "Friday's child is loving and giving;" "Is blithe and bonny, good and gay." "Monday's child is fair of face;" "Saturday's child works hard for a living;" "Thursday's child has far to go;" "Tuesday's child is full of grace;" "Wednesday's child is full of woe;" ] [12-Jan-2014 11-Jan-2015 12-Jan-2015 11-Jan-2016]
REXX
<lang rexx>/*REXX program sorts a stemmed array using the insertion-sort algoritm.*/ call gen@ /*generate the array's elements. */ call show@ 'before sort' /*show the before array elements.*/ call insertionSort # /*invoke the insertion sort. */ call show@ ' after sort' /*show the after array elements.*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────GEN@ subroutine─────────────────────*/ gen@: @. = /*assign default value to array. */
@.1 = "---Monday's Child Is Fair of Face (by Mother Goose)---" @.2 = "Monday's child is fair of face;" @.3 = "Tuesday's child is full of grace;" @.4 = "Wednesday's child is full of woe;" @.5 = "Thursday's child has far to go;" @.6 = "Friday's child is loving and giving;" @.7 = "Saturday's child works hard for a living;" @.8 = "But the child that is born on the Sabbath day" @.9 = "Is blithe and bonny, good and gay."
do #=1 while @.#\== /*find how many entries in array.*/ end /*#*/ /*short and sweet DO loop, eh? */
- =#-1 /*because of DO, adjust # entries*/
return /*──────────────────────────────────INSERTIONSORT subroutine────────────*/ insertionSort: procedure expose @. #
do i=2 to # value=@.i; do j=i-1 by -1 while j\==0 & @.j>value jp=j+1; @.jp=@.j end /*j*/ jp=j+1 @.jp=value end /*i*/
return /*──────────────────────────────────SHOW@ subroutine────────────────────*/ show@: do j=1 for #
say 'element' right(j,length(#)) arg(1)': ' @.j end /*j*/
say copies('─',79) /*show a separator line that fits*/ return</lang>
- Output:
element 1 before sort: ---Monday's Child Is Fair of Face (by Mother Goose)--- element 2 before sort: Monday's child is fair of face; element 3 before sort: Tuesday's child is full of grace; element 4 before sort: Wednesday's child is full of woe; element 5 before sort: Thursday's child has far to go; element 6 before sort: Friday's child is loving and giving; element 7 before sort: Saturday's child works hard for a living; element 8 before sort: But the child that is born on the Sabbath day element 9 before sort: Is blithe and bonny, good and gay. ─────────────────────────────────────────────────────────────────────────────── element 1 after sort: ---Monday's Child Is Fair of Face (by Mother Goose)--- element 2 after sort: But the child that is born on the Sabbath day element 3 after sort: Friday's child is loving and giving; element 4 after sort: Is blithe and bonny, good and gay. element 5 after sort: Monday's child is fair of face; element 6 after sort: Saturday's child works hard for a living; element 7 after sort: Thursday's child has far to go; element 8 after sort: Tuesday's child is full of grace; element 9 after sort: Wednesday's child is full of woe; ───────────────────────────────────────────────────────────────────────────────
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] p ary.insertionsort!
- => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang>
Alternative version which doesn't swap elements but rather removes and inserts the value at the correct place: <lang ruby>class Array
def insertionsort! 1.upto(length - 1) do |i| value = delete_at i j = i - 1 j -= 1 while j >= 0 && value < self[j] insert(j + 1, value) end self end
end
ary = [7,6,5,9,8,4,3,1,2,0] p ary.insertionsort!
- => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang>
Run BASIC
<lang runbasic>dim insSort(100) sortEnd = 0 global inSort global sortEnd
' -- insert some random numbers --
for i = 1 to 20
a = int(1000 * rnd(1)) x = insertSort(a)
next i
' --- Print the Sorted Data -----
print "End Sort:";sortEnd ' number sorted for i = 1 to sortEnd
print i;" ";insSort(i) ' location and sorted data
next i wait
function insertSort(x) ' Insert Sort Function i = 1 while x > insSort(i) and i <= sortEnd
i = i + 1
wend for j = sortEnd to i step -1
insSort(j + 1) = insSort(j)
next j insSort(i) = x sortEnd = sortEnd + 1 end function</lang>
End Sort:20 1 124 2 248 3 263 4 279 5 390 6 431 7 458 8 480 9 543 10 556 11 567 12 619 13 625 ........
Rust
<lang rust>fn insertion_sort<T: std::cmp::Ord>(arr: &mut [T]) {
for i in range(1, arr.len()) { let mut j = i; while (j > 0 && arr[j] < arr[j-1]) { arr.swap(j, j-1); j = j-1; } }
}</lang>
Scala
<lang scala>def insertSort[X](list: List[X])(implicit ord: Ordering[X]) = {
def insert(list: List[X], value: X) = list.span(x => ord.lt(x, value)) match { case (lower, upper) => lower ::: value :: upper } list.foldLeft(List.empty[X])(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]
Sidef
<lang ruby>class Array {
method insertion_sort { { |i| var j = i; var k = self[i]; while ((j > 0) && (k < self[j - 1])) { self[j] = self[j - 1]; j--; }; self[j] = k; } * self.offset; return self; }
}
var a = 10.of {100.rand.int}; say a.insertion_sort.dump;</lang>
SNOBOL4
<lang snobol>* read data into an array A = table() i = 0 readln A = trim(input) :s(readln) aSize = i - 1
- sort array
i = 1 loop1 value = A j = i - 1 loop2 gt(j,0) gt(A<j>,value) :f(done2) A<j + 1> = A<j> j = j - 1 :(loop2) done2 A<j + 1> = value i = ?lt(i,aSize) i + 1 :s(loop1) i = 1
- output sorted data
while output = A; i = ?lt(i,aSize) i + 1 :s(while) end</lang>
Swift
Using generics. <lang Swift>func insertionSort<T:Comparable>(inout list:[T]) {
for i in 1..<list.count { var j = i while j > 0 && list[j - 1] > list[j] { (list[j], list[j - 1]) = (list[j - 1], list[j]) j-- } }
}</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>
TI-83 BASIC
Input into L1, run prgmSORTINS, output in L2.
:"INSERTION" :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 :Return
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>
XPL0
<lang XPL0>code ChOut=8, IntOut=11;
proc InsertionSort(A, L); \Sort array A of length L int A, L; int I, J, V; [for I:= 1 to L-1 do
[V:= A(I); J:= I-1; while J>=0 and A(J)>V do [A(J+1):= A(J); J:= J-1; ]; A(J+1):= V; ];
];
int A, I; [A:= [3, 1, 4, 1, -5, 9, 2, 6, 5, 4]; InsertionSort(A, 10); for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )]; ]</lang>
- Output:
-5 1 1 2 3 4 4 5 6 9
Yorick
Based on pseudocode, except using 1-based arrays. <lang yorick>func insertionSort(&A) {
for(i = 2; i <= numberof(A); i++) { value = A(i); j = i - 1; while(j >= 1 && A(j) > value) { A(j+1) = A(j); j--; } A(j+1) = value; }
}</lang>
zkl
<lang zkl>fcn insertionSort(list){
sink:=List(); foreach x in (list){ if(False==(n:=sink.filter1n('>(x)))) sink.append(x); // x>all items in sink else sink.insert(n,x); } sink.close();
}</lang> <lang zkl>insertionSort(T(4,65,2,-31,0,99,2,83,782,1)).println(); insertionSort("big fjords vex quick waltz nymph".split()).println();</lang>
- Output:
L(-31,0,1,2,2,4,65,83,99,782) L("big","fjords","nymph","quick","vex","waltz")
- Programming Tasks
- Sorting Algorithms
- WikipediaSourced
- GUISS/Omit
- ACL2
- ActionScript
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- BASIC
- BBC BASIC
- C
- C++
- C sharp
- Clojure
- CMake
- COBOL
- Common Lisp
- D
- Delphi
- E
- E examples needing attention
- Examples needing attention
- Eiffel
- Emacs Lisp
- Erlang
- Euphoria
- F Sharp
- Forth
- Fortran
- GAP
- Go
- Groovy
- Haskell
- HicEst
- Icon
- Unicon
- Io
- J
- Java
- JavaScript
- Jq
- Liberty BASIC
- Lua
- Mathematica
- MATLAB
- Octave
- Maxima
- MAXScript
- ML
- MLite
- Standard ML
- Modula-3
- Nemerle
- NetRexx
- Nim
- Objeck
- OCaml
- Oz
- Qi
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- Prolog
- PureBasic
- Python
- R
- Racket
- Rascal
- REALbasic
- Rebol
- REXX
- Ruby
- Run BASIC
- Rust
- Scala
- Scheme
- Seed7
- Sidef
- SNOBOL4
- Swift
- TI-83 BASIC
- Tcl
- UnixPipes
- Ursala
- XPL0
- Yorick
- Zkl