Note: This article was first published in Hackernoon by myself. This is simply a copy of the article.
Data structures and algorithms are essential to computer science. Yes, it is true that most software engineers don’t implement them on an every day basis. However, I do strongly believe that a good foundation of data structures and algorithms can help make you a better, overall engineer.
Today I’m going to be demoing an implementation of bubble sort in assembly. To most people, the thought of this probably sounds insane. You’re probably thinking, “Why on earth would you implement an algorithm in assembly?” Well to start off, I would probably never write a production application in assembly. Compilers do a WAY better job of writing assembly than I do. However, I do think it is important to understand assembly. Most of us run commands to compile our code, and I think it’s really easy to take for granted the work the compiler is doing for us. We all use loops, conditionals, and functions on a daily basis. Have you ever taken the time to understand how these are implemented at the assembly level? Chances are, if you majored in computer science, you might have explored assembly. However, if not, keep reading!
The second question you might be asking is “Why bubble sort?” For those not familiar with algorithms, bubble sort is generally considered one of the slowest sorting algorithms out there. The only main reason I chose bubble sort is because it’s fairly easy to implement and writing these algorithms out in assembly can be pretty tricky.
The implementation below isn’t perfect. Like I said, compilers do a way better job of writing assembly than I do. The goal here was not to write a perfectly optimized algorithm in assembly. It’s simply just a demonstration and a fun weekend project if you’re a computer science geek like myself. I chose MIPS as I have the most experience writing assembly for that architecture. MIPS isn’t widely used versus things like x86 and ARM, however it’s still widely taught today.
Okay, enough talking for now. Here’s the code:
# an interative approach to bubble sort # c/c++ implementation: https://codescracker.com/cpp/program/cpp-program-bubble-sort.htm .data arr: .word 7,4,6,9,1,3 N: .word 6 .text la $s0, arr # get address of array la $s1, N # get address of N lw $s1, 0($s1) # get value of N .globl main main: add $a0, $s0, $0 # get address of arr in param1 add $a1, $s1, $0 # put value of N in param2 jal bubbleSort # sort arr jal printValues # print the values j exit # exit bubbleSort: add $sp, $sp, -8 # make room for 3 ints on stack (i, j, tmp) sw $s0, 0($sp) # i sw $s1, 4($sp) # j sw $s2, 8($sp) # tmp add $s0, $0, $0 # use i in for loop and initiate to 0 outerLoop: addi $t0, $a1, -1 # n -1 slt $t0, $s0, $t0 # i < (n - 1) beq $t0, $0, return # if false exit add $s1, $0, $0 # set j = 0 innerLoop: sub $t0, $a1, $s0 # n - i addi $t0, $t0, -1 # (n - i - 1) slt $t0, $s1, $t0 # j < (n - i - 1) beq $t0, $0, exitInner # if false go to next iteration of outer loop sll $t0, $s1, 2 # get ready to do arr[j]. Shift 4 bits cause we have ints addi $t1, $t0, 4 # get ready to do arr[j + 1]. Shift 4 bits cause we have ints add $t0, $t0, $a0 # add address of j and arr add $t1, $t1, $a0 # add address of j + 1 and arr lw $t2, 0($t0) # *arr[j] lw $t3, 0($t1) # *arr[j + 1] slt $t4, $t3, $t2 # *arr[j + 1] < *arr[j] bne $t4, $0, swap addi $s1, $s1, 1 # j++ j innerLoop exitInner: addi $s0, $s0, 1 # i++ in outerLoop j outerLoop swap: add $s2, $t2 $0 sw $t3, 0($t0) # arr[j] = arr[j+1] sw $s2, 0($t1) # arr[j + 1] = tmp addi $s1, $s1, 1 # j++ j innerLoop return: lw $s0, 0($sp) lw $s1, 4($sp) lw $s2, 8($sp) addi $sp, $sp, 8 jr $ra printValues: addi $sp, $sp, -8 # make room for i on stack sw $s0, 0($sp) # store i on stack sw $a0, 4($sp) # store base addr of arr add $s0, $0, $0 # initialize i to 0 printLoop: lw $t1, 4($sp) # get base addr of arr off stac slt $t0, $s0, $a1 # i < N beq $t0, $0, returnPrintValues sll $t0, $s0, 2 # shift 4 bytes to get next elem add $t0, $t0, $t1 # get addr of arr[i] lw $t0, 0($t0) li $v0, 1 # service 1 is print integer add $a0, $t0, $zero # get ready to print val syscall addi $s0, $s0, 1 # i++ j printLoop returnPrintValues: lw $s0, 0($sp) lw $a0, 4($sp) addi $sp, $sp, 8 # restore stack pointer jr $ra exit: li $v0, 10 # exit syscall