Sorting algorithms/Insertion sort: Difference between revisions
m
→{{header|Binary Lambda Calculus}}
No edit summary |
|||
(106 intermediate revisions by 51 users not shown) | |||
Line 1:
{{task|Sorting Algorithms}}
{{Sorting Algorithm}}
[[Category:Sorting]]
{{wikipedia|Insertion sort}}
{{omit from|GUISS}}
Line 10 ⟶ 11:
Although insertion sort is an <span style="font-family: serif">[[O]](''n''<sup>2</sup>)</span> algorithm, its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases: <br>
:# as the final finishing-off algorithm for <span style="font-family: serif">[[O]](''n'' log''n'')</span> algorithms such as [[Merge sort|mergesort]] and [[quicksort]].
The algorithm is as follows (from [[wp:Insertion_sort#Algorithm|wikipedia]]):
Line 27 ⟶ 30:
Writing the algorithm for integers will suffice.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F insertion_sort(&l)
L(i) 1 .< l.len
V j = i - 1
V key = l[i]
L j >= 0 & l[j] > key
l[j + 1] = l[j]
j--
l[j + 1] = key
V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
insertion_sort(&arr)
print(arr)</syntaxhighlight>
{{out}}
<pre>
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
</pre>
=={{header|360 Assembly}}==
Line 32 ⟶ 56:
These programs use two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.
===Basic===
<
INSSORT CSECT
USING INSSORT,R13 base register
Line 88 ⟶ 112:
XDEC DS CL12 for xdeco
YREGS symbolics for registers
END INSSORT</
{{out}}
<pre>
Line 96 ⟶ 120:
===Assembler Structured Macros===
No harmful gotos [:)Dijkstra], no labels. It's cleaner, but is it clearer?
<
INSSORTS CSECT
USING INSSORTS,R13 base register
Line 148 ⟶ 172:
XDEC DS CL12 for xdeco
YREGS symbolics for registers
END INSSORTS</
{{out}}
Same as previous
=={{header|AArch64 Assembly}}==
<syntaxhighlight lang="asm">
.section .text
.globl insertion_sort
// C equivalent at bottom
/* void insertion_sort(int *arr, size_t len);
* X0: pointer to &a[0]
* X1: index of one past the last element of arr
* Preconditions:
* - Arg 1 (X0) is not a null pointer
* - Arg 2 (X1) is not zero
*/
#define ARR_BEGIN x0
#define ARR_END x2
#define I x3
#define J x4
#define OUTER_TMP w6
#define INNER_TMP w5
insertion_sort:
add ARR_END, ARR_BEGIN, x1, LSL #2
add I, ARR_BEGIN, #4
b 2f
// goto test;
// do {
0:
ldr OUTER_TMP, [I] // OUTER_TMP = *I;
// int INNER_TMP, *J;
// for (J = I; J != &arr[0] && (INNER_TMP = J[-1]) > OUTER_TMP; J--)
// *J = INNER_TMP;
mov J, I
b 3f
1:
// Loop body
str INNER_TMP, [J], #-4
3:
// Loop test
cmp J, ARR_BEGIN
b.eq 1f
ldr INNER_TMP, [J, #-4]
cmp INNER_TMP, OUTER_TMP
b.gt 1b
1:
str OUTER_TMP, [J] // *J = OUTER_TMP
add I, I, #4
// test:; } while (I < &arr[len]);
2:
cmp I, ARR_END
b.lo 0b
ret
/*
// First I wrote this C code, then I hand-compiled it to the above assembly.
void insertion_sort(int arr[], size_t len) {
int x, *pi, *pj;
for (pi = &a[1]; pi != &arr[len]; pi++) {
x = *pi;
for (pj = pi; pj != &a[0] && pj[-1] > x; pj--)
*pj = pj[-1];
*pj = x;
}
}
*/
</syntaxhighlight>{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program insertionSort64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
sMessResult: .asciz "Value : @ \n"
szCarriageReturn: .asciz "\n"
.align 4
#TableNumber: .quad 1,3,6,2,5,9,10,8,4,7
TableNumber: .quad 10,9,8,7,6,-5,4,3,2,1
.equ NBELEMENTS, (. - TableNumber) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrTableNumber // address number table
mov x1,0 // first element
mov x2,NBELEMENTS // number of élements
bl insertionSort
ldr x0,qAdrTableNumber // address number table
bl displayTable
ldr x0,qAdrTableNumber // address number table
mov x1,NBELEMENTS // number of élements
bl isSorted // control sort
cmp x0,1 // sorted ?
beq 1f
ldr x0,qAdrszMessSortNok // no !! error sort
bl affichageMess
b 100f
1: // yes
ldr x0,qAdrszMessSortOk
bl affichageMess
100: // standard end of the program
mov x0,0 // return code
mov x8,EXIT // request to exit program
svc 0 // perform the system call
qAdrsZoneConv: .quad sZoneConv
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsMessResult: .quad sMessResult
qAdrTableNumber: .quad TableNumber
qAdrszMessSortOk: .quad szMessSortOk
qAdrszMessSortNok: .quad szMessSortNok
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements > 0 */
/* x0 return 0 if not sorted 1 if sorted */
isSorted:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
mov x2,0
ldr x4,[x0,x2,lsl 3]
1:
add x2,x2,1
cmp x2,x1
bge 99f
ldr x3,[x0,x2, lsl 3]
cmp x3,x4
blt 98f
mov x4,x3
b 1b
98:
mov x0,0 // not sorted
b 100f
99:
mov x0,1 // sorted
100:
ldp x3,x4,[sp],16 // restaur 2 registers
ldp x2,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* insertion sort */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the first element */
/* x2 contains the number of element */
insertionSort:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
add x3,x1,1 // index i
1: // start loop 1
ldr x4,[x0,x3,lsl 3] // load value A[i]
sub x5,x3,1 // index j
2: // start loop 2
ldr x6,[x0,x5,lsl 3] // load value A[j]
cmp x6,x4 // compare value
ble 3f
add x5,x5,1 // increment index j
str x6,[x0,x5,lsl 3] // store value A[j+1}
sub x5,x5,2 // j = j - 1
cmp x5,x1 // compare first element
bge 2b // loop 2
3:
add x5,x5,1 // increment index j
str x4,[x0,x5,lsl 3] // store value A[i}
add x3,x3,1 // increment index i
cmp x3,x2 // end ?
blt 1b // loop 1
100:
ldp x6,x7,[sp],16 // restaur 2 registers
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* x0 contains the address of table */
displayTable:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
mov x2,x0 // table address
mov x3,0
1: // loop display table
ldr x0,[x2,x3,lsl 3]
ldr x1,qAdrsZoneConv
bl conversion10S // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
add x3,x3,1
cmp x3,NBELEMENTS - 1
ble 1b
ldr x0,qAdrszCarriageReturn
bl affichageMess
mov x0,x2
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ACL2}}==
<
(cond ((endp xs) (list x))
((< x (first xs))
Line 164 ⟶ 417:
nil
(insert (first xs)
(isort (rest xs)))))</
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT size)
INT i
Put('[)
FOR i=0 TO size-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
PROC InsertionSort(INT ARRAY a INT size)
INT i,j,value
FOR i=1 TO size-1
DO
value=a(i)
j=i-1
WHILE j>=0 AND a(j)>value
DO
a(j+1)=a(j)
j==-1
OD
a(j+1)=value
OD
RETURN
PROC Test(INT ARRAY a INT size)
PrintE("Array before sort:")
PrintArray(a,size)
InsertionSort(a,size)
PrintE("Array after sort:")
PrintArray(a,size)
PutE()
RETURN
PROC Main()
INT ARRAY
a(10)=[1 4 65535 0 3 7 4 8 20 65530],
b(21)=[10 9 8 7 6 5 4 3 2 1 0
65535 65534 65533 65532 65531
65530 65529 65528 65527 65526],
c(8)=[101 102 103 104 105 106 107 108],
d(12)=[1 65535 1 65535 1 65535 1
65535 1 65535 1 65535]
Test(a,10)
Test(b,21)
Test(c,8)
Test(d,12)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Insertion_sort.png Screenshot from Atari 8-bit computer]
<pre>
Array before sort:
[1 4 -1 0 3 7 4 8 20 -6]
Array after sort:
[-6 -1 0 1 3 4 4 7 8 20]
Array before sort:
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10]
Array after sort:
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10]
Array before sort:
[101 102 103 104 105 106 107 108]
Array after sort:
[101 102 103 104 105 106 107 108]
Array before sort:
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1]
Array after sort:
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]
</pre>
=={{header|ActionScript}}==
<
{
for(var i:int = 1; i < array.length;i++)
Line 181 ⟶ 511:
}
return array;
}</
=={{header|Ada}}==
<
procedure Insertion_Sort(Item : in out Data_Array) is
Line 201 ⟶ 531:
Item(J + 1) := Value;
end loop;
end Insertion_Sort;</
=={{header|ALGOL 68}}==
Line 211 ⟶ 541:
{{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:
Line 235 ⟶ 565:
in place insertion sort(ref data);
FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line);
print((data))</
{{out}}
<pre>
Line 244 ⟶ 574:
=={{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 ) ;
Line 256 ⟶ 586:
end while_j_ge_0_and_Aj_gt_v ;
A( j + 1 ) := v
end insertionSortI ;</
Test the insertionSortI procedure.
<
% external in-place insertion sort procedure %
procedure insertionSortI ( integer array A( * ); integer value lb, ub ) ;
Line 273 ⟶ 603:
write( i_w := 1, d( 1 ) );
for i := 2 until 8 do writeon( i_w := 1, d( i ) )
end.</
{{out}}
<pre>
-56 -1 0 0 2 3 9 34
</pre>
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">-- In-place insertion sort
on insertionSort(theList, l, r) -- Sort items l thru r of theList.
set listLength to (count theList)
if (listLength < 2) then return
-- Convert negative and/or transposed range indices.
if (l < 0) then set l to listLength + l + 1
if (r < 0) then set r to listLength + r + 1
if (l > r) then set {l, r} to {r, l}
-- The list as a script property to allow faster references to its items.
script o
property lst : theList
end script
-- Set up a minor optimisation whereby the latest instance of the highest value so far isn't
-- put back into the list until either it's superseded or the end of the sort is reached.
set highestSoFar to o's lst's item l
set rv to o's lst's item (l + 1)
if (highestSoFar > rv) then
set o's lst's item l to rv
else
set highestSoFar to rv
end if
-- Work through the rest of the range, rotating values back into the sorted group as necessary.
repeat with j from (l + 2) to r
set rv to o's lst's item j
if (highestSoFar > rv) then
repeat with i from (j - 2) to l by -1
set lv to o's lst's item i
if (lv > rv) then
set o's lst's item (i + 1) to lv
else
set i to i + 1
exit repeat
end if
end repeat
set o's lst's item i to rv
else
set o's lst's item (j - 1) to highestSoFar
set highestSoFar to rv
end if
end repeat
set o's lst's item r to highestSoFar
return -- nothing.
end insertionSort
property sort : insertionSort
-- Demo:
local aList
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.
return aList</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">{6, 11, 15, 22, 41, 45, 54, 59, 59, 60, 61, 64, 66, 73, 77, 77, 89, 91, 97, 100}</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program insertionSort.s */
/* look Pseudocode begin this task */
/************************************/
/* Constantes */
/************************************/
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
sMessResult: .ascii "Value : "
sMessValeur: .fill 11, 1, ' ' @ size => 11
szCarriageReturn: .asciz "\n"
.align 4
iGraine: .int 123456
.equ NBELEMENTS, 10
#TableNumber: .int 1,3,6,2,5,9,10,8,4,7
TableNumber: .int 10,9,8,7,6,5,4,3,2,1
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
1:
ldr r0,iAdrTableNumber @ address number table
mov r1,#0
mov r2,#NBELEMENTS @ number of élements
bl insertionSort
ldr r0,iAdrTableNumber @ address number table
bl displayTable
ldr r0,iAdrTableNumber @ address number table
mov r1,#NBELEMENTS @ number of élements
bl isSorted @ control sort
cmp r0,#1 @ sorted ?
beq 2f
ldr r0,iAdrszMessSortNok @ no !! error sort
bl affichageMess
b 100f
2: @ yes
ldr r0,iAdrszMessSortOk
bl affichageMess
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrsMessValeur: .int sMessValeur
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsMessResult: .int sMessResult
iAdrTableNumber: .int TableNumber
iAdrszMessSortOk: .int szMessSortOk
iAdrszMessSortNok: .int szMessSortNok
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements > 0 */
/* r0 return 0 if not sorted 1 if sorted */
isSorted:
push {r2-r4,lr} @ save registers
mov r2,#0
ldr r4,[r0,r2,lsl #2]
1:
add r2,#1
cmp r2,r1
movge r0,#1
bge 100f
ldr r3,[r0,r2, lsl #2]
cmp r3,r4
movlt r0,#0
blt 100f
mov r4,r3
b 1b
100:
pop {r2-r4,lr}
bx lr @ return
/******************************************************************/
/* insertion sort */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first element */
/* r2 contains the number of element */
insertionSort:
push {r2,r3,r4,lr} @ save registers
add r3,r1,#1 @ start index i
1: @ start loop
ldr r4,[r0,r3,lsl #2] @ load value A[i]
sub r5,r3,#1 @ index j
2:
ldr r6,[r0,r5,lsl #2] @ load value A[j]
cmp r6,r4 @ compare value
ble 3f
add r5,#1 @ increment index j
str r6,[r0,r5,lsl #2] @ store value A[j+1]
sub r5,#2 @ j = j - 1
cmp r5,r1
bge 2b @ loop if j >= first item
3:
add r5,#1 @ increment index j
str r4,[r0,r5,lsl #2] @ store value A[i] in A[j+1]
add r3,#1 @ increment index i
cmp r3,r2 @ end ?
blt 1b @ no -> loop
100:
pop {r2,r3,r4,lr}
bx lr @ return
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* r0 contains the address of table */
displayTable:
push {r0-r3,lr} @ save registers
mov r2,r0 @ table address
mov r3,#0
1: @ loop display table
ldr r0,[r2,r3,lsl #2]
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
add r3,#1
cmp r3,#NBELEMENTS - 1
ble 1b
ldr r0,iAdrszCarriageReturn
bl affichageMess
100:
pop {r0-r3,lr}
bx lr
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {r0,r1,r2,r7,lr} @ save registres
mov r2,#0 @ counter length
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call systeme
pop {r0,r1,r2,r7,lr} @ restaur des 2 registres */
bx lr @ return
/******************************************************************/
/* Converting a register to a decimal unsigned */
/******************************************************************/
/* r0 contains value and r1 address area */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes */
.equ LGZONECAL, 10
conversion10:
push {r1-r4,lr} @ save registers
mov r3,r1
mov r2,#LGZONECAL
1: @ start loop
bl divisionpar10U @ unsigned r0 <- dividende. quotient ->r0 reste -> r1
add r1,#48 @ digit
strb r1,[r3,r2] @ store digit on area
cmp r0,#0 @ stop if quotient = 0
subne r2,#1 @ else previous position
bne 1b @ and loop
@ and move digit from left of area
mov r4,#0
2:
ldrb r1,[r3,r2]
strb r1,[r3,r4]
add r2,#1
add r4,#1
cmp r2,#LGZONECAL
ble 2b
@ and move spaces in end on area
mov r0,r4 @ result length
mov r1,#' ' @ space
3:
strb r1,[r3,r4] @ store space in area
add r4,#1 @ next position
cmp r4,#LGZONECAL
ble 3b @ loop if r4 <= area size
100:
pop {r1-r4,lr} @ restaur registres
bx lr @return
/***************************************************/
/* division par 10 unsigned */
/***************************************************/
/* r0 dividende */
/* r0 quotient */
/* r1 remainder */
divisionpar10U:
push {r2,r3,r4, lr}
mov r4,r0 @ save value
//mov r3,#0xCCCD @ r3 <- magic_number lower raspberry 3
//movt r3,#0xCCCC @ r3 <- magic_number higter raspberry 3
ldr r3,iMagicNumber @ r3 <- magic_number raspberry 1 2
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0)
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
pop {r2,r3,r4,lr}
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">insertionSort: function [items][
arr: new items
loop 1..(size items)-1 'i [
value: arr\[i]
j: i - 1
while [and? -> j >= 0
-> value < arr\[j]]
[
arr\[j+1]: arr\[j]
j: j - 1
]
arr\[j+1]: value
]
return arr
]
print insertionSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
=={{header|ATS}}==
===For arrays whose elements must not be of linear type===
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)'''.
<syntaxhighlight lang="ats">#include "share/atspre_staload.hats"
(*------------------------------------------------------------------*)
(* Interface *)
extern fn {a : t@ype} (* The "less than" template. *)
insertion_sort$lt : (a, a) -<> bool (* Arguments by value. *)
extern fn {a : t@ype}
insertion_sort
{n : int}
(arr : &array (a, n) >> _,
n : size_t n)
:<!wrt> void
(*------------------------------------------------------------------*)
(* Implementation *)
implement {a}
insertion_sort {n} (arr, n) =
let
macdef lt = insertion_sort$lt<a>
fun
sort {i : int | 1 <= i; i <= n}
.<n - i>.
(arr : &array (a, n) >> _,
i : size_t i)
:<!wrt> void =
if i <> n then
let
fun
find_new_position
{j : nat | j <= i}
.<j>.
(arr : &array (a, n) >> _,
elem : a,
j : size_t j)
:<> [j : nat | j <= i] size_t j =
if j = i2sz 0 then
j
else if ~(elem \lt arr[pred j]) then
j
else
find_new_position (arr, elem, pred j)
val j = find_new_position (arr, arr[i], i)
in
if j < i then
array_subcirculate<a> (arr, j, i);
sort (arr, succ i)
end
prval () = lemma_array_param arr
in
if n <> i2sz 0 then
sort (arr, i2sz 1)
end
(*------------------------------------------------------------------*)
implement
insertion_sort$lt<int> (x, y) =
x < y
implement
main0 () =
let
#define SIZE 30
var i : [i : nat] int i
var arr : array (int, SIZE)
in
array_initize_elt<int> (arr, i2sz SIZE, 0);
for (i := 0; i < SIZE; i := succ i)
arr[i] := $extfcall (int, "rand") % 10;
for (i := 0; i < SIZE; i := succ i)
print! (" ", arr[i]);
println! ();
insertion_sort<int> (arr, i2sz SIZE);
for (i := 0; i < SIZE; i := succ i)
print! (" ", arr[i]);
println! ()
end</syntaxhighlight>
{{out}}
Sorting random numbers.
<pre>$ patscc -DATS_MEMALLOC_GCBDW -O3 insertion_sort_task_array_of_nonlinear.dats -lgc && ./a.out
3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6 1 8 7 9 2 0 2 3 7 5
0 0 0 1 1 2 2 2 2 2 3 3 3 3 5 5 5 6 6 6 6 6 7 7 7 7 8 9 9 9</pre>
===For arrays whose elements may be of linear type===
If the elements of the array may be of linear type, then it becomes necessary to compare the elements by reference. Furthermore it is necessary to break down the array's view, to obtain views of the elements to be compared. Here, as in the simpler implementation for non-linear elements, I use '''array_subcirculate''' to insert an element into its correct position.
(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.)
<syntaxhighlight lang="ats">#include "share/atspre_staload.hats"
(*------------------------------------------------------------------*)
(* Interface *)
extern fn {a : vt@ype} (* The "less than" template. *)
insertion_sort$lt : (&a, &a) -<> bool (* Arguments by reference. *)
extern fn {a : vt@ype}
insertion_sort
{n : int}
(arr : &array (a, n) >> _,
n : size_t n)
:<!wrt> void
(*------------------------------------------------------------------*)
(* Implementation *)
implement {a}
insertion_sort {n} (arr, n) =
let
macdef lt = insertion_sort$lt<a>
fun
sort {i : int | 1 <= i; i <= n}
{p_arr : addr}
.<n - i>.
(pf_arr : !array_v (a, p_arr, n) >> _ |
p_arr : ptr p_arr,
i : size_t i)
:<!wrt> void =
if i <> n then
let
val pi = ptr_add<a> (p_arr, i)
fun
find_new_position
{j : nat | j <= i}
.<j>.
(pf_left : !array_v (a, p_arr, j) >> _,
pf_i : !a @ (p_arr + (i * sizeof a)) |
j : size_t j)
:<> [j : nat | j <= i] size_t j =
if j = i2sz 0 then
j
else
let
prval @(pf_left1, pf_k) = array_v_unextend pf_left
val k = pred j
val pk = ptr_add<a> (p_arr, k)
in
if ~((!pi) \lt (!pk)) then
let
prval () = pf_left :=
array_v_extend (pf_left1, pf_k)
in
j
end
else
let
val new_pos =
find_new_position (pf_left1, pf_i | k)
prval () = pf_left :=
array_v_extend (pf_left1, pf_k)
in
new_pos
end
end
prval @(pf_left, pf_right) =
array_v_split {a} {p_arr} {n} {i} pf_arr
prval @(pf_i, pf_rest) = array_v_uncons pf_right
val j = find_new_position (pf_left, pf_i | i)
prval () = pf_arr :=
array_v_unsplit (pf_left, array_v_cons (pf_i, pf_rest))
in
if j < i then
array_subcirculate<a> (!p_arr, j, i);
sort (pf_arr | p_arr, succ i)
end
prval () = lemma_array_param arr
in
if n <> i2sz 0 then
sort (view@ arr | addr@ arr, i2sz 1)
end
(*------------------------------------------------------------------*)
(* The demonstration converts random numbers to linear strings, then
sorts the elements by their first character. Thus here is a simple
demonstration that the sort can handle elements of linear type, and
also that the sort is stable. *)
implement
main0 () =
let
implement
insertion_sort$lt<Strptr1> (x, y) =
let
val sx = $UNSAFE.castvwtp1{string} x
and sy = $UNSAFE.castvwtp1{string} y
val cx = $effmask_all $UNSAFE.string_get_at (sx, 0)
and cy = $effmask_all $UNSAFE.string_get_at (sy, 0)
in
cx < cy
end
implement
array_initize$init<Strptr1> (i, x) =
let
#define BUFSIZE 10
var buffer : array (char, BUFSIZE)
val () = array_initize_elt<char> (buffer, i2sz BUFSIZE, '\0')
val _ = $extfcall (int, "snprintf", addr@ buffer,
i2sz BUFSIZE, "%d",
$extfcall (int, "rand") % 100)
val () = buffer[BUFSIZE - 1] := '\0'
in
x := string0_copy ($UNSAFE.cast{string} buffer)
end
implement
array_uninitize$clear<Strptr1> (i, x) =
strptr_free x
#define SIZE 30
val @(pf_arr, pfgc_arr | p_arr) =
array_ptr_alloc<Strptr1> (i2sz SIZE)
macdef arr = !p_arr
var i : [i : nat] int i
in
array_initize<Strptr1> (arr, i2sz SIZE);
for (i := 0; i < SIZE; i := succ i)
let
val p = ptr_add<Strptr1> (p_arr, i)
val s = $UNSAFE.ptr0_get<string> p
in
print! (" ", s)
end;
println! ();
insertion_sort<Strptr1> (arr, i2sz SIZE);
for (i := 0; i < SIZE; i := succ i)
let
val p = ptr_add<Strptr1> (p_arr, i)
val s = $UNSAFE.ptr0_get<string> p
in
print! (" ", s)
end;
println! ();
array_uninitize<Strptr1> (arr, i2sz SIZE);
array_ptr_free (pf_arr, pfgc_arr | p_arr)
end</syntaxhighlight>
{{out}}
Sorting random numbers by their first digit, to demonstrate that the sort is stable. The numbers are stored in the array as linear strings (strings that must be explicitly freed), to demonstrate that the sort works with linear types.
<pre>$ patscc -DATS_MEMALLOC_LIBC -O3 insertion_sort_task_array_of_linear.dats && ./a.out
83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35
15 11 21 27 26 26 29 23 35 36 30 35 49 40 59 62 63 68 67 62 67 77 72 83 86 86 82 93 92 90</pre>
===For linear lists whose elements may be of linear type===
It is useful in a language such as ATS to have a stable insertion sort that operates on singly-linked lists. Such a sort can serve as the innermost part of a list mergesort or list quicksort.
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.
<syntaxhighlight lang="ats">#include "share/atspre_staload.hats"
(*------------------------------------------------------------------*)
(* Interface *)
extern fn {a : vt@ype} (* The "less than" template. *)
insertion_sort$lt : (&a, &a) -<> bool (* Arguments by reference. *)
extern fn {a : vt@ype}
insertion_sort
{n : int}
(lst : list_vt (a, n))
:<!wrt> list_vt (a, n)
(*------------------------------------------------------------------*)
(* Implementation *)
(* This implementation is based on the insertion-sort part of the
mergesort code of the ATS prelude.
Unlike the prelude, however, I build the sorted list in reverse
order. Building the list in reverse order actually makes the
implementation more like that for an array. *)
(* Some convenient shorthands. *)
#define NIL list_vt_nil ()
#define :: list_vt_cons
(* Inserting in reverse order minimizes the work for a list already
nearly sorted, or for stably sorting a list whose entries often
have equal keys. *)
fun {a : vt@ype}
insert_reverse
{m : nat}
{p_xnode : addr}
{p_x : addr}
{p_xs : addr}
.<m>.
(pf_x : a @ p_x,
pf_xs : list_vt (a, 0)? @ p_xs |
dst : &list_vt (a, m) >> list_vt (a, m + 1),
(* list_vt_cons_unfold is a viewtype created by the
unfolding of a list_vt_cons (our :: operator). *)
xnode : list_vt_cons_unfold (p_xnode, p_x, p_xs),
p_x : ptr p_x,
p_xs : ptr p_xs)
:<!wrt> void =
(* dst is some tail of the current (reverse-order) destination list.
xnode is a viewtype for the current node in the source list.
p_x points to the node's CAR.
p_xs points to the node's CDR. *)
case+ dst of
| @ (y :: ys) =>
if insertion_sort$lt<a> (!p_x, y) then
let (* Move to the next destination node. *)
val () = insert_reverse (pf_x, pf_xs | ys, xnode, p_x, p_xs)
prval () = fold@ dst
in
end
else
let (* Insert xnode here. *)
prval () = fold@ dst
val () = !p_xs := dst
val () = dst := xnode
prval () = fold@ dst
in
end
| ~ NIL =>
let (* Put xnode at the end. *)
val () = dst := xnode
val () = !p_xs := NIL
prval () = fold@ dst
in
end
implement {a}
insertion_sort {n} lst =
let
fun (* Create a list sorted in reverse. *)
loop {i : nat | i <= n}
.<n - i>.
(dst : &list_vt (a, i) >> list_vt (a, n),
src : list_vt (a, n - i))
:<!wrt> void =
case+ src of
| @ (x :: xs) =>
let
val tail = xs
in
insert_reverse<a> (view@ x, view@ xs |
dst, src, addr@ x, addr@ xs);
loop (dst, tail)
end
| ~ NIL => () (* We are done. *)
prval () = lemma_list_vt_param lst
var dst : List_vt a = NIL
in
loop (dst, lst);
(* Reversing a linear list is an in-place operation. *)
list_vt_reverse<a> dst
end
(*------------------------------------------------------------------*)
(* The demonstration converts random numbers to linear strings, then
sorts the elements by their first character. Thus here is a simple
demonstration that the sort can handle elements of linear type, and
also that the sort is stable. *)
implement
main0 () =
let
implement
insertion_sort$lt<Strptr1> (x, y) =
let
val sx = $UNSAFE.castvwtp1{string} x
and sy = $UNSAFE.castvwtp1{string} y
val cx = $effmask_all $UNSAFE.string_get_at (sx, 0)
and cy = $effmask_all $UNSAFE.string_get_at (sy, 0)
in
cx < cy
end
implement
list_vt_freelin$clear<Strptr1> x =
strptr_free x
#define SIZE 30
fn
create_the_list ()
:<!wrt> list_vt (Strptr1, SIZE) =
let
fun
loop {i : nat | i <= SIZE}
.<SIZE - i>.
(lst : list_vt (Strptr1, i),
i : size_t i)
:<!wrt> list_vt (Strptr1, SIZE) =
if i = i2sz SIZE then
list_vt_reverse lst
else
let
#define BUFSIZE 10
var buffer : array (char, BUFSIZE)
val () =
array_initize_elt<char> (buffer, i2sz BUFSIZE, '\0')
val _ = $extfcall (int, "snprintf", addr@ buffer,
i2sz BUFSIZE, "%d",
$extfcall (int, "rand") % 100)
val () = buffer[BUFSIZE - 1] := '\0'
val s = string0_copy ($UNSAFE.cast{string} buffer)
in
loop (s :: lst, succ i)
end
in
loop (NIL, i2sz 0)
end
var p : List string
val lst = create_the_list ()
val () =
for (p := $UNSAFE.castvwtp1{List string} lst;
isneqz p;
p := list_tail p)
print! (" ", list_head p)
val () = println! ()
val lst = insertion_sort<Strptr1> lst
val () =
for (p := $UNSAFE.castvwtp1{List string} lst;
isneqz p;
p := list_tail p)
print! (" ", list_head p)
val () = println! ()
val () = list_vt_freelin lst
in
end</syntaxhighlight>
{{out}}
Sorting random numbers by their first digit, to demonstrate that the sort is stable. The numbers are stored in the list as linear strings (strings that must be explicitly freed), to demonstrate that the sort works if the list elements themselves are linear.
<pre>$ patscc -DATS_MEMALLOC_LIBC -O3 insertion_sort_task_linear_list.dats && ./a.out
83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35
15 11 21 27 26 26 29 23 35 36 30 35 49 40 59 62 63 68 67 62 67 77 72 83 86 86 82 93 92 90</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")
Line 297 ⟶ 1,412:
sorted .= "," . a%A_Index%
Return SubStr(sorted,2) ; drop leading comma
}</syntaxhighlight>
=={{header|AWK}}==
Sort standard input (storing lines into an array) and output to standard output
<
line[NR] = $0
}
Line 318 ⟶ 1,433:
print line[i]
}
}</
=={{header|Bash}}==
<syntaxhighlight lang="bash">#!/bin/bash
# Sorting integers with insertion sort
function insertion_sort ()
{
# input: unsorted integer array
# output: sorted integer array (ascending)
# local variables
local -a arr # array
local -i i # integers
local -i j
local -i key
local -i prev
local -i leftval
local -i N # size of array
arr=( $@ ) # copy args into array
N=${#arr[*]} # arr extent
readonly N # make const
# insertion sort
for (( i=1; i<$N; i++ )) # c-style for loop
do
key=$((arr[$i])) # current value
prev=$((arr[$i-1])) # previous value
j=$i # current index
while [ $j -gt 0 ] && [ $key -lt $prev ] # inner loop
do
arr[$j]=$((arr[$j-1])) # shift
j=$(($j-1)) # decrement
prev=$((arr[$j-1])) # last value
done
arr[$j]=$(($key)) # insert key in proper order
done
echo ${arr[*]} # output sorted array
}
################
function main ()
{
# main script
declare -a sorted
# use a default if no cmdline list
if [ $# -eq 0 ]; then
arr=(10 8 20 100 -3 12 4 -5 32 0 1)
else
arr=($@) #cmdline list of ints
fi
echo
echo "original"
echo -e "\t ${arr[*]} \n"
sorted=($(insertion_sort ${arr[*]})) # call function
echo
echo "sorted:"
echo -e "\t ${sorted[*]} \n"
}
#script starts here
# source or run
if [[ "$0" == "bash" ]]; then # script is sourced
unset main
else
main "$@" # call with cmdline args
fi
#END</syntaxhighlight>
{{out}}
<pre>
original
10 8 20 100 -3 12 4 -5 32 0 1
sorted:
-5 -3 0 1 4 8 10 12 20 32 100
</pre>
=={{header|B4X}}==
The array type can be changed to Object and it will then work with any numeric type.
<syntaxhighlight lang="b4x">Sub InsertionSort (A() As Int)
For i = 1 To A.Length - 1
Dim value As Int = A(i)
Dim j As Int = i - 1
Do While j >= 0 And A(j) > value
A(j + 1) = A(j)
j = j - 1
Loop
A(j + 1) = value
Next
End Sub
Sub Test
Dim arr() As Int = Array As Int(34, 23, 54, 123, 543, 123)
InsertionSort(arr)
For Each i As Int In arr
Log(i)
Next
End Sub
</syntaxhighlight>
{{out}}
<pre>
23
34
54
123
123
543
</pre>
=={{header|BASIC}}==
Line 325 ⟶ 1,564:
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
Line 354 ⟶ 1,593:
theList(j + 1) = insertionElement
NEXT
END SUB</
{{out}}
Line 361 ⟶ 1,600:
</pre>
==={{header|
{{works with|BASICA}}
{{works with|QBasic}}
{{works with|QuickBASIC}}
{{works with|VB-DOS}}
Sorts N integers in an array a() with the Insertion sort
<syntaxhighlight lang="qbasic">
10 'SAVE "INSERTGW",A
20 DEFINT A-Z
30 OPTION BASE 1
40 N=20: R=100: I=0: Y=0: V=0: P=0
50 DIM A(N)
60 ' Creates the disordered array
70 CLS: PRINT "This program sorts by Insertion a list of randomly generated numbers."
80 PRINT: PRINT "Unsorted list:"
90 RANDOMIZE TIMER
100 FOR I = 1 TO N
110 A(I) = INT(RND * R) + 1
120 NEXT I
130 GOSUB 260
140 PRINT: PRINT "Sorted list."
150 ' Insertion Sort
160 FOR I=1 TO N
170 V=A(I): P=I-1: S=1
180 WHILE P>0 AND S=1
185 S=0
190 IF A(P) > V THEN A(P+1)=A(P): P=P-1: S=1
200 WEND
210 A(P+1) = V
220 NEXT I
230 GOSUB 260
240 PRINT: PRINT "End of program execution."
250 END
260 ' Print list routine
270 FOR I=1 TO N
280 PRINT A(I);
290 NEXT I
300 PRINT
310 RETURN
</syntaxhighlight>
{{out}}
<pre>This program sorts by Insertion a list of randomly generated numbers.
Unsorted list:
73 11 100 68 28 48 3 36 15 34 31 26 47 61 5 58 15 86 69 79
Sorted list:
3 5 11 15 15 26 28 31 34 36 47 48 58 61 68 69 73 79 86 100
End of program execution.</pre>
==={{header|ZX BASIC}}===
Sorts N elements in array i() into ascending order. Invoke with GO SUB 500.
<syntaxhighlight lang="zxbasic">500 FOR j=1 TO N-1
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
600 NEXT j: RETURN</syntaxhighlight>
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:
<pre>
530 IF k>0 THEN IF i(k)>c THEN LET i(k+1)=i(k): LET k=k-1: GO TO 530 </pre>
==={{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)
Line 383 ⟶ 1,691:
a(j%) = t
NEXT
ENDPROC</
{{out}}
<pre>
Line 389 ⟶ 1,697:
</pre>
==={{header|Commodore BASIC}}===
<
10 DIM A(10): N=9
11 REM GENERATE SOME RANDOM NUMBERS AND PRINT THEM
Line 399 ⟶ 1,707:
32 RETURN
50 PRINT: FOR I=0 TO N: PRINTA(I): NEXT: RETURN
</syntaxhighlight>
==={{header|IS-BASIC}}===
<syntaxhighlight lang="is-basic">100 PROGRAM "InserSrt.bas"
110 RANDOMIZE
120 NUMERIC ARRAY(5 TO 21)
130 CALL INIT(ARRAY)
140 CALL WRITE(ARRAY)
150 CALL INSERTSORT(ARRAY)
160 CALL WRITE(ARRAY)
170 DEF INIT(REF A)
180 FOR I=LBOUND(A) TO UBOUND(A)
190 LET A(I)=RND(98)+1
200 NEXT
210 END DEF
220 DEF WRITE(REF A)
230 FOR I=LBOUND(A) TO UBOUND(A)
240 PRINT A(I);
250 NEXT
260 PRINT
270 END DEF
280 DEF INSERTSORT(REF A)
290 FOR J=LBOUND(A)+1 TO UBOUND(A)
300 LET I=J-1:LET SW=A(J)
310 DO WHILE I>=LBOUND(A) AND SW<A(I)
320 LET A(I+1)=A(I):LET I=I-1
330 LOOP
340 LET A(I+1)=SW
350 NEXT
360 END DEF</syntaxhighlight>
=={{header|BASIC256}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic">global array
dim array(15)
a = array[?,]
b = array[?]
for i = a to b-1
array[i] = int(rand * 100)
next i
print "unsort ";
for i = a to b-1
print rjust(array[i], 4);
next i
call insertionSort(array) # ordenar el array
print chr(10); " sort ";
for i = a to b-1
print rjust(array[i], 4);
next i
end
subroutine insertionSort(array)
lb = array[?,]
for i = lb + 1 to array[?]-1
valor = array[i]
j = i - 1
while j >= lb and array[j] > valor
array[j +1] = array[j]
j -= 1
end while
array[j+1] = valor
next i
end subroutine</syntaxhighlight>
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">get "libhdr"
let insertionSort(A, len) be
for i = 1 to len-1 do
$( let value = A!i
let j = i-1
while j >= 0 & A!j > value do
$( A!(j+1) := A!j
j := j-1
$)
A!(j+1) := value
$)
let write(s, A, len) be
$( writes(s)
for i=0 to len-1 do writed(A!i, 4)
wrch('*N')
$)
let start() be
$( let array = table 4,65,2,-31,0,99,2,83,782,1
let length = 10
write("Before: ", array, length)
insertionSort(array, length)
write("After: ", array, length)
$)</syntaxhighlight>
{{out}}
<pre>Before: 4 65 2 -31 0 99 2 83 782 1
After: -31 0 1 2 2 4 65 83 99 782</pre>
=={{header|Binary Lambda Calculus}}==
As documented at https://github.com/tromp/AIT/blob/master/lists/sort.lam, the 55 byte BLC program
<pre>15 46 84 06 05 46 81 60 15 fb ec 2f 80 01 5b f9 7f 0b 7e f7 2f ec 2d fb 80 56 05 fd 85 bb 76 11 5d 50 5c 00 8b f3 ff 04 af fe 60 de 57 ff 30 5d 81 ff c2 dd 9a 28 20</pre>
sorts a list of bitstrings, such as integers of a fixed bit-width, lexicographically.
=={{header|C}}==
<
void insertion_sort(int*, const size_t);
void insertion_sort(int *a,
for(size_t i = 1; i < n; ++i) {
int
size_t j = i;
while( (j > 0) &&
a[j] = a[j - 1];
--j;
}
a[j] =
}
}
int main (int argc, char** argv) {
int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
const size_t n = sizeof(a) / sizeof(a[0]) ; // array extent
for
printf("%d%s", a[i], (i == (n - 1))? "\n" : " ");
insertion_sort(a, n);
for
printf("%d%s", a[i], (i == (n - 1))? "\n" : " ");
return 0;
}
</syntaxhighlight>
{{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;
Line 490 ⟶ 1,876:
}
}
}</
'''Example''':
<
using System;
Line 501 ⟶ 1,887:
Console.WriteLine(String.Join(" ", entries));
}
}</
=={{header|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.
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <iterator>
// std::rotate is used to shift the sub-region
// if the predicate p is true
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);
}
}
// calls with default Predicate std::less (sort ascending)
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));
// 'iterates' numbers to std::cout
// converts ints to strings for output to screen
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}</syntaxhighlight>
{{out}}
<pre>
-199 -52 2 3 33 56 99 100 177 200
</pre>
=={{header|Clojure}}==
<
(defn insertion-sort [coll]
(reduce (fn [result input]
Line 511 ⟶ 1,939:
[]
coll))
</syntaxhighlight>
Translated from the Haskell example:
<
(defn in-sort! [data]
(letfn [(insert ([raw x](insert [] raw x))
Line 523 ⟶ 1,951:
(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]</
=={{header|CLU}}==
<syntaxhighlight lang="clu">% Insertion-sort an array in place.
insertion_sort = proc [T: type] (a: array[T])
where T has lt: proctype (T,T) returns (bool)
bound_lo: int := array[T]$low(a)
bound_hi: int := array[T]$high(a)
for i: int in int$from_to(bound_lo, bound_hi) do
value: T := a[i]
j: int := i - 1
while j >= bound_lo cand value < a[j] do
a[j+1] := a[j]
j := j-1
end
a[j+1] := value
end
end insertion_sort
% Print an array
print_arr = proc [T: type] (a: array[T], w: int, s: stream)
where T has unparse: proctype (T) returns (string)
for el: T in array[T]$elements(a) do
stream$putright(s, T$unparse(el), w)
end
stream$putc(s, '\n')
end print_arr
start_up = proc ()
ai = array[int]
po: stream := stream$primary_output()
test: ai := ai$[7, -5, 0, 2, 99, 16, 4, 20, 47, 19]
stream$puts(po, "Before: ") print_arr[int](test, 3, po)
insertion_sort[int](test)
stream$puts(po, "After: ") print_arr[int](test, 3, po)
end start_up</syntaxhighlight>
{{out}}
<pre>Before: 7 -5 0 2 99 16 4 20 47 19
After: -5 0 2 4 7 16 19 20 47 99</pre>
=={{header|CMake}}==
<
function(insertion_sort var)
math(EXPR last "${ARGC} - 1") # Sort ARGV[1..last].
Line 556 ⟶ 2,025:
endforeach(i)
set("${var}" "${answer}" PARENT_SCOPE)
endfunction(insertion_sort)</
<
message(STATUS "${result}") # -- 11;22;33;44;55;66</
=={{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.
Line 589 ⟶ 2,058:
F-999.
EXIT.</
And a fully runnable version, by Steve Williams
{{works with|GnuCOBOL}}
<syntaxhighlight lang="cobol">
>>SOURCE FORMAT FREE
*> This code is dedicated to the public domain
Line 663 ⟶ 2,132:
stop run
.
end program insertionsort.</
{{out}}
Line 672 ⟶ 2,141:
=={{header|Common Lisp}}==
<
(let ((tail (member-if-not predicate list)))
(values (ldiff list tail) tail)))
Line 684 ⟶ 2,153:
(defun insertion-sort (list)
(reduce #'insert list :initial-value nil))</
<
(if (cdr sequence)
(insert (car sequence) ;; insert the current item into
Line 703 ⟶ 2,172:
(insert item ;; the list of the item sorted with the rest of the list
(cdr sequence)
predicate)))))</
=={{header|Craft Basic}}==
<syntaxhighlight lang="basic">define size = 10, value = 0
dim list[size]
gosub fill
gosub sort
gosub show
end
sub fill
for i = 0 to size - 1
let list[i] = int(rnd * 100)
next i
return
sub sort
for i = 1 to size - 1
let value = list[i]
let j = i - 1
do
if j >= 0 and list[j] > value then
let p = j + 1
let list[p] = list[j]
let j = j - 1
endif
loop j >= 0 and list[j] > value
let p = j + 1
let list[p] = value
wait
next i
return
sub show
for i = 0 to size - 1
print i, ": ", list[i]
next i
return</syntaxhighlight>
=={{header|D}}==
<
foreach (immutable i, value; data[1 .. $]) {
auto j = i + 1;
Line 720 ⟶ 2,248:
items.insertionSort;
items.writeln;
}</
{{out}}
<pre>[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]</pre>
Line 726 ⟶ 2,254:
===Higher Level Version===
{{trans|C++}}
<
void insertionSort(R)(R arr)
Line 756 ⟶ 2,284:
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|Dart}}==
{{trans|Java}}
<syntaxhighlight lang="dart">
insertSort(List<int> array){
for(int i = 1; i < array.length; i++){
int value = array[i];
int j = i - 1;
while(j >= 0 && array[j] > value){
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = value;
}
return array;
}
void main() {
List<int> a = insertSort([10, 3, 11, 15, 19, 1]);
print('${a}');
}
</syntaxhighlight>
{{out}}
<pre>array unsorted: [10, 3, 11, 15, 19, 1];
a sorted: [1, 3, 10, 11, 15, 19]</pre>
=={{header|Delphi}}==
Line 767 ⟶ 2,323:
Static array is an arbitrary-based array of fixed length
<
{$APPTYPE CONSOLE}
Line 816 ⟶ 2,372:
Writeln;
Readln;
end.</
{{out}}
<pre>
Line 825 ⟶ 2,381:
===String sort===
// string is 1-based variable-length array of Char
<
var
I, J, L: Integer;
Line 841 ⟶ 2,397:
S[J + 1]:= Ch;
end;
end;</
<pre>
// in : S = 'the quick brown fox jumps over the lazy dog'
Line 851 ⟶ 2,407:
A direct conversion of the pseudocode.
<
for i in 1..!(array.size()) {
def value := array[i]
Line 861 ⟶ 2,417:
array[j+1] := value
}
}</
Test case:
<
> 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()</
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
proc sort . d[] .
for i = 2 to len d[]
h = d[i]
j = i - 1
while j >= 1 and h < d[j]
d[j + 1] = d[j]
j -= 1
.
d[j + 1] = h
.
.
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
sort data[]
print data[]
</syntaxhighlight>
=={{header|Eiffel}}==
Line 877 ⟶ 2,452:
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
Line 908 ⟶ 2,483:
end
end</
=={{header|Elena}}==
ELENA 6.x :
<syntaxhighlight lang="elena">import extensions;
extension op
{
insertionSort()
= self
insertionSort(
for(int i := first + 1
var entry := self[i]
int j := i
while
self[j] := self[j - 1]
j -= 1
self[j] := entry
}
public program()
{
var list :=
console
console
}</syntaxhighlight>
{{out}}
<pre>
Line 951 ⟶ 2,527:
=={{header|Elixir}}==
<
def insert_sort(list) when is_list(list), do: insert_sort(list, [])
Line 960 ⟶ 2,536:
defp insert(x, sorted) when x < hd(sorted), do: [x | sorted]
defp insert(x, [h | t]), do: [h | insert(x, t)]
end</
Example:
Line 969 ⟶ 2,545:
=={{header|Emacs Lisp}}==
<syntaxhighlight lang="lisp">(defun min-or-max-of-a-list (numbers comparator)
"Return minimum or maximum of NUMBERS using COMPARATOR."
(let ((extremum (car numbers)))
(dolist (n (cdr numbers))
(when (funcall comparator n extremum)
(setq extremum n)))
extremum))
(defun
"Return NUMBERS without N.
If n is present twice or more, it will be removed only once."
(let (result)
(while numbers
(let (
(
(while numbers
(push (pop numbers) result))
(push number result))))
(nreverse result)))
(defun
"
(if numbers
(let ((extremum (min-or-max-of-a-list numbers comparator)))
(cons extremum
(insertion-sort (remove-number-from-list numbers extremum)
nil))
(insertion-sort '(1 2 3 9 8 7 25 12 3 2 1) #'>)</syntaxhighlight>
{{out}}
(25 12 9 8 7 3 3 2 2 1 1)
=={{header|EMal}}==
<syntaxhighlight lang="emal">
fun insertionSort = void by List a # sort list in place
for int i = 1; i < a.length; ++i
var v = a[i]
int j
for j = i - 1; j >= 0 and a[j] > v; --j
a[j + 1] = a[j]
end
a[j + 1] = v
end
end
List lists = List[ # a list of lists
int[4, 65, 2, -31, 0, 99, 83, 782, 1],
real[5.17, 2, 5.12],
text["this", "is", "insertion", "sort"]]
for each List list in lists
writeLine("Before: " + text!list) # list as text
insertionSort(list)
writeLine("After : " + text!list)
writeLine()
end
</syntaxhighlight>
{{out}}
<pre>
Before: [4,65,2,-31,0,99,83,782,1]
After : [-31,0,1,2,4,65,83,99,782]
Before: [5.17,2.0,5.12]
After : [2.0,5.12,5.17]
Before: [this,is,insertion,sort]
After : [insertion,is,sort,this]
</pre>
=={{header|Erlang}}==
<
-export([insertion/1]).
Line 1,026 ⟶ 2,623:
insert(X,[]) -> [X];
insert(X,L=[H|_]) when X =< H -> [X|L];
insert(X,[H|T]) -> [H|insert(X, T)].</
And the calls:
<
{ok,sort}
2> sort:insertion([5,3,9,4,1,6,8,2,7]).
[1,2,3,4,5,6,7,8,9]</
=={{header|ERRE}}==
Note: array index is assumed to start at zero.
<syntaxhighlight lang="erre">
PROGRAM INSERTION_SORT
Line 1,070 ⟶ 2,667:
PRINT
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Line 1,078 ⟶ 2,675:
=={{header|Euphoria}}==
<
object temp
integer j
Line 1,099 ⟶ 2,696:
pretty_print(1,s,{2})
puts(1,"\nAfter: ")
pretty_print(1,insertion_sort(s),{2})</
{{out}}
Line 1,137 ⟶ 2,734:
=={{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).
Line 1,152 ⟶ 2,749:
B.[j+1] <- value
B // the array B is returned
</syntaxhighlight>
Functional Version
<
let insertionSort collection =
Line 1,171 ⟶ 2,768:
| x::xs, ys -> xs |> isort (sinsert x ys)
collection |> isort []
</syntaxhighlight>
=={{header|Factor}}==
{{trans|Haskell}}
<syntaxhighlight lang="factor">USING: kernel prettyprint sorting.extras sequences ;
: insertion-sort ( seq -- sorted-seq )
<reversed> V{ } clone [ swap insort-left! ] reduce ;
{ 6 8 5 9 3 2 1 4 7 } insertion-sort .</syntaxhighlight>
{{out}}
<pre>
{ 1 2 3 4 5 6 7 8 9 }
</pre>
But note that Factor already comes with an <code>insertion-sort</code> in the <code>sorting.insertion</code> vocabulary that is likely faster and more robust. See its implementation [https://docs.factorcode.org/content/word-insertion-sort%2Csorting.insertion.html here].
=={{header|Forth}}==
<
dup @ >r ( r: v ) \ v = a[i]
begin
Line 1,191 ⟶ 2,803:
create test 7 , 3 , 0 , 2 , 9 , 1 , 6 , 8 , 4 , 5 ,
test 10 sort
test 10 cells dump</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
implicit none
integer :: n, i, j
Line 1,211 ⟶ 2,823:
a(j + 1) = x
end do
end subroutine</
=== Alternate Fortran 77 version ===
IMPLICIT NONE
INTEGER N,I,J
Line 1,222 ⟶ 2,834:
J = I
10 J = J - 1
IF (J.EQ.0) GO TO 20
IF (A(J).LE.X) GO TO 20
Line 1,229 ⟶ 2,840:
20 A(J + 1) = X
30 CONTINUE
END</
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx
Line 1,281 ⟶ 2,892:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>unsort -7 -1 4 -6 5 2 1 -2 0 -5 -4 6 -3 7 3
sort -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7</pre>
=={{header|GAP}}==
<
local n, i, j, x;
n := Length(L);
Line 1,303 ⟶ 2,915:
InsertionSort(s);
s;
# "ABCDEFGHIJKLMNOPQRSTUVWXYZ"</
=={{header|Go}}==
<
import "fmt"
Line 1,328 ⟶ 2,940:
insertionSort(list)
fmt.Println("sorted! ", list)
}</
{{out}}
<pre>
Line 1,336 ⟶ 2,948:
A generic version that takes any container that conforms to <code>sort.Interface</code>:
<
import (
Line 1,357 ⟶ 2,969:
insertionSort(sort.IntSlice(list))
fmt.Println("sorted! ", list)
}</
{{out}}
<pre>
Line 1,365 ⟶ 2,977:
Using binary search to locate the place to insert:
<
import (
Line 1,387 ⟶ 2,999:
insertionSort(list)
fmt.Println("sorted! ", list)
}</
{{out}}
<pre>
Line 1,396 ⟶ 3,008:
=={{header|Groovy}}==
Solution:
<
def size = list.size()
Line 1,408 ⟶ 3,020:
}
list
}</
Test:
<
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]))</
{{out}}
Line 1,419 ⟶ 3,031:
=={{header|Haskell}}==
<
insertionSort :: Ord a => [a] -> [a]
Line 1,426 ⟶ 3,038:
-- Example use:
-- *Main> insertionSort [6,8,5,9,3,2,1,4,7]
-- [1,2,3,4,5,6,7,8,9]</
=={{header|Haxe}}==
<syntaxhighlight lang="haxe">class InsertionSort {
@:generic
public static function sort<T>(arr:Array<T>) {
for (i in 1...arr.length) {
var value = arr[i];
var j = i - 1;
while (j >= 0 && Reflect.compare(arr[j], value) > 0) {
arr[j + 1] = arr[j--];
}
arr[j + 1] = value;
}
}
}
class Main {
static function main() {
var integerArray = [1, 10, 2, 5, -1, 5, -19, 4, 23, 0];
var floatArray = [1.0, -3.2, 5.2, 10.8, -5.7, 7.3,
3.5, 0.0, -4.1, -9.5];
var stringArray = ['We', 'hold', 'these', 'truths', 'to',
'be', 'self-evident', 'that', 'all',
'men', 'are', 'created', 'equal'];
Sys.println('Unsorted Integers: ' + integerArray);
InsertionSort.sort(integerArray);
Sys.println('Sorted Integers: ' + integerArray);
Sys.println('Unsorted Floats: ' + floatArray);
InsertionSort.sort(floatArray);
Sys.println('Sorted Floats: ' + floatArray);
Sys.println('Unsorted Strings: ' + stringArray);
InsertionSort.sort(stringArray);
Sys.println('Sorted Strings: ' + stringArray);
}
}</syntaxhighlight>
{{out}}
<pre>
Unsorted Integers: [1,10,2,5,-1,5,-19,4,23,0]
Sorted Integers: [-19,-1,0,1,2,4,5,5,10,23]
Unsorted Floats: [1,-3.2,5.2,10.8,-5.7,7.3,3.5,0,-4.1,-9.5]
Sorted Floats: [-9.5,-5.7,-4.1,-3.2,0,1,3.5,5.2,7.3,10.8]
Unsorted Strings: [We,hold,these,truths,to,be,self-evident,that,all,men,are,created,equal]
Sorted Strings: [We,all,are,be,created,equal,hold,men,self-evident,that,these,to,truths]
</pre>
=={{header|HicEst}}==
<
value = A(i)
j = i - 1
Line 1,440 ⟶ 3,097:
ENDIF
A(j+1) = value
ENDDO</
=={{header|Icon}} and {{header|Unicon}}==
<
demosort(insertionsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
Line 1,459 ⟶ 3,116:
}
return X
end</
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.
Line 1,473 ⟶ 3,130:
=={{header|Io}}==
<syntaxhighlight lang="io">
List do(
insertionSortInPlace := method(
Line 1,490 ⟶ 3,147:
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)</
A shorter, but slightly less efficient, version:
<
insertionSortInPlace := method(
# In fact, we could've done slice(1, size - 1) foreach(...)
Line 1,506 ⟶ 3,163:
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)
</syntaxhighlight>
=={{header|Isabelle}}==
<syntaxhighlight lang="isabelle">theory Insertionsort
imports Main
begin
fun insert :: "int ⇒ int list ⇒ int list" where
"insert x [] = [x]"
| "insert x (y#ys) = (if x ≤ y then (x#y#ys) else y#(insert x ys))"
text‹Example:›
lemma "insert 4 [1, 2, 3, 5, 6] = [1, 2, 3, 4, 5, 6]" by(code_simp)
fun insertionsort :: "int list ⇒ int list" where
"insertionsort [] = []"
| "insertionsort (x#xs) = insert x (insertionsort xs)"
lemma "insertionsort [4, 2, 6, 1, 8, 1] = [1, 1, 2, 4, 6, 8]" by(code_simp)
text‹
Our function behaves the same as the \<^term>‹sort› function of the standard library.
›
lemma insertionsort: "insertionsort xs = sort xs"
proof(induction xs)
case Nil
show "insertionsort [] = sort []" by simp
next
case (Cons x xs)
text‹Our \<^const>‹insert› behaves the same as the std libs \<^const>‹insort›.›
have "insert a as = insort a as" for a as by(induction as) simp+
with Cons show "insertionsort (x # xs) = sort (x # xs)" by simp
qed
text‹
Given that we behave the same as the std libs sorting algorithm,
we get the correctness properties for free.
›
corollary insertionsort_correctness:
"sorted (insertionsort xs)" and
"set (insertionsort xs) = set xs"
using insertionsort by(simp)+
text‹
The Haskell implementation from
🌐‹https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#Haskell›
also behaves the same. Ultimately, they all return a sorted list.
One exception to the Haskell implementation is that the type signature of
\<^const>‹foldr› in Isabelle is slightly different:
The initial value of the accumulator goes last.
›
definition rosettacode_haskell_insertionsort :: "int list ⇒ int list" where
"rosettacode_haskell_insertionsort ≡ λxs. foldr insert xs []"
lemma "rosettacode_haskell_insertionsort [4, 2, 6, 1, 8, 1] =
[1, 1, 2, 4, 6, 8]" by(code_simp)
lemma "rosettacode_haskell_insertionsort xs = insertionsort xs"
unfolding rosettacode_haskell_insertionsort_def by(induction xs) simp+
end</syntaxhighlight>
=={{header|J}}==
{{eff note|J|/:~}}
Solution inspired by the Common LISP solution:
<
Example of use:
<
_38 1 2 3 4 32 34 95 120</
=={{header|Java}}==
<
for(int i = 1; i < A.length; i++){
int value = A[i];
Line 1,527 ⟶ 3,245:
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);
Line 1,544 ⟶ 3,262:
a[j] = x;
}
}</
=={{header|JavaScript}}==
<
function insertionSort (a) {
for (var i = 0; i < a.length; i++) {
Line 1,560 ⟶ 3,278:
var a = [4, 65, 2, -31, 0, 99, 83, 782, 1];
insertionSort(a);
document.write(a.join(" "));</
=={{header|jq}}==
{{works with|jq|1.4}}
The insertion sort can be expressed directly in jq as follows:
<
reduce .[] as $x ([]; insert($x));</
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;
u;</
bsearch is the only non-trivial part of this solution, and so we include
Line 1,581 ⟶ 3,299:
(-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.<
if length == 0 then -1
elif length == 1 then
Line 1,618 ⟶ 3,336:
def insertion_sort:
reduce .[] as $x ([]; insert($x));</
Example:<
{{Out}}
[null,-1.1,1,1,1.1,2,[null],{"null":null}]
=={{header|Julia}}==
<
function insertionsort!(A::Array{T}) where T <: Number
Line 1,641 ⟶ 3,358:
x = randn(5)
@show x insertionsort!(x)</
{{out}}
Line 1,648 ⟶ 3,365:
=={{header|Kotlin}}==
<
for (index in 1 until array.size) {
val value = array[index]
Line 1,674 ⟶ 3,391:
insertionSort(numbers)
printArray("Sorted:", numbers)
}</
{{out}}
<pre>Unsorted: [5, 2, 3, 17, 12, 1, 8, 3, 4, 9, 7]
Sorted: [1, 2, 3, 3, 4, 5, 7, 8, 9, 12, 17]</pre>
=={{header|Ksh}}==
<syntaxhighlight lang="ksh">#!/bin/ksh
# An insertion sort in ksh
# # Variables:
#
typeset -a arr=( 4 65 2 -31 0 99 2 83 782 1 )
# # Functions:
#
# # Function _insertionSort(array) - Insersion sort of array of integers
#
function _insertionSort {
typeset _arr ; nameref _arr="$1"
typeset _i _j _val ; integer _i _j _val
for (( _i=1; _i<${#_arr[*]}; _i++ )); do
_val=${_arr[_i]}
(( _j = _i - 1 ))
while (( _j>=0 && _arr[_j]>_val )); do
_arr[_j+1]=${_arr[_j]}
(( _j-- ))
done
_arr[_j+1]=${_val}
done
}
######
# main #
######
_insertionSort arr
printf "%s" "( "
for (( i=0; i<${#arr[*]}; i++ )); do
printf "%d " ${arr[i]}
done
printf "%s\n" " )"</syntaxhighlight>
{{out}}
( -31 0 1 2 2 4 65 83 99 782 )
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{def sort
{def sort.i
{lambda {:x :a}
{if {A.empty? :a}
then {A.new :x}
else {if {<= :x {A.first :a}}
then {A.addfirst! :x :a}
else {A.addfirst! {A.first :a} {sort.i :x {A.rest :a}}} }}}}
{def sort.r
{lambda {:a1 :a2}
{if {A.empty? :a1}
then :a2
else {sort.r {A.rest :a1} {sort.i {A.first :a1} :a2}} }}}
{lambda {:a}
{sort.r :a {A.new}} }}
-> sort
{def A {A.new 4 65 2 -31 0 99 83 782 1}}
-> A
{sort {A}}
-> [-31,0,1,2,4,65,83,99,782]
</syntaxhighlight>
=={{header|Liberty BASIC}}==
<
dim A(itemCount)
for i = 1 to itemCount
Line 1,711 ⟶ 3,501:
next i
print
return</
=={{header|Lua}}==
Binary variation of Insertion sort (Has better complexity)
<syntaxhighlight lang="lua">do
local function lower_bound(container, container_begin, container_end, value, comparator)
local count = container_end - container_begin + 1
while count > 0 do
local half = bit.rshift(count, 1) -- or math.floor(count / 2)
local middle = container_begin + half
if comparator(container[middle], value) then
container_begin = middle + 1
count = count - half - 1
else
count = half
end
end
return container_begin
end
local function binary_insertion_sort_impl(container, comparator)
for i = 2, #container do
local j = i - 1
local selected = container[i]
local loc = lower_bound(container, 1, j, selected, comparator)
while j >= loc do
container[j + 1] = container[j]
j = j - 1
end
container[j + 1] = selected
end
end
local function binary_insertion_sort_comparator(a, b)
return a < b
end
function table.bininsertionsort(container, comparator)
if not comparator then
comparator = binary_insertion_sort_comparator
end
binary_insertion_sort_impl(container, comparator)
end
end</syntaxhighlight>
<syntaxhighlight lang="lua">function bins(tb, val, st, en)
local st, en = st or 1, en or #tb
local mid = math.floor((st + en)/2)
Line 1,730 ⟶ 3,567:
end
print(unpack(isort{4,5,2,7,8,3}))</
=={{header|Maple}}==
<
len := numelems(arr):
for i from 2 to len do
Line 1,744 ⟶ 3,581:
arr[j+1] := val:
end do:
arr;</
{{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;
Line 1,755 ⟶ 3,592:
A[[j + 1]] = value;];
A
]</
{{out}}
<pre>insertionSort@{ 2, 1, 3, 5}
{1, 2, 3, 5}</pre>
Line 1,762 ⟶ 3,599:
=={{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))
Line 1,777 ⟶ 3,614:
end %for
end %insertionSort</
Sample Usage:
<
ans =
1 2 3 4 5 6</
=={{header|Maxima}}==
<
[n: length(u), x, j],
for i from 2 thru n do (
Line 1,798 ⟶ 3,635:
u[j + 1]: x
)
)$</
=={{header|MAXScript}}==
<syntaxhighlight lang="maxscript">
fn inSort arr =
(
Line 1,816 ⟶ 3,653:
return arr
)
</syntaxhighlight>
Output:
<syntaxhighlight 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)
</syntaxhighlight>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout ("Before: " ++ show testlist ++ "\n"),
Stdout ("After: " ++ show (insertionsort testlist) ++ "\n")]
where testlist = [4,65,2,-31,0,99,2,83,782,1]
insertionsort :: [*]->[*]
insertionsort = foldr insert []
insert :: *->[*]->[*]
insert x [] = [x]
insert x (y:ys) = x:y:ys, if x<y
= y:insert x ys, otherwise</syntaxhighlight>
{{out}}
<pre>Before: [4,65,2,-31,0,99,2,83,782,1]
After: [-31,0,1,2,2,4,65,83,99,782]</pre>
=={{header|ML}}==
==={{header|mLite}}===
{{trans|OCaml}}
<
let
fun insert
Line 1,842 ⟶ 3,697:
println ` insertion_sort [6,8,5,9,3,2,1,4,7];
</syntaxhighlight>
Output
<pre>
Line 1,849 ⟶ 3,704:
==={{header|Standard ML}}===
<
fun insert (x, []) = [x]
| insert (x, y::ys) =
Line 1,858 ⟶ 3,713:
end;
insertion_sort Int.compare [6,8,5,9,3,2,1,4,7];</
=={{header|Modula-3}}==
{{trans|Ada}}
<
PROCEDURE IntSort(VAR item: ARRAY OF INTEGER) =
Line 1,877 ⟶ 3,732:
END;
END IntSort;
END InsertSort.</
=={{header|N/t/roff}}==
Line 1,884 ⟶ 3,739:
===Sliding method===
<
..
.de array
Line 1,938 ⟶ 3,793:
.a.pushln 13 64 22 87 54 87 23 92 11 64 5 9 3 3 0
.insertionsort a
.a.dump</
===Swapping method===
<
..
.de array
Line 1,985 ⟶ 3,840:
.a.pushln 13 64 22 87 54 87 23 92 11 64 5 9 3 3 0
.insertionsort a
.a.dump</
=={{header|Nanoquery}}==
{{trans|Python}}
<syntaxhighlight lang="nanoquery">def insertion_sort(L)
for i in range(1, len(L) - 1)
j = i - 1
key = L[i]
while (L[j] > key) and (j >= 0)
L[j + 1] = L[j]
j -= 1
end
L[j+1] = key
end
return L
end</syntaxhighlight>
=={{header|Nemerle}}==
From the psuedocode.
<
using Nemerle.English;
Line 2,015 ⟶ 3,886:
foreach (i in arr) Write($"$i ");
}
}</
=={{header|NetRexx}}==
<
options replace format comments java crossref savelog symbols binary
Line 2,065 ⟶ 3,936:
return ArrayList(A)
</syntaxhighlight>
{{out}}
<pre>
Line 2,088 ⟶ 3,959:
=={{header|Nim}}==
<
for i in 1 ..
let value = a[i]
var j = i
Line 2,099 ⟶ 3,970:
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
insertSort a
echo a</
{{out}}
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
=={{header|Oberon-2}}==
{{trans|Modula-3}}
<syntaxhighlight lang="oberon2">MODULE InsertionSort;
IMPORT Out;
VAR
A1:ARRAY 10 OF INTEGER;
PROCEDURE Init;
BEGIN
A1[0] := 4; A1[1] := 65; A1[2] := 2; A1[3] := -31;
A1[4] := 0; A1[5] := 99; A1[6] := 2; A1[7] := 83;
A1[8] := 782; A1[9] := 1;
END Init;
PROCEDURE InsertionSort(VAR A:ARRAY OF INTEGER);
VAR
i,j:LONGINT;
value:INTEGER;
BEGIN
FOR i := 1 TO LEN(A)-1 DO
value := A[i];
j := i-1;
WHILE((j >= 0) & (A[j] > value)) DO A[j+1] := A[j]; DEC(j) END;
A[j+1] := value
END;
END InsertionSort;
PROCEDURE PrintArray(VAR A:ARRAY OF INTEGER);
VAR i:LONGINT;
BEGIN
FOR i := 0 TO LEN(A)-1 DO Out.Int(A[i],0); Out.Char(' ') END;
Out.Ln
END PrintArray;
BEGIN
Init;
PrintArray(A1);
InsertionSort(A1);
PrintArray(A1);
END InsertionSort.
</syntaxhighlight>
{{out}}
<pre>4 65 2 -31 0 99 2 83 782 1
-31 0 1 2 2 4 65 83 99 782
</pre>
=={{header|Objeck}}==
<
bundle Default {
class Insert {
Line 2,128 ⟶ 4,048:
}
}
</syntaxhighlight>
=={{header|OCaml}}==
<
match lst with
| y
|
let insertion_sort = List.fold_left insert []
|> insertion_sort |> List.iter (Printf.printf " %u") |> print_newline</syntaxhighlight>
{{out}}
<pre> 1 2 3 4 5 6 7 8 9</pre>
=={{header|Oforth}}==
Line 2,146 ⟶ 4,067:
Returns a new sorted list.
<
| l i j v |
a asListBuffer ->l
Line 2,159 ⟶ 4,080:
l put(j 1 +, v)
]
l ;</
{{out}}
Line 2,170 ⟶ 4,091:
=={{header|ooRexx}}==
{{trans|REXX}}
<
/* using the insertion sort algorithm */
Call gen /* fill the array with test data */
Line 2,212 ⟶ 4,133:
Say 'Element' right(j,length(x.0)) arg(1)":" x.j
End
Return</
{{out}}
<pre>Element 1 before sort: ---Monday's Child Is Fair of Face (by Mother Goose)---
Line 2,238 ⟶ 4,159:
=={{header|Oz}}==
Direct translation of pseudocode. In-place sorting of mutable arrays.
<
proc {InsertionSort A}
Low = {Array.low A}
Line 2,258 ⟶ 4,179:
in
{InsertionSort Arr}
{Show {Array.toRecord unit Arr}}</
=={{header|PARI/GP}}==
<
for(i=1,#v-1,
my(j=i-1,x=v[i]);
Line 2,285 ⟶ 4,192:
);
v
};</
=={{header|Pascal}}==
{{works with|FPC}}
<syntaxhighlight lang="pascal">
program SortDemo;
{$mode objfpc}{$h+}{$b-}
procedure InsertionSort(var A: array of Integer);
var
I, J, Tmp: Integer;
begin
for I := 1 to High(a) do
if A[I] < A[I - 1] then begin
J := I;
Tmp := A[I];
repeat
A[J] := A[J - 1];
Dec(J);
until (J = 0) or (Tmp >= A[J - 1]);
A[J] := Tmp;
end;
end;
procedure PrintArray(const A: array of Integer);
var
I: Integer;
begin
Write('[');
for I := 0 to High(A) - 1 do
Write(A[I], ', ');
WriteLn(A[High(A)], ']');
end;
var
a: array[-7..6] of Integer = (-34, -20, 30, 13, 36, -10, 5, -25, 9, 19, 35, -50, 29, 11);
begin
InsertionSort(a);
PrintArray(a);
end.
</syntaxhighlight>
{{out}}
<pre>
[-50, -34, -25, -20, -10, 5, 9, 11, 13, 19, 29, 30, 35, 36]
</pre>
=={{header|Perl}}==
<
sub insertion_sort {
my (@list) = @_;
Line 2,308 ⟶ 4,258:
my @a = insertion_sort(4, 65, 2, -31, 0, 99, 83, 782, 1);
print "@a\n";
</syntaxhighlight>
{{out}}
-31 0 1 2 4 65 83 99 782
=={{header|Phix}}==
Copy of [[Sorting_algorithms/Insertion_sort#Euphoria|Euphoria]]
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">insertion_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">temp</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">j</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">temp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]></span><span style="color: #000000;">temp</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">j</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">temp</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">15</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"delta"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">31</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"alpha"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">19</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"gamma"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">13</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"beta"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">782</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Before: "</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">s</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"After: "</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">insertion_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,363 ⟶ 4,292:
=={{header|PHP}}==
<
for($i=0;$i<count($arr);$i++){
$val = $arr[$i];
Line 2,377 ⟶ 4,306:
$arr = array(4,2,1,6,9,3,8,7);
insertionSort($arr);
echo implode(',',$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)) ) ) )
Lst )</
{{out}}
<pre>: (insertionSort (5 3 1 7 4 1 1 20))
Line 2,392 ⟶ 4,321:
=={{header|PL/I}}==
<
insert_sort: proc(array);
dcl
h
do i
tmp =
do j = i - 1 by -1 while(j > l - 1 & array(j) > tmp);
array(j + 1) = array(j);
array(j + 1) = tmp;
end;
end insert_sort;
</syntaxhighlight>
=={{header|PL/M}}==
<syntaxhighlight lang="plm">100H:
/* INSERTION SORT ON 16-BIT INTEGERS */
INSERTION$SORT: PROCEDURE (AP, LEN);
DECLARE (AP, LEN, I, J, V, A BASED AP) ADDRESS;
DO I = 1 TO LEN-1;
V = A(I);
J = I;
DO WHILE J > 0 AND A(J-1) > V;
A(J) = A(J-1);
J = J-1;
END;
A(J) = V;
END;
END INSERTION$SORT;
/* CP/M CALLS AND FUNCTION TO PRINT INTEGERS */
BDOS: PROCEDURE (FN, ARG);
DECLARE FN BYTE, ARG ADDRESS;
GO TO 5;
END BDOS;
PRINT$NUMBER: PROCEDURE (N);
DECLARE S (7) BYTE INITIAL ('..... $');
DECLARE (N, P) ADDRESS, C BASED P BYTE;
P = .S(5);
DIGIT:
P = P-1;
C = N MOD 10 + '0';
N = N / 10;
IF N > 0 THEN GO TO DIGIT;
CALL BDOS(9, P);
END PRINT$NUMBER;
/* SORT AN ARRAY */
DECLARE NUMBERS (11) ADDRESS INITIAL (4, 65, 2, 31, 0, 99, 2, 8, 3, 782, 1);
CALL INSERTION$SORT(.NUMBERS, LENGTH(NUMBERS));
/* PRINT THE SORTED ARRAY */
DECLARE N BYTE;
DO N = 0 TO LAST(NUMBERS);
CALL PRINT$NUMBER(NUMBERS(N));
END;
CALL BDOS(0,0);
EOF</syntaxhighlight>
{{out}}
<pre>0 1 2 2 3 4 8 31 65 99 782</pre>
=={{header|PowerShell}}==
Very similar to the PHP code.
<
for($i=0;$i -lt $arr.length;$i++){
$val = $arr[$i]
Line 2,425 ⟶ 4,407:
$arr = @(4,2,1,6,9,3,8,7)
insertionSort($arr)
$arr -join ","</
{{Out}}
<pre>1,2,3,4,6,7,8,9</pre>
=={{header|Prolog}}==
<
insert_sort_intern(L1,[],L2).
Line 2,443 ⟶ 4,425:
!.
insert([H|T],X,[H|T2]) :-
insert(T,X,T2).</
% Example use:
Line 2,453 ⟶ 4,435:
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).
Line 2,472 ⟶ 4,454:
insert([H | T], N, [H|L1]) :-
insert(T, N, L1).
</syntaxhighlight>
Example use:
<pre> ?- isort([2,23,42,3,10,1,34,5],L).
Line 2,479 ⟶ 4,461:
=={{header|PureBasic}}==
<
Protected low, high
Protected firstIndex, lastIndex = ArraySize(a())
Line 2,498 ⟶ 4,480:
Wend
EndIf
EndProcedure</
=={{header|Python}}==
<
for i in xrange(1, len(
j = i-1
key =
while
j -= 1
Using pythonic iterators:
<syntaxhighlight lang="python">def insertion_sort(L):
for i, value in enumerate(L):
for j in range(i - 1, -1, -1):
if L[j] > value:
L[j + 1] = L[j]
L[j] = value</syntaxhighlight>
===Insertion sort with binary search===
<
for i in range(1, len(seq)):
key = seq[i]
Line 2,524 ⟶ 4,515:
up = middle
# insert key at position ``low``
seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]</
This is also built-in to the standard library:
<
def insertion_sort_bin(seq):
for i in range(1, len(seq)):
bisect.insort(seq, seq.pop(i), 0, i)</
=={{header|Qi}}==
Based on the scheme version.
<syntaxhighlight 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])
</syntaxhighlight>
=={{Header|Quackery}}==
<syntaxhighlight lang="quackery">[ [] swap witheach
[ swap 2dup findwith
[ over > ] [ ]
nip stuff ] ] is insertionsort ( [ --> [ )</syntaxhighlight>
=={{header|R}}==
Direct translation of pseudocode.
<
{
for(i in 2:(length(x)))
Line 2,550 ⟶ 4,561:
x
}
insertionsort(c(4, 65, 2, -31, 0, 99, 83, 782, 1)) # -31 0 1 2 4 65 83 99 782</
R has native vectorized operations which allow the following, more efficient implementation.
<syntaxhighlight lang="r">
insertion_sort <- function(x) {
for (j in 2:length(x)) {
Line 2,572 ⟶ 4,583:
}
}
</syntaxhighlight>
=={{header|Racket}}==
This implementation makes use of the pattern matching facilities in the Racket distribution.
<
#lang racket
Line 2,586 ⟶ 4,597:
[(cons y rst) (cond [(< x y) (cons x ys)]
[else (cons y (insert x rst))])]))
(foldl insert '() l))</
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>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;
</syntaxhighlight>
{{out}}
<pre>input = 22 7 2 -5 8 4
output = -5 2 4 7 8 22
</pre>
=={{header|Rascal}}==
<
public list[int] insertionSort(a){
Line 2,602 ⟶ 4,637:
}
return a;
}</
{{out}}
<
list[int]: [-31,0,1,2,4,65,83,99,782]</
=={{header|REALbasic}}==
<
for insertionElementIndex as Integer = 1 to UBound(theList)
dim insertionElement as Integer = theList(insertionElementIndex)
Line 2,618 ⟶ 4,653:
theList(j + 1) = insertionElement
next
End Sub</
=={{header|REBOL}}==
<
; This program works with REBOL version R2 and R3, to make it work with Red
; change the word func to function
Line 2,661 ⟶ 4,696:
; 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]
</syntaxhighlight>
{{out}}
Line 2,678 ⟶ 4,713:
[12-Jan-2014 11-Jan-2015 12-Jan-2015 11-Jan-2016]
</pre>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
, 7 6 5 9 8 4 3 1 2 0: e.Arr
= <Prout e.Arr>
<Prout <Sort e.Arr>>;
};
Sort {
(e.S) = e.S;
(e.S) s.I e.X = <Sort (<Insert s.I e.S>) e.X>;
e.X = <Sort () e.X>;
};
Insert {
s.N = s.N;
s.N s.M e.X, <Compare s.N s.M>: {
'+' = s.M <Insert s.N e.X>;
s.C = s.N s.M e.X;
};
};</syntaxhighlight>
{{out}}
<pre>7 6 5 9 8 4 3 1 2 0
0 1 2 3 4 5 6 7 8 9</pre>
=={{header|REXX}}==
<
call gen /*generate the array's (data) elements.*/
call show 'before sort' /*display the before array elements. */
say copies('▒', 85)
call insertionSort # /*invoke the insertion sort. */
call show ' after sort' /*display the after array elements. */
Line 2,698 ⟶ 4,757:
@.9 = "But the child that is born on the Sabbath day"
@.10 = "Is blithe and bonny, good and gay."
do #=1 while @.#\==''; end; #= #-1
return /* [↑] adjust # for the DO loop index.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
insertionSort: procedure expose @.; parse arg #
do i=2 to #; $= @.i;
_= j + 1; @._= @.j
end /*j*/
_= j + 1;
end /*i*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: do j=1 for #; say ' element' right(j,length(#)) arg(1)": " @.j; end; return</
<pre>
element 1 before sort: ---Monday's Child Is Fair of Face (by Mother Goose)---
Line 2,736 ⟶ 4,795:
=={{header|Ring}}==
<
alist = [7,6,5,9,8,4,3,1,2,0]
see insertionsort(alist)
Line 2,751 ⟶ 4,810:
next
return blist
</syntaxhighlight>
=={{header|RPL}}==
In RPL, the condition <code>while j > 0 and A[j] > value do</code> needs to be fully assessed before performing the loop: an error would then occur when j will equal zero. This is why the loop condition has been encapsulated in a <code>IFERR..THEN..END</code> structure, which removes the need to test the value of j.
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ 'A' STO
2 A SIZE '''FOR''' ii
A ii GET
ii 1 -
'''WHILE '''
'''IFERR''' DUP2 A SWAP GET < '''THEN''' 3 DROPN 0 '''END REPEAT'''
'A' OVER GETI PUT
1 -
'''END '''
'A' SWAP 1 + ROT PUT
'''NEXT '''
A 'A' PURGE
≫ 'ISORT' STO
|
''( [array] -- [array] ) ''
for i from 2 to length[A] do ''// RPL arrays starts at 1''
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
Display result and delete global variable
|}
{{in}}
<pre>
[ 1 4 -1 0 3 7 4 8 20 -6 ] ISORT
</pre>
{{out}}
<pre>
1: [ -6 -1 0 1 3 4 4 7 8 20 ]
</pre>
=={{header|Ruby}}==
<
def insertionsort!
1.upto(length - 1) do |i|
Line 2,770 ⟶ 4,874:
ary = [7,6,5,9,8,4,3,1,2,0]
p ary.insertionsort!
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</
Alternative version which doesn't swap elements but rather removes and inserts the value at the correct place:
<
def insertionsort!
1.upto(length - 1) do |i|
Line 2,787 ⟶ 4,891:
ary = [7,6,5,9,8,4,3,1,2,0]
p ary.insertionsort!
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</
=={{header|Run BASIC}}==
<
sortEnd = 0
global inSort
Line 2,820 ⟶ 4,924:
insSort(i) = x
sortEnd = sortEnd + 1
end function</
<pre>End Sort:20
1 124
Line 2,838 ⟶ 4,942:
=={{header|Rust}}==
<
for i in 1..arr.len() {
let mut j = i;
Line 2,846 ⟶ 4,950:
}
}
}</
=={{header|
Copied from SASL manual, Appendix II, answer (2)(a)
<syntaxhighlight lang="sasl">DEF
sort () = ()
sort (a : x) = insert a (sort x)
Line 2,857 ⟶ 4,960:
insert a (b : x) = a < b -> a : b : x
b : insert a x
?</
=={{header|Scala}}==
<
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)
}</
=={{header|Scheme}}==
<
(if (null? lst)
(list x)
Line 2,883 ⟶ 4,986:
(insertion-sort (cdr lst)))))
(insertion-sort '(6 8 5 9 3 2 1 4 7))</
=={{header|Seed7}}==
<
local
var integer: i is 0;
Line 2,901 ⟶ 5,004:
arr[j] := help;
end for;
end func;</
Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#insertionSort]
=={{header|Sidef}}==
<
method insertion_sort {
{ |i|
Line 2,922 ⟶ 5,025:
var a = 10.of { 100.irand }
say a.insertion_sort</
=={{header|SNOBOL4}}==
<
A = table()
i = 0
Line 2,944 ⟶ 5,047:
* output sorted data
while output = A<i>; i = ?lt(i,aSize) i + 1 :s(while)
end</
=={{header|Stata}}==
<
void insertion_sort(real vector a) {
real scalar i, j, n, x
Line 2,960 ⟶ 5,064:
}
}
end</
=={{header|Swift}}==
Using generics.
<
for i in 1..<list.count {
var j = i
Line 2,973 ⟶ 5,077:
}
}
}</
=={{header|Tcl}}==
<
proc insertionsort {m} {
Line 3,014 ⟶ 5,095:
}
puts [insertionsort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</
=={{header|TI-83 BASIC}}==
Line 3,041 ⟶ 5,122:
=={{header|uBasic/4tH}}==
<syntaxhighlight lang="text">PRINT "Insertion sort:"
n = FUNC (_InitArray)
PROC _ShowArray (n)
Line 3,089 ⟶ 5,170:
PRINT
RETURN</
=={{header|UnixPipes}}==
<
read a
test -n "$a" && ( selectionsort | sort -nm <(echo $a) -)
}</
<syntaxhighlight lang
=={{header|Ursala}}==
<
insort = ~&i&& @hNCtX ~&r->lx ^\~&rt nleq-~rlrSPrhlPrSCPTlrShlPNCTPQ@rhPlD</
test program:
<
example = insort <45,82,69,82,104,58,88,112,89,74></
{{out}}
<pre>
<45,58,69,74,82,82,88,89,104,112>
</pre>
=={{header|Vala}}==
{{trans|Nim}}
<syntaxhighlight lang="vala">void insertion_sort(int[] array) {
var count = 0;
for (int i = 1; i < array.length; i++) {
var val = array[i];
var j = i;
while (j > 0 && val < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
array[j] = val;
}
}
void main() {
int[] array = {4, 65, 2, -31, 0, 99, 2, 83, 782};
insertion_sort(array);
foreach (int i in array)
print("%d ", i);
}</syntaxhighlight>
{{out}}
<pre>
-31 0 2 2 4 65 83 99 782
</pre>
=={{header|VBA}}==
{{trans|Phix}}<syntaxhighlight lang="vb">Option Base 1
Private Function insertion_sort(s As Variant) As Variant
Dim temp As Variant
Dim j As Integer
For i = 2 To UBound(s)
temp = s(i)
j = i - 1
Do While s(j) > temp
s(j + 1) = s(j)
j = j - 1
If j = 0 Then Exit Do
Loop
s(j + 1) = temp
Next i
insertion_sort = s
End Function
Public Sub main()
s = [{4, 15, "delta", 2, -31, 0, "alpha", 19, "gamma", 2, 13, "beta", 782, 1}]
Debug.Print "Before: ", Join(s, ", ")
Debug.Print "After: ", Join(insertion_sort(s), "' ")
End Sub</syntaxhighlight>{{out}}
<pre>Before: 4, 15, delta, 2, -31, 0, alpha, 19, gamma, 2, 13, beta, 782, 1
After: -31' 0' 1' 2' 2' 4' 13' 15' 19' 782' alpha' beta' delta' gamma</pre>
=={{header|VBScript}}==
{{trans|REALbasic}}
<
Dim n(9) 'nine is the upperbound.
'since VBS arrays are 0-based, it will have 10 elements.
Line 3,147 ⟶ 5,282:
Next
End Sub
</syntaxhighlight>
{{Out}}
<pre>ORIGINAL : 26699;2643;10249;31612;21346;19702;29799;31115;20413;5197;
SORTED : 2643;5197;10249;19702;20413;21346;26699;29799;31115;31612;</pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="v (vlang)">fn insertion(mut arr []int) {
for i in 1 .. arr.len {
value := arr[i]
mut j := i - 1
for j >= 0 && arr[j] > value {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = value
}
}
fn main() {
mut arr := [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
println('Input: ' + arr.str())
insertion(mut arr)
println('Output: ' + arr.str())
}</syntaxhighlight>
{{out}}
<pre>Input: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
Output: [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]</pre>
=={{header|Wren}}==
<syntaxhighlight lang="wren">var insertionSort = Fn.new { |a|
for (i in 1..a.count-1) {
var v = a[i]
var j = i - 1
while (j >= 0 && a[j] > v) {
a[j+1] = a[j]
j = j - 1
}
a[j+1] = v
}
}
var array = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
for (a in array) {
System.print("Before: %(a)")
insertionSort.call(a)
System.print("After : %(a)")
System.print()
}</syntaxhighlight>
{{out}}
<pre>
Before: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
After : [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]
Before: [7, 5, 2, 6, 1, 4, 2, 6, 3]
After : [1, 2, 2, 3, 4, 5, 6, 6, 7]
</pre>
<br>
Alternatively we can just call a library method.
{{libheader|Wren-sort}}
<syntaxhighlight lang="wren">import "./sort" for Sort
var array = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
for (a in array) {
System.print("Before: %(a)")
Sort.insertion(a)
System.print("After : %(a)")
System.print()
}</syntaxhighlight>
{{out}}
<pre>
As above.
</pre>
=={{header|XPL0}}==
<
proc InsertionSort(A, L); \Sort array A of length L
Line 3,173 ⟶ 5,378:
InsertionSort(A, 10);
for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];
]</
{{out}}
Line 3,179 ⟶ 5,384:
-5 1 1 2 3 4 4 5 6 9
</pre>
=={{header|Yabasic}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">
sub InsertionSort (matriz())
for i = 1 to arraysize(matriz(),1)
valor = matriz(i)
j = i - 1
while (j >= 0) and (valor < matriz(j))
matriz(j + 1) = matriz(j)
j = j - 1
wend
matriz(j + 1) = valor
next i
end sub
//--------------------------
dim array(10)
print "Antes de ordenar:"
for i = 1 to 10
array(i) = int(ran(32768))
print array(i), " ";
next i
print
print "\nDespues de ordenar:"
InsertionSort(array())
for i = 1 to 10
print array(i), " ";
next i
print
end
</syntaxhighlight>
=={{header|Yorick}}==
Based on pseudocode, except using 1-based arrays.
<
for(i = 2; i <= numberof(A); i++) {
value = A(i);
Line 3,192 ⟶ 5,433:
A(j+1) = value;
}
}</
=={{header|zkl}}==
<
sink:=List();
foreach x in (list){
Line 3,202 ⟶ 5,443:
}
sink.close();
}</
<
insertionSort("big fjords vex quick waltz nymph".split()).println();</
{{out}}
<pre>
|