Sorting algorithms/Insertion sort: Difference between revisions
Content added Content deleted
imported>Tromp |
imported>StraightDoubt (Added another example for the section under AArch64 Assembly) |
||
Line 177: | Line 177: | ||
=={{header|AArch64 Assembly}}== |
=={{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 |
|||
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 lang="aarch64 assembly"> |
<syntaxhighlight lang="aarch64 assembly"> |
||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
/* ARM assembly AARCH64 Raspberry PI 3B */ |