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.<\/p>\n\n\n\n
Let’s begin by examining the QuickSort algorithm in C. Here’s a typical implementation:<\/p>\n\n\n\n
int partition(int array[], int low, int high) {\r\n int pivot = array[high];\r\n int i = (low - 1);\r\n for (int j = low; j < high; j++) {\r\n if (array[j] <= pivot) {\r\n i++;\r\n swap(&array[i], &array[j]);\r\n }\r\n }\r\n swap(&array[i + 1], &array[high]);\r\n return (i + 1);\r\n}\r\n\r\nvoid quickSort(int array[], int low, int high) {\r\n if (low < high) {\r\n int pi = partition(array, low, high);\r\n quickSort(array, low, pi - 1);\r\n quickSort(array, pi + 1, high);\r\n }\r\n}\r<\/code><\/pre>\n\n\n\nThis 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.<\/p>\n\n\n\n
QuickSort in Bare-Metal ARM Assembly<\/h3>\n\n\n\n
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:<\/p>\n\n\n\n
@ qs.s\r\n@ Kevin Siraki\r\n@ 1\/09\/2024\r\n@\r\n@ Description: A QuickSort implementation in bare-metal Raspberry Pi ARM Assembly.\r\n\r\n.data\r\n.balign 4\r\nformat: .asciz \"%d \"\r\nnew: .byte '\\n'\r\narray: .int 82, 45, 17, 64, 29, 53, 98, 12, 36, 71, 50, 24, 88, 5, 42, 67, 11, 78, 33, 60\r\n\r\n.text\r\n.global main\r\n.extern printf\r\n\r\nprint_array:\r\n push {ip, lr}\r\n mov r7, #0\r\n mov r4, r0 \t\t\t\t@ r0 contains the address of the sorted array\r\n mov r5, r1 \t\t\t\t@ r1 contains the length of the array\r\n looper:\r\n ldr r0, =format @ formatting to print\r\n ldr r1, [r4, r7, lsl #2]\r\n bl printf @ print the element\r\n add r7, #1 @ for(int i=0;i<length, i++)\r\n cmp r7, r5\r\n blt looper\r\n ldr r0, =new @ newline character\r\n bl printf\r\n pop {ip, pc}\r\n\r\nquicksort:\r\n push {r4, r5, r6, ip, lr} @ create a stack frame \r\n mov r4, r0\t\t\t\t\t@ r0 contains the address of the array\r\n mov r5, r1\t\t\t\t\t@ r1 contains the low index\r\n mov r6, r2\t\t\t\t\t@ r2 contains the high index\r\n cmp r5, r6 @ if low>high\r\n bge end @ return\r\n bl partition @ call partition subroutine\r\n mov r8, r0\t\t\t\t\t@ r8 contains the pivot index\r\n sub r8, r8, #1\t\t\t\t@ r8 contains the pivot index - 1\r\n add r9, r0, #1 \t\t\t@ r9 contains the pivot index + 1\r\n mov r0, r4 \r\n mov r1, r5 \r\n mov r2, r8\r\n bl quicksort @ left call\r\n mov r0, r4\r\n mov r1, r9\r\n mov r2, r6\r\n bl quicksort @ right call\r\nend:\r\n pop {r4, r5, r6, ip, pc} @ pop the stack, return\r\n\r\npartition:\r\n push {ip, lr}\r\n mov r4, r0\t\t\t\t\t@ r0 contains the address of the array\r\n mov r5, r1 \t\t\t\t@ r1 contains the low index\r\n mov r6, r2 \t\t\t\t@ r2 contains the high index\r\n ldr r7, [r4, r6, lsl #2] \t@ pivot = array[high]\r\n mov r8, r5 \r\n sub r8, #1 @ i = low - 1;\r\n mov r3, r5 \t\t\t\t\t@ j = low\r\nloop:\r\n ldr r9, [r4, r3, lsl #2] \t@ load array[j]\r\n cmp r9, r7 @ if(array[j]>pivot) \r\n bgt endif @ skip\r\n add r8, #1 @ i++\r\n ldr r10, [r4, r8, lsl #2] @ load array[i] into r10 (swap)\r\n str r9, [r4, r8, lsl #2] \t@ store array[j] into array[i]\r\n str r10, [r4, r3, lsl #2] @ store array[i] into array[j]\r\nendif:\r\n add r3, #1 @ for(int j=low, j<high; j++)\r\n cmp r3, r6\r\n bne loop\r\nendloop:\r\n add r8, #1\r\n ldr r9, [r4, r8, lsl #2] \t@ load the value at array[pivot index] (swap)\r\n str r7, [r4, r8, lsl #2] \t@ store the pivot into array[pivot index]\r\n str r9, [r4, r6, lsl #2] \t@ store the original value (at pivot index) into array[high]\r\n pop {ip, lr}\r\n mov r0, r8 @ return (i+1)\r\n bx lr\r\n\r\nmain: @ entry point\r\n push {ip, lr}\r\n ldr r0, =array\r\n mov r1, #0\r\n mov r2, #19\r\n bl quicksort @ quicksort(array, 0, length-1)\r\n ldr r0, =array\r\n mov r1, #20\r\n bl print_array @ print_array(array, length)\r\n pop {ip, pc}\r<\/code><\/pre>\n\n\n\n
\n\n\n\nConclusion<\/h3>\n\n\n\n
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.<\/p>\n\n\n\n
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.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_EventAllDay":false,"_EventTimezone":"","_EventStartDate":"","_EventEndDate":"","_EventStartDateUTC":"","_EventEndDateUTC":"","_EventShowMap":false,"_EventShowMapLink":false,"_EventURL":"","_EventCost":"","_EventCostDescription":"","_EventCurrencySymbol":"","_EventCurrencyCode":"","_EventCurrencyPosition":"","_EventDateTimeSeparator":"","_EventTimeRangeSeparator":"","_EventOrganizerID":[],"_EventVenueID":[],"_OrganizerEmail":"","_OrganizerPhone":"","_OrganizerWebsite":"","_VenueAddress":"","_VenueCity":"","_VenueCountry":"","_VenueProvince":"","_VenueState":"","_VenueZip":"","_VenuePhone":"","_VenueURL":"","_VenueStateProvince":"","_VenueLat":"","_VenueLng":"","_VenueShowMap":false,"_VenueShowMapLink":false,"footnotes":""},"categories":[14,6],"tags":[34,33,32,28],"class_list":["post-296","post","type-post","status-publish","format-standard","hentry","category-hardware","category-programming","tag-algorithms","tag-arm","tag-assembly","tag-raspberry-pi"],"_links":{"self":[{"href":"https:\/\/blog.kevinsiraki.com\/index.php?rest_route=\/wp\/v2\/posts\/296","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kevinsiraki.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kevinsiraki.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kevinsiraki.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kevinsiraki.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=296"}],"version-history":[{"count":1,"href":"https:\/\/blog.kevinsiraki.com\/index.php?rest_route=\/wp\/v2\/posts\/296\/revisions"}],"predecessor-version":[{"id":297,"href":"https:\/\/blog.kevinsiraki.com\/index.php?rest_route=\/wp\/v2\/posts\/296\/revisions\/297"}],"wp:attachment":[{"href":"https:\/\/blog.kevinsiraki.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=296"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kevinsiraki.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=296"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kevinsiraki.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=296"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}