Sorting algorithms/Insertion sort: Difference between revisions

{{trans|Python}}

L(i) 1 .< l.len

V j = i - 1

V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]

insertion_sort(&arr)

{{out}}

These programs use two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.

===Basic===

INSSORT CSECT

USING INSSORT,R13 base register

XDEC DS CL12 for xdeco

YREGS symbolics for registers

{{out}}

<pre>

===Assembler Structured Macros===

No harmful gotos [:)Dijkstra], no labels. It's cleaner, but is it clearer?

INSSORTS CSECT

USING INSSORTS,R13 base register

XDEC DS CL12 for xdeco

YREGS symbolics for registers

{{out}}

Same as previous

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program insertionSort64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

=={{header|ACL2}}==

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

((< x (first xs))

nil

(insert (first xs)

=={{header|Action!}}==

INT i

Test(c,8)

Test(d,12)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Insertion_sort.png Screenshot from Atari 8-bit computer]

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

=={{header|ALGOL W}}==

External in-place insertion sort routine for integers. From the pseudo code but with variable bounds.

% of an array parameter, the lower and upper bounds must be specified in lb and ub %

procedure insertionSortI ( integer array A ( * ); integer value lb, ub ) ;

end while_j_ge_0_and_Aj_gt_v ;

A( j + 1 ) := v

Test the insertionSortI procedure.

% external in-place insertion sort procedure %

procedure insertionSortI ( integer array A( * ); integer value lb, ub ) ;

write( i_w := 1, d( 1 ) );

for i := 2 until 8 do writeon( i_w := 1, d( i ) )

{{out}}

<pre>

=={{header|AppleScript}}==

on insertionSort(theList, l, r) -- Sort items l thru r of theList.

set listLength to (count theList)

set aList to {60, 73, 11, 66, 6, 77, 41, 97, 59, 45, 64, 15, 91, 100, 22, 89, 77, 59, 54, 61}

sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.

{{output}}

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program insertionSort.s */

bx lr @ leave function

iMagicNumber: .int 0xCCCCCCCD

=={{header|Arturo}}==

arr: new items

loop 1..(size items)-1 'i [

]

{{out}}

This implementation finds the position at which the element is to be inserted, and then uses '''array_subcirculate''' to move it into place. The prelude's implementation of '''array_subcirculate''' is a '''memmove(3)'''.

(*------------------------------------------------------------------*)

print! (" ", arr[i]);

println! ()

{{out}}

(The complications are necessary to prevent us accidentally having two copies of a linear value. Having two copies would introduce such nasty possibilities as a double-free error, use of a destroyed list, etc.)

(*------------------------------------------------------------------*)

array_uninitize<Strptr1> (arr, i2sz SIZE);

array_ptr_free (pf_arr, pfgc_arr | p_arr)

{{out}}

None of the activities in the following implementation requires allocating a new node. The original list is consumed. However, you can use this code to non-destructively sort a non-linear list by first creating a copy, casting the copy to a linear list, and sorting the copy, then casting the result to a non-linear list.

(*------------------------------------------------------------------*)

val () = list_vt_freelin lst

in

{{out}}

=={{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|Bash}}==

# Sorting integers with insertion sort

fi

{{out}}

=={{header|B4X}}==

The array type can be changed to Object and it will then work with any numeric type.

For i = 1 To A.Length - 1

Dim value As Int = A(i)

Next

End Sub

{{out}}

<pre>

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}}

Sorts N elements in array i() into ascending order. Invoke with GO SUB 500.

510 IF i(j)<=i(j+1) THEN NEXT j: RETURN

520 LET c=i(j+1)

530 FOR k=j TO 1 STEP -1: IF i(k)>c THEN LET i(k+1)=i(k): NEXT k

540 LET i(k+1)=c

For those who prefer GO TOs over conditional NEXTs (fine in ZX BASIC but problematic for compilers and stack-dependent interpreters like NextBASIC’s integer extensions) replace NEXT J: RETURN in line 510 with GO TO 600 and use this line 530:

==={{header|BBC BASIC}}===

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>

==={{header|Commodore BASIC}}===

10 DIM A(10): N=9

11 REM GENERATE SOME RANDOM NUMBERS AND PRINT THEM

32 RETURN

50 PRINT: FOR I=0 TO N: PRINTA(I): NEXT: RETURN

==={{header|IS-BASIC}}===

110 RANDOMIZE

120 NUMERIC ARRAY(5 TO 21)

340 LET A(I+1)=SW

350 NEXT

=={{header|BCPL}}==

let insertionSort(A, len) be

insertionSort(array, length)

write("After: ", array, length)

{{out}}

<pre>Before: 4 65 2 -31 0 99 2 83 782 1

=={{header|C}}==

void insertion_sort(int*, const size_t);

return 0;

}

{{out}}

<pre>

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

using System;

}

}

'''Example''':

using System;

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

}

=={{header|C++}}==

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.

#include <iostream>

#include <iterator>

std::cout << "\n";

{{out}}

<pre>

=={{header|Clojure}}==

(defn insertion-sort [coll]

(reduce (fn [result input]

[]

coll))

Translated from the Haskell example:

(defn in-sort! [data]

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

(reduce insert [] data)))

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

=={{header|CLU}}==

insertion_sort = proc [T: type] (a: array[T])

where T has lt: proctype (T,T) returns (bool)

insertion_sort[int](test)

stream$puts(po, "After: ") print_arr[int](test, 3, po)

{{out}}

<pre>Before: 7 -5 0 2 99 16 4 20 47 19

=={{header|CMake}}==

function(insertion_sort var)

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

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.

And a fully runnable version, by Steve Williams

{{works with|GnuCOBOL}}

>>SOURCE FORMAT FREE

*> This code is dedicated to the public domain

stop run

.

{{out}}

=={{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]

{{trans|Java}}

insertSort(List<int> array){

print('${a}');

}

{{out}}

<pre>array unsorted: [10, 3, 11, 15, 19, 1];

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|EasyLang}}==

for i = 1 to len data[] - 1

h = data[i]

data[] = [ 29 4 72 44 55 26 27 77 92 5 ]

call sort

=={{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|Elena}}==

ELENA 5.0 :

extension op

console.printLine("before:", list.asEnumerable());

console.printLine("after :", list.insertionSort().asEnumerable());

{{out}}

<pre>

=={{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}}==

"Return minimum or maximum of NUMBERS using COMPARATOR."

(let ((extremum (car numbers)))

nil))

{{out}}

=={{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#}}==

Procedural Version

// 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

Functional Version

let insertionSort collection =

| x::xs, ys -> xs |> isort (sinsert x ys)

collection |> isort []

=={{header|Factor}}==

{{trans|Haskell}}

: insertion-sort ( seq -- sorted-seq )

<reversed> V{ } clone [ swap insort-left! ] reduce ;

{{out}}

<pre>

=={{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}}

implicit none

integer :: n, i, j

a(j + 1) = x

end do

=== Alternate Fortran 77 version ===

IMPLICIT NONE

INTEGER N,I,J

20 A(J + 1) = X

30 CONTINUE

=={{header|FreeBASIC}}==

' compile with: fbc -s console

' for boundry checks on array's compile with: fbc -s console -exx

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>unsort -7 -1 4 -6 5 2 1 -2 0 -5 -4 6 -3 7 3

=={{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|Haxe}}==

@:generic

public static function sort<T>(arr:Array<T>) {

Sys.println('Sorted Strings: ' + stringArray);

}

{{out}}

=={{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|Isabelle}}==

imports Main

begin

unfolding rosettacode_haskell_insertionsort_def by(induction xs) simp+

{{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|Julia}}==

function insertionsort!(A::Array{T}) where T <: Number

x = randn(5)

{{out}}

=={{header|Kotlin}}==

for (index in 1 until array.size) {

val value = array[index]

insertionSort(numbers)

printArray("Sorted:", numbers)

{{out}}

=={{header|Ksh}}==

# An insertion sort in ksh

printf "%d " ${arr[i]}

done

{{out}}

=={{header|Lambdatalk}}==

{def sort

{sort {A}}

-> [-31,0,1,2,4,65,83,99,782]

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

dim A(itemCount)

for i = 1 to itemCount

next i

print

=={{header|Lua}}==

Binary variation of Insertion sort (Has better complexity)

local function lower_bound(container, container_begin, container_end, value, comparator)

local count = container_end - container_begin + 1

binary_insertion_sort_impl(container, comparator)

end

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

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

end

=={{header|Maple}}==

len := numelems(arr):

for i from 2 to len do

arr[j+1] := val:

end do:

{{Out|Output}}

<pre>[0,0,2,3,3,8,17,36,40,72]</pre>

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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

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

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

A

{{out}}

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

=={{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|N/t/roff}}==

===Sliding method===

..

.de array

.a.pushln 13 64 22 87 54 87 23 92 11 64 5 9 3 3 0

.insertionsort a

===Swapping method===

..

.de array

.a.pushln 13 64 22 87 54 87 23 92 11 64 5 9 3 3 0

.insertionsort a

=={{header|Nanoquery}}==

{{trans|Python}}

for i in range(1, len(L) - 1)

j = i - 1

return L

=={{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}}==

for i in 1 .. a.high:

let value = a[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

[] -> [x]

let insertion_sort = List.fold_left insert [];;

=={{header|Oforth}}==

Returns a new sorted list.