Sorting algorithms/Insertion sort: Difference between revisions
m
→{{header|Binary Lambda Calculus}}
| (30 intermediate revisions by 17 users not shown) | |||
Line 177:
=={{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 */
Line 1,535 ⟶ 1,599:
1486 ; 9488 ; 9894 ; 17479 ; 18989 ; 23119 ; 23233 ; 24927 ; 25386 ; 26689 ;
</pre>
==={{header|GW-BASIC}}===
{{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}}===
Line 1,593 ⟶ 1,710:
==={{header|IS-BASIC}}===
<syntaxhighlight lang="is-basic">
110 RANDOMIZE
120 NUMERIC ARRAY(5 TO 21)
Line 1,620 ⟶ 1,737:
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}}==
Line 1,651 ⟶ 1,806:
<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}}==
Line 2,010 ⟶ 2,173:
(cdr sequence)
predicate)))))</syntaxhighlight>
=={{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}}==
Line 2,207 ⟶ 2,429:
<syntaxhighlight lang="text">
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 ]
print data[]
</syntaxhighlight>
Line 2,264 ⟶ 2,486:
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">import extensions;
Line 2,274 ⟶ 2,496:
insertionSort(int first, int last)
{
for(int i := first + 1
{
var entry := self[i];
Line 2,357 ⟶ 2,579:
(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}}==
Line 3,404 ⟶ 3,661:
#(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}}==
Line 3,464 ⟶ 3,739:
===Sliding method===
<syntaxhighlight lang="
..
.de array
Line 3,521 ⟶ 3,796:
===Swapping method===
<syntaxhighlight lang="
..
.de array
Line 3,698 ⟶ 3,973:
{{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}}==
Line 3,727 ⟶ 4,051:
=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">let rec insert lst x =
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 3,870 ⟶ 4,195:
=={{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}}==
Line 4,345 ⟶ 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}}==
Line 4,419 ⟶ 4,811:
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}}==
Line 4,874 ⟶ 5,311:
=={{header|Wren}}==
<syntaxhighlight lang="
for (i in 1..a.count-1) {
var v = a[i]
Line 4,886 ⟶ 5,323:
}
var
for (a in
System.print("Before: %(a)")
insertionSort.call(a)
Line 4,905 ⟶ 5,342:
Alternatively we can just call a library method.
{{libheader|Wren-sort}}
<syntaxhighlight lang="
var
for (a in
System.print("Before: %(a)")
Sort.insertion(a)
| |||