Two Wrongs

(don't make a right)

Bubble Sort: Not Even Once

by ~kqr

I have just witnessed the worst thing I've ever witnessed in my programming career.

I'm not even kidding. I've seen a lot of ugly code, but this takes the prize by any measure.

I seriously hope this code was written as a joke, but even so it's not a funny one. I'm still struggling to find words, so you'll have to excuse the loose assortment of utterances in this post.

The Bug Report

A client has a database of images, categorised and tagged, such that it is easy to retrieve the image you're looking for when you need it. This system works decently well and is used by a lot of clients. Sure, the code is not the best, but it was written a long time ago and you never know what kind of compromises the programmers were forced to make.

One customer, who doesn't have a lot of images, but use the filtering function a lot, complained that it was starting to become very slow.

Since this system is so old, we're not really doing enhancements to it, but I decided to look into it anyway to see if there was some obvious, simple optimisation I could do.

I made a discovery that I wish I could un-make.

Cool Stuff

I started reading the code that filters stuff in the database and creates a list of images from it. Oh, I should mention that this is one of those old-school PHP things, where you manually construct SQL statements from multiple strings. It's not a big deal, that's kinda what you expect from these older systems.

It's not a very sophisticated system either, so I was expecting to find a string somewhere that contains text along the lines of ORDER BY and then something. Normal SQL stuff.

I didn't find that, but I did find a loop that walks through the SQL query results, assigning what's called score in the code, which seems to be a home-grown relevance ranking system. I mean, it's not necessarily the fastest or even best way to do it, but eh, not too bad. Seeing how those filtering results were scored was interesting as well.

The Descent Into Madness

Then I came across code that started with

$keepSorting = true;
while ($keepSorting) {

I figured that's where I need to look to see how the results are actually sorted. What's weird was when I got to the next line, this was what I stared at:

$keepSorting = true;
while ($keepSorting) {
    $keepSorting = false;

This was vaguely familiar. I know I've seen an algorithm that looks like that somewhere, but I couldn't quite put my finger on what it was. Either way, it wasn't too important because $keepSorting is set to true further down in the code, so the author probably knew what they were doing, even if it looks odd.

That was when I saw, a few lines further down

$tmp = $results[$i];
$results[$i] = $results[$i+1];
$results[$i+1] = $tmp;

This is code that swaps two elements next to each other in an array.

If your sorting algorithm swaps specifically two elements next to each other (which it should pretty much never do), the lines above and below better not be

if ($results[$i+1]['score'] > $results[$i]['score']) {
    $tmp = $results[$i];
    $results[$i] = $results[$i+1];
    $results[$i+1] = $tmp;
    $keepSorting = true;

This is the central part of a bubble sort. It scans through the entire array many times, and swaps adjacent elements until the array is sorted. That is just as inefficient as it sounds. That should never be in any of your code.

Bubble sort is slow, ugly, difficult to understand and generally just completely useless. Every programmer should write it exactly zero or one times in their life, never again.

Bubble sort in production code is literally the worst thing I've seen in my programming career. Yes, it is that bad. Never do it.

The horror.

The horror.

The horror…

I can hear someone faintly in the back, "Hey, I know this one use case for bubb …"

No. Two words for you: insertion sort.

If you enjoyed this article, you might like others tagged with