QuickSort is a powerful and efficient sorting algorithm that’s widely used in computer science and software engineering. It’s known for its speed and simplicity, making it a popular choice for various applications. In this blog post, we’ll explore QuickSort’s implementation in both C and bare-metal ARM assembly language, specifically targeting Raspberry Pi.
QuickSort in C
Let’s begin by examining the QuickSort algorithm in C. Here’s a typical implementation:
int partition(int array[], int low, int high) {
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
int pi = partition(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
This C implementation of QuickSort follows the standard algorithm. It partitions the array around a chosen pivot element and recursively sorts the subarrays on either side of the pivot until the entire array is sorted.
QuickSort in Bare-Metal ARM Assembly
Now, let’s delve into the exciting world of bare-metal ARM assembly language on Raspberry Pi. Below is an ARM assembly implementation of QuickSort:
@ qs.s
@ Kevin Siraki
@ 1/09/2024
@
@ Description: A QuickSort implementation in bare-metal Raspberry Pi ARM Assembly.
.data
.balign 4
format: .asciz "%d "
new: .byte '\n'
array: .int 82, 45, 17, 64, 29, 53, 98, 12, 36, 71, 50, 24, 88, 5, 42, 67, 11, 78, 33, 60
.text
.global main
.extern printf
print_array:
push {ip, lr}
mov r7, #0
mov r4, r0 @ r0 contains the address of the sorted array
mov r5, r1 @ r1 contains the length of the array
looper:
ldr r0, =format @ formatting to print
ldr r1, [r4, r7, lsl #2]
bl printf @ print the element
add r7, #1 @ for(int i=0;i<length, i++)
cmp r7, r5
blt looper
ldr r0, =new @ newline character
bl printf
pop {ip, pc}
quicksort:
push {r4, r5, r6, ip, lr} @ create a stack frame
mov r4, r0 @ r0 contains the address of the array
mov r5, r1 @ r1 contains the low index
mov r6, r2 @ r2 contains the high index
cmp r5, r6 @ if low>high
bge end @ return
bl partition @ call partition subroutine
mov r8, r0 @ r8 contains the pivot index
sub r8, r8, #1 @ r8 contains the pivot index - 1
add r9, r0, #1 @ r9 contains the pivot index + 1
mov r0, r4
mov r1, r5
mov r2, r8
bl quicksort @ left call
mov r0, r4
mov r1, r9
mov r2, r6
bl quicksort @ right call
end:
pop {r4, r5, r6, ip, pc} @ pop the stack, return
partition:
push {ip, lr}
mov r4, r0 @ r0 contains the address of the array
mov r5, r1 @ r1 contains the low index
mov r6, r2 @ r2 contains the high index
ldr r7, [r4, r6, lsl #2] @ pivot = array[high]
mov r8, r5
sub r8, #1 @ i = low - 1;
mov r3, r5 @ j = low
loop:
ldr r9, [r4, r3, lsl #2] @ load array[j]
cmp r9, r7 @ if(array[j]>pivot)
bgt endif @ skip
add r8, #1 @ i++
ldr r10, [r4, r8, lsl #2] @ load array[i] into r10 (swap)
str r9, [r4, r8, lsl #2] @ store array[j] into array[i]
str r10, [r4, r3, lsl #2] @ store array[i] into array[j]
endif:
add r3, #1 @ for(int j=low, j<high; j++)
cmp r3, r6
bne loop
endloop:
add r8, #1
ldr r9, [r4, r8, lsl #2] @ load the value at array[pivot index] (swap)
str r7, [r4, r8, lsl #2] @ store the pivot into array[pivot index]
str r9, [r4, r6, lsl #2] @ store the original value (at pivot index) into array[high]
pop {ip, lr}
mov r0, r8 @ return (i+1)
bx lr
main: @ entry point
push {ip, lr}
ldr r0, =array
mov r1, #0
mov r2, #19
bl quicksort @ quicksort(array, 0, length-1)
ldr r0, =array
mov r1, #20
bl print_array @ print_array(array, length)
pop {ip, pc}
Conclusion
QuickSort is a versatile algorithm that can be implemented in various programming languages, including C and assembly language. While the C implementation offers readability and ease of understanding, the bare-metal ARM assembly implementation provides insight into low-level system programming and optimization.
Understanding both high-level and low-level implementations of algorithms like QuickSort can deepen your understanding of computer science concepts and improve your programming skills. Whether you’re working with C, assembly language, or any other language, mastering algorithms like QuickSort is a valuable asset in the world of software development.
Leave a Reply