How to resolve the algorithm Sorting Algorithms/Circle Sort step by step in the ARM Assembly programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Sorting Algorithms/Circle Sort step by step in the ARM Assembly programming language
Table of Contents
Problem Statement
Sort an array of integers (of any convenient size) into ascending order using Circlesort. In short, compare the first element to the last element, then the second element to the second last element, etc. Then split the array in two and recurse until there is only one single element in the array, like this: Repeat this procedure until quiescence (i.e. until there are no swaps). Show both the initial, unsorted list and the final sorted list. (Intermediate steps during sorting are optional.) Optimizations (like doing 0.5 log2(n) iterations and then continue with an Insertion sort) are optional. Pseudo code:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sorting Algorithms/Circle Sort step by step in the ARM Assembly programming language
Source code in the arm programming language
/* ARM assembly Raspberry PI */
/* program circleSort.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly
for the routine affichageMess conversion10
see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes */
/************************************/
.include "../constantes.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessSortOk: .asciz "Table sorted.\n"
szMessSortNok: .asciz "Table not sorted !!!!!.\n"
szMessSortBefore: .asciz "Display table before sort.\n"
sMessResult: .asciz "Value : @ \n"
szCarriageReturn: .asciz "\n"
.align 4
#TableNumber: .int 1,3,6,2,5,9,10,8,4,7
#TableNumber: .int 1,2,3,4,5,6,7,8,9,10
TableNumber: .int 9,5,12,8,2,12,6
#TableNumber: .int 10,9,8,7,6,5,4,3,2,1
.equ NBELEMENTS, (. - TableNumber) / 4
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
ldr r0,iAdrszMessSortBefore
bl affichageMess
ldr r0,iAdrTableNumber @ address number table
bl displayTable
1:
ldr r0,iAdrTableNumber @ address number table
mov r1,#0
mov r2,#NBELEMENTS -1 @ number of élements
mov r3,#0
bl circleSort
cmp r0,#0
bne 1b
ldr r0,iAdrTableNumber @ address number table
mov r1,#NBELEMENTS @ number of élements
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
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsMessResult: .int sMessResult
iAdrTableNumber: .int TableNumber
iAdrszMessSortOk: .int szMessSortOk
iAdrszMessSortNok: .int szMessSortNok
iAdrszMessSortBefore: .int szMessSortBefore
/******************************************************************/
/* 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
/******************************************************************/
/* circle sort */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first index */
/* r2 contains the last index */
/* r3 contains number of swaps */
circleSort:
push {r1-r10,lr} @ save registers
cmp r1,r2
beq 99f
mov r7,r0 @ save address
mov r8,r1 @ low
mov r9,r2 @ high
sub r4,r2,r1
lsr r4,#1
mov r10,r4 @ mid
1: @ start loop
cmp r1,r2
bge 3f
ldr r5,[r0,r1,lsl #2]
ldr r6,[r0,r2,lsl #2]
cmp r5,r6
ble 2f
str r6,[r0,r1,lsl #2] @ swap values
str r5,[r0,r2,lsl #2]
add r3,r3,#1
2:
add r1,r1,#1 @ increment lo
sub r2,r2,#1 @ decrement hi
b 1b @ and loop
3:
cmp r1,r2 @ compare lo hi
bne 4f @ not egal
ldr r5,[r0,r1,lsl #2]
add r2,r2,#1
ldr r6,[r0,r2,lsl #2]
cmp r5,r6
ble 4f
str r6,[r0,r1,lsl #2] @ swap
str r5,[r0,r2,lsl #2]
add r3,r3,#1
4:
mov r1,r8 @ low
mov r2,r10 @ mid
add r2,r2,r1
bl circleSort
mov r3,r0 @ swaps
mov r0,r7 @ table address
mov r1,r8 @ low
mov r2,r10 @ mid
add r1,r2,r1
add r1,r1,#1
mov r2,r9 @ high
bl circleSort
mov r3,r0 @ swaps
99:
mov r0,r3 @ return number swaps
100:
pop {r1-r10,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,iAdrsZoneConv
bl conversion10 @ décimal conversion
ldr r0,iAdrsMessResult
ldr r1,iAdrsZoneConv @ insert conversion
bl strInsertAtCharInc
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
iAdrsZoneConv: .int sZoneConv
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
You may also check:How to resolve the algorithm Multiplication tables step by step in the F# programming language
You may also check:How to resolve the algorithm Literals/Floating point step by step in the Fortran programming language
You may also check:How to resolve the algorithm Mandelbrot set step by step in the Dart programming language
You may also check:How to resolve the algorithm Jensen's Device step by step in the FutureBasic programming language
You may also check:How to resolve the algorithm Miller–Rabin primality test step by step in the Erlang programming language