Reading Time: 3 minutes

Introduction

In this post, we’re going to be taking a look at sorting, with a particular focus on what’s known as a “Bubble Sort.”

Sorting

In computing, sorting is one of those things you rarely think about. Applications that present users with lists usually have a button to sort search results. Your Amazon or eBay searches let you sort by price or distance, for example.

Linux has a handy commandline utility called ‘sort’. Let’s say you wanted to know about a certain subset of programs you were running and you started with:

$ ps aux |grep $USER

which dumps a whole lot of information to the screen, so you start piping that through other utilities, (often called ‘filters’ when used this way,) until you come up with something like this:

$ ps aux |grep $USER| grep bin| awk '{print $11}' | awk -F '/' '{print $NF}'|sort| uniq

(Note: This is not a useful set of filters. I just cobbed it together as an example)
It works and works well, without us having to think about how a computer performs the many, many operations needed to actually do the sort.
There are many algorithms, in many different languages and perhaps the simplest is known as a Bubble Sort.

So, what’s a Bubble Sort?

A “Bubble Sort” is an algorithm where the desired results “bubble up,” based upon the comparisons you do to pairs of elements, as you iterate through a stack of numbers. Basically, you step through your array and compare each value with the adjoining value. If it’s lower, move it to the left. Keep iterating until your array is sorted:

Gary Sims, from the excellent Gary Explains channel on Youtube explains it really well here:

(If you want to play with Gary’s code, but don’t feel like typing it in, you can grab it from my Github copy of it:

$ git clone https://github.com/jimoconnell/BubbleSortSaga.git

This is really a great way to understand what happens in a bubble sort, but of course, written in python, it’s probably only useful as an educational exercise. Python, after all, is a very high level language.
Take a look at this example, written in Assembler, a very low-level computer language that’s as close to machine code as anyone is likely to be working with:
(Example code by @stephenpaulger on GitHub)

; Runs on https://schweigi.github.io/assembler-simulator/
; https://en.wikipedia.org/wiki/Bubble_sort

	MOV C, data	; C tracks the address of end
	ADD C, 16	; of the unsorted section of data.

start:
	DEC C           ; One byte is sorted each pass
	MOV D, data	; Start of the data
bubble:
	MOV A, [D]
	CMP A, [D+1]    ; Compare two adjacent values
	JNA noswap      ; jump if the don't need swapping
	MOV B, [D+1]	; swap the two values
	MOV [D+1], A
	MOV [D], B
noswap:	
	INC D		; Move along the data one byte
	CMP D, C
	JB bubble	; loop if there's more unsorted data
	CMP C, data
	JNB start	; start again unless we've sorted all values.
	HLT


	DB "_______"	; Align the sorted data nicely.
data:
	DB "QWERTYUIOPASDFGH"  ; 16 characters to sort.

Even if you’ve never looked at Assembler before, with the comments, it’s not difficult to see what’s going on and that it’s not too different than Gary’s Python example.

This is all something that you could do with playing cards: take eight or so number cards from the deck and arrange them in random order, face up. Take the first two cards and compare them. If the card on the right is the lower of the two, swap the two cards. Move one spot to the right and repeat. Do this for the whole row. When you get to the far right, start again from the left and repeat the process, until you have no more cards to swap.

I hope that gives you a better understanding of one of those basic concepts that are too-often neglected in computer education.

Jim