Sorting algorithms/Insertion sort: Difference between revisions
m
→{{header|Binary Lambda Calculus}}
| (12 intermediate revisions by 9 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,536 ⟶ 1,600:
</pre>
==={{header|
{{works with|BASICA}}
{{works with|
{{works with|
{{works with|VB-DOS}}
Sorts N integers in an array a() with the Insertion sort
Line 1,578 ⟶ 1,643:
</syntaxhighlight>
{{out}}
<pre>This program sorts by Insertion a list of randomly generated numbers.
Unsorted list:
Line 1,587 ⟶ 1,651:
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,648 ⟶ 1,710:
==={{header|IS-BASIC}}===
<syntaxhighlight lang="is-basic">
110 RANDOMIZE
120 NUMERIC ARRAY(5 TO 21)
Line 1,744 ⟶ 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,371 ⟶ 2,441:
.
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
print data[]
</syntaxhighlight>
Line 2,416 ⟶ 2,486:
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">import extensions;
Line 2,426 ⟶ 2,496:
insertionSort(int first, int last)
{
for(int i := first + 1
{
var entry := self[i];
Line 3,726 ⟶ 3,796:
===Swapping method===
<syntaxhighlight lang="
..
.de array
Line 4,643 ⟶ 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 5,217 ⟶ 5,311:
=={{header|Wren}}==
<syntaxhighlight lang="
for (i in 1..a.count-1) {
var v = a[i]
Line 5,229 ⟶ 5,323:
}
var
for (a in
System.print("Before: %(a)")
insertionSort.call(a)
Line 5,248 ⟶ 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)
| |||