Anonymous user
Sorting algorithms/Insertion sort: Difference between revisions
Sorting algorithms/Insertion sort (view source)
Revision as of 23:51, 24 February 2024
, 3 months agoAdded another example for the section under AArch64 Assembly
imported>Tromp |
imported>StraightDoubt (Added another example for the section under AArch64 Assembly) |
||
Line 177:
=={{header|AArch64 Assembly}}==
<syntaxhighlight lang="asm">
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}▼
.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
1:
// Loop test
cmp J, ARR_BEGIN
b.eq 1f
ldr INNER_TMP, [J, #-4]
cmp INNER_TMP, OUTER_TMP
b.le 1f
// Loop body
str INNER_TMP, [J], #-4
b 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 */
| |||