Sorting algorithms/Insertion sort: Difference between revisions

{{task|Sorting Algorithms}}

{{Sorting Algorithm}}

{{wikipedia|Insertion sort}}

{{omit from|GUISS}}

An <span style="font-family: serif">[[O]](''n''²)</span> 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.

 

Although insertion sort is an <span style="font-family: serif">[[O]](''n''²)</span> algorithm, its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases: <br>

 

The algorithm is as follows (from [[wp:Insertion_sort#Algorithm|wikipedia]]):

 

Writing the algorithm for integers will suffice.

 

=={{header|ACL2}}==

(cond ((endp xs) (list x))

((< x (first xs))

nil

(insert (first xs)

 

=={{header|ActionScript}}==

{

for(var i:int = 1; i < array.length;i++)

}

return array;

 

=={{header|Ada}}==

procedure Insertion_Sort(Item : in out Data_Array) is

Item(J + 1) := Value;

end loop;

 

=={{header|ALGOL 68}}==

 

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}

 

PROC in place insertion sort = (REF[]DATA item)VOID:

in place insertion sort(ref data);

FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line);

{{out}}

<pre>

big fjords vex quick waltz nymph

</pre>

 

=={{header|AutoHotkey}}==

contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276481.html#276481 forum]

MsgBox % InsertionSort("xxx")

MsgBox % InsertionSort("3,2,1")

sorted .= "," . a%A_Index%

Return SubStr(sorted,2) ; drop leading comma

 

=={{header|AWK}}==

Sort standard input (storing lines into an array) and output to standard output

line[NR] = $0

}

print line[i]

}

 

=={{header|BASIC}}==

 

This version should work on any BASIC that can accept arrays as function arguments.

 

DIM n(10) AS INTEGER, L AS INTEGER, o AS STRING

theList(j + 1) = insertionElement

NEXT

 

{{out}}

</pre>

 

Note that the array index is assumed to start at zero.

test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

PROCinsertionsort(test(), 10)

a(j%) = t

NEXT

{{out}}

<pre>

-31 0 1 2 2 4 65 83 99 782

</pre>

 

=={{header|C}}==

 

}

 

int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};

insertion_sort(a, n);

return 0;

}

{{out}}

<pre>

4 65 2 -31 0 99 2 83 782 1

-31 0 1 2 2 4 65 83 99 782

</pre>

 

=={{header|C sharp|C#}}==

using System;

 

}

}

'''Example''':

using System;

 

Console.WriteLine(String.Join(" ", entries));

}

 

=={{header|Clojure}}==

Translated from the Haskell example:

(letfn [(insert ([raw x](insert [] raw x))

([sorted [y & raw] x]

(reduce insert [] data)))

;Usage:(in-sort! [6,8,5,9,3,2,1,4,7])

 

=={{header|CMake}}==

function(insertion_sort var)

math(EXPR last "${ARGC} - 1") # Sort ARGV[1..last].

# Extend the sorted area to ARGV[1..i].

set(b ${i})

endforeach(i)

set("${var}" "${answer}" PARENT_SCOPE)

 

 

=={{header|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.

PERFORM E-INSERTION VARYING WB-IX-1 FROM 1 BY 1

UNTIL WB-IX-1 > WC-SIZE.

 

F-999.

 

=={{header|Common Lisp}}==

(let ((tail (member-if-not predicate list)))

(values (ldiff list tail) tail)))

 

(defun insertion-sort (list)

 

(if (cdr sequence)

(insert (car sequence) ;; insert the current item into

(insert item ;; the list of the item sorted with the rest of the list

(cdr sequence)

 

=={{header|D}}==

foreach (immutable i, value; data[1 .. $]) {

auto j = i + 1;

items.insertionSort;

items.writeln;

{{out}}

<pre>[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]</pre>

===Higher Level Version===

{{trans|C++}}

 

void insertionSort(R)(R arr)

assert(arr3.isSorted);

}

{{out}}

<pre>arr1 sorted: [2, 4, 11, 17, 19, 24, 25, 28, 44, 46]

arr2 sorted: [2, 4, 11, 17, 19, 24, 25, 28, 44, 46]</pre>

 

=={{header|Delphi}}==

 

Static array is an arbitrary-based array of fixed length

 

{$APPTYPE CONSOLE}

Writeln;

Readln;

{{out}}

<pre>

===String sort===

// string is 1-based variable-length array of Char

var

I, J, L: Integer;

S[J + 1]:= Ch;

end;

<pre>

// in : S = 'the quick brown fox jumps over the lazy dog'

A direct conversion of the pseudocode.

 

for i in 1..!(array.size()) {

def value := array[i]

array[j+1] := value

}

 

Test case:

 

> insertionSort(a)

> a

 

=={{header|Eiffel}}==

For a more complete explanation of the Eiffel sort examples, see the [[Sorting algorithms/Bubble sort#Eiffel|Bubble sort]].

 

MY_SORTED_SET [G -> COMPARABLE]

inherit

end

 

 

=={{header|Elixir}}==

def insert_sort(list) when is_list(list), do: insert_sort(list, [])

defp insert(x, sorted) when x < hd(sorted), do: [x | sorted]

defp insert(x, [h | t]), do: [h | insert(x, t)]

 

Example:

 

=={{header|Emacs Lisp}}==

 

 

nil))

 

 

 

 

 

 

=={{header|Erlang}}==

-export([insertion/1]).

 

insert(X,[]) -> [X];

insert(X,L=[H|_]) when X =< H -> [X|L];

 

And the calls:

{ok,sort}

2> sort:insertion([5,3,9,4,1,6,8,2,7]).

 

=={{header|ERRE}}==

Note: array index is assumed to start at zero.

PROGRAM INSERTION_SORT

 

PRINT

END PROGRAM

{{out}}

<pre>

 

=={{header|Euphoria}}==

object temp

integer j

pretty_print(1,s,{2})

puts(1,"\nAfter: ")

 

{{out}}

 

=={{header|F Sharp|F#}}==

// This function performs an insertion sort with an array.

// The input parameter is a generic array (any type that can perform comparison).

B.[j+1] <- value

B // the array B is returned

 

=={{header|Forth}}==

dup @ >r ( r: v ) \ v = a[i]

begin

create test 7 , 3 , 0 , 2 , 9 , 1 , 6 , 8 , 4 , 5 ,

test 10 sort

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

 

=== Alternate Fortran 77 version ===

IMPLICIT NONE

INTEGER N,I,J

DOUBLE PRECISION A(N),X

30 CONTINUE

 

=={{header|GAP}}==

local n, i, j, x;

n := Length(L);

InsertionSort(s);

s;

=={{header|Go}}==

 

import "fmt"

insertionSort(list)

fmt.Println("sorted! ", list)

{{out}}

<pre>

 

A generic version that takes any container that conforms to <code>sort.Interface</code>:

 

import (

insertionSort(sort.IntSlice(list))

fmt.Println("sorted! ", list)

{{out}}

<pre>

 

Using binary search to locate the place to insert:

 

import (

insertionSort(list)

fmt.Println("sorted! ", list)

{{out}}

<pre>

=={{header|Groovy}}==

Solution:

def size = list.size()

}

list

 

Test:

 

{{out}}

 

=={{header|Haskell}}==

 

insertionSort :: Ord a => [a] -> [a]

-- Example use:

-- *Main> insertionSort [6,8,5,9,3,2,1,4,7]

 

=={{header|HicEst}}==

value = A(i)

j = i - 1

ENDIF

A(j+1) = value

 

=={{header|Icon}} and {{header|Unicon}}==

demosort(insertionsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")

end

}

return X

 

Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| 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.

=={{header|Io}}==

 

List do(

insertionSortInPlace := method(

 

lst := list(7, 6, 5, 9, 8, 4, 3, 1, 2, 0)

 

A shorter, but slightly less efficient, version:

insertionSortInPlace := method(

# In fact, we could've done slice(1, size - 1) foreach(...)

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)

 

=={{header|J}}==

{{eff note|J|/:~}}

Solution inspired by the Common LISP solution:

Example of use:

 

=={{header|Java}}==

for(int i = 1; i < A.length; i++){

int value = A[i];

A[j + 1] = value;

}

 

Using some built-in algorithms (warning: not stable, due to the lack of an "upper bound" binary search function)

{{trans|C++}}

for (int i = 1; i < a.size(); i++) {

int j = Math.abs(Collections.binarySearch(a.subList(0, i), a.get(i)) + 1);

a[j] = x;

}

 

=={{header|JavaScript}}==

function insertionSort (a) {

for (var i = 0; i < a.length; i++) {

var a = [4, 65, 2, -31, 0, 99, 83, 782, 1];

insertionSort(a);

 

=={{header|jq}}==

{{works with|jq|1.4}}

The insertion sort can be expressed directly in jq as follows:

 

The following solution uses an "industrial strength" implementation of bsearch (binary search) that requires the following control structure:

def do_until(condition; next):

def u: if condition then . else (next|u) end;

 

bsearch is the only non-trivial part of this solution, and so we include

(-1 - ix), where ix is the insertion point that would leave the array sorted.

 

if length == 0 then -1

elif length == 1 then

 

def insertion_sort:

{{Out}}

[null,-1.1,1,1,1.1,2,[null],{"null":null}]

 

=={{header|Liberty BASIC}}==

dim A(itemCount)

for i = 1 to itemCount

next i

print

 

=={{header|Lua}}==

 

local st, en = st or 1, en or #tb

local mid = math.floor((st + en)/2)

end

 

 

For[i = 2, i <= Length[A], i++,

value = A[[i]]; j = i - 1;

A[[j + 1]] = value;];

A

<pre>insertionSort@{ 2, 1, 3, 5}

{1, 2, 3, 5}</pre>

=={{header|MATLAB}} / {{header|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.

 

for i = (2:numel(list))

end %for

 

Sample Usage:

 

ans =

 

 

=={{header|Maxima}}==

[n: length(u), x, j],

for i from 2 thru n do (

u[j + 1]: x

)

 

=={{header|MAXScript}}==

fn inSort arr =

(

return arr

)

Output:

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)

 

=={{header|ML}}==

==={{header|mLite}}===

{{trans|OCaml}}

let

fun insert

 

println ` insertion_sort [6,8,5,9,3,2,1,4,7];

Output

<pre>

 

==={{header|Standard ML}}===

fun insert (x, []) = [x]

| insert (x, y::ys) =

end;

 

 

=={{header|Modula-3}}==

{{trans|Ada}}

 

PROCEDURE IntSort(VAR item: ARRAY OF INTEGER) =

END;

END IntSort;

 

=={{header|Nemerle}}==

From the psuedocode.

using Nemerle.English;

 

foreach (i in arr) Write($"$i ");

}

 

=={{header|NetRexx}}==

options replace format comments java crossref savelog symbols binary

 

 

return ArrayList(A)

{{out}}

<pre>

 

=={{header|Nim}}==

let value = a[i]

var j = i

var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]

insertSort a

{{out}}

<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>

 

=={{header|Objeck}}==

bundle Default {

class Insert {

}

}

 

=={{header|OCaml}}==

match lst with

 

 

 

=={{header|Oforth}}==

Returns a new sorted list.

 

| l i j v |

2 l size for: i [

l at(i) ->v

while(j) [

l at(j) dup v <= ifTrue: [ drop break ]

]

l put(j 1 +, v)

]

 

{{out}}

>

</pre>

 

=={{header|Oz}}==

Direct translation of pseudocode. In-place sorting of mutable arrays.

proc {InsertionSort A}

Low = {Array.low A}

in

{InsertionSort Arr}

 

=={{header|PARI/GP}}==

for(i=1,#v-1,

my(j=i-1,x=v[i]);

);

v

 

=={{header|Pascal}}==

 

=={{header|Perl}}==

sub insertion_sort {

my (@list) = @_;

my @a = insertion_sort(4, 65, 2, -31, 0, 99, 83, 782, 1);

print "@a\n";

{{out}}

-31 0 1 2 4 65 83 99 782

 

{{out}}

</pre>

 

=={{header|PHP}}==

for($i=0;$i<count($arr);$i++){

$val = $arr[$i];

$arr = array(4,2,1,6,9,3,8,7);

insertionSort($arr);

<pre>1,2,3,4,6,7,8,9</pre>

 

=={{header|PicoLisp}}==

(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)) ) ) )

{{out}}

<pre>: (insertionSort (5 3 1 7 4 1 1 20))

 

=={{header|PL/I}}==

 

 

=={{header|PowerShell}}==

Very similar to the PHP code.

for($i=0;$i -lt $arr.length;$i++){

$val = $arr[$i]

$arr = @(4,2,1,6,9,3,8,7)

insertionSort($arr)

{{Out}}

<pre>1,2,3,4,6,7,8,9</pre>

 

=={{header|Prolog}}==

insert_sort_intern(L1,[],L2).

!.

insert([H|T],X,[H|T2]) :-

% Example use:

Works with SWI-Prolog.<br>

Insertion sort inserts elements of a list in a sorted list. So we can use foldl to sort a list.

isort(L, LS) :-

foldl(insert, [], L, LS).

insert([H | T], N, [H|L1]) :-

insert(T, N, L1).

Example use:

<pre> ?- isort([2,23,42,3,10,1,34,5],L).

 

=={{header|PureBasic}}==

Protected low, high

Protected firstIndex, lastIndex = ArraySize(a())

Wend

EndIf

 

=={{header|Python}}==

j = i-1

j -= 1

===Insertion sort with binary search===

for i in range(1, len(seq)):

key = seq[i]

up = middle

# insert key at position ``low``

 

This is also built-in to the standard library:

 

def insertion_sort_bin(seq):

for i in range(1, len(seq)):

 

=={{header|R}}==

Direct translation of pseudocode.

{

for(i in 2:(length(x)))

x

}

 

R has native vectorized operations which allow the following, more efficient implementation.

 

insertion_sort <- function(x) {

for (j in 2:length(x)) {

}

}

 

=={{header|Racket}}==

This implementation makes use of the pattern matching facilities in the Racket distribution.

 

#lang racket

 

(define (sort < l)

 

=={{header|Rascal}}==

 

public list[int] insertionSort(a){

}

return a;

{{out}}

 

=={{header|REALbasic}}==

for insertionElementIndex as Integer = 1 to UBound(theList)

dim insertionElement as Integer = theList(insertionElementIndex)

theList(j + 1) = insertionElement

next

 

; change the word func to function

insertion-sort: func [

; 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]

 

{{out}}

[12-Jan-2014 11-Jan-2015 12-Jan-2015 11-Jan-2016]

</pre>

 

=={{header|REXX}}==