Jez Higgins

Freelance software grandad
software created
extended or repaired


Follow me on Twitter
Applications, Libraries, Code
Talks & Presentations

Hire me
Contact

Older posts are available in the archive or through tags.

Feed

Monday 14 September 2020 The Forest Road Reader, No 2.55 : STinC++ - bubble sort

STinC++ rewrites the programs in Software Tools in Pascal using C++

Here we are in Chapter 4, which is all about sorting. Rather than getting straight into usable tools, Kernighan and Plauger divert slightly from their established course. The sorting chapter isn’t, they say, about sorting algorithms per se, but about packing up a sorting algorithm so that people can use it. A well put together program will be useful and hence used, but “if a sorting program is so poorly packaged that people feel compelled to write their own …​ the quality of its sorting algorithm is surely irrelevant”. I suspect the bit about writing your own sort program might be a reflection of the culture at Bell Labs in the 70s, but the point about the importance of human interface factors - even if your user interface is a command line on the console - is well made.

Before getting into the meat of their program, they do take a page or two to recap a couple of sorting algorithms, the first being bubble sort, and the second being shell sort. They simply present the code, and then briefly describe it. I’m choosing to use these as an excuse to take a little diversion too, and to use them as the basis for a couple of exercises.

Bubble Sort

My first little exercise is writing a bubble sort with an extra C++y twist - a bubble sort implementation with the same interface as std::sort, the standard sort. Just as an aide memoire, std::sort looks like this:

std::sort [1]
template<class RandomIt>
void sort(RandomIt first, RandomIt last);

template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

std::sort is a generic function that takes a pair of iterators that delimit the sequence to be sorted. There’s an overload, which take a comparison function, should you wish to sort the sequence in the manner of your choosing.

That’s what I want my function to look like on the outside, but what goes on the inside?

How Bubble Sort Works

Here’s some random dice! We want to sort them so the lowest value is on the left, going up to the largest on the right.

a dice showing 4 a dice showing 6 a dice showing 2 a dice showing 1

Pass One

We’ll start by taking the first two dice and comparing them. We want the smaller value on the left.

a dice showing 4 a dice showing 6 a dice showing 2 a dice showing 1

Here, that’s already the case. There’s nothing to do, so we take the next pair.

a dice showing 4 a dice showing 6 a dice showing 2 a dice showing 1

These two are in the wrong order, so we swap them and move to the next pair.

a dice showing 4 a dice showing 2 a dice showing 6 a dice showing 1

This pair is also in the wrong order, so we swap those as well.

a dice showing 4 a dice showing 2 a dice showing 1 a dice showing 6

We’ve now completed one pass, and we can see the largest value - the six - has moved, been bubbled, the right and is in its proper place. Now we start again from the beginning.

Pass Two

a dice showing 4 a dice showing 2 a dice showing 1 a dice showing 6

Two is less than four, so we swap.

a dice showing 2 a dice showing 4 a dice showing 1 a dice showing 6

One is also smaller than four, so we swap this pair too.

a dice showing 2 a dice showing 1 a dice showing 4 a dice showing 6

We don’t need to compare the last pair, because we know we moved the six to the right place in the first pass. We’ve now completed the second pass, and bubbled the second largest value into its place. We go round again.

Pass Three

a dice showing 2 a dice showing 1 a dice showing 4 a dice showing 6

This time we only need to compare the first two dice. We swap them, and our sort is complete.

a dice showing 1 a dice showing 2 a dice showing 4 a dice showing 6

Sorted

Sorting four dice took three passes. The first pass had three comparisons, the second two, and the third has one comparision. That’s a pretty expensive sort, and you can see how the number of comparisions races away with larger datasets.

Live and In Colour

Rather than write an extended essay on how I wrote half a dozen lines of sorting code, I thought it might be fun - or at least a little different - to capture what I did, along with my confused looking face, in a short video.

stiX: Bubble Sort, implemented in C++ with a standard style interface
  • Bonus - see if you can spot where I was interrupted part way though

  • Bonus bonus - can you identify any of the books on the shelf behind me?

Video Postscript

While I was feeling pretty pleased with myself at the end of the video, I did do a little more work on the code afterwards.

bubble_sort.cpp
template<class Iterator, class Comparator = std::less<>>
void bubble_sort(Iterator begin, Iterator end, Comparator comparator = std::less<>()) {
  if (begin == end) return; (1)

  for (auto boundary = std::prev(end); boundary != begin; boundary = std::prev(boundary)) { (2)
    for (auto cur = begin; cur != boundary; cur = std::next(cur)) {
      auto next = std::next(cur); (3)
      if (comparator(*next, *cur)) {
        std::iter_swap(next, cur);
      } // if ...
    } // for ...
  } // for ...
}
  1. Oops! I hadn’t checked what happened with an empty sequence. It wasn’t good.

  2. Instead of calling operator-- and operator++ on the iterators, I switched instead to using std::prev and std::next. I dabbled for a while with std::advance but calling a function named advance to move an iterator backwards just seemed strange.

  3. Went back and forth trying to eliminate next, but couldn’t. Briefly considered

for (auto cur = begin, next = std::next(cur); cur != boundary; cur = std::next(cur), next = std::next(next))

but that really doesn’t help at all. It just looks so weird and uncomfortable.

There’s an optimisation we could make to detect if the sequence is sorted before needing all the passes, but it didn’t add to the fun, and it only occurred to me later.

Pretty sure this is the first time I’ve written a bubble sort, although I’m obviously in that demographic that has watched a bubble sort in action many, many times.

Reference

In everyday code, where you know the types you’re working with, let’s say you’ve got a std::vector<Something>, then you’re probably just going to call the begin and end member functions, and the iterator’s operator++. And you know, I think that’s absolutely fine. For library code though, when we can’t be as certain or when we don’t want to place unnecessary constraints on people using our code, then these little utility functions are just what we need.

Like the container and iterator utilities above, iter_swap and swap use the magic of template deduction, specialisation, and what-not to do the right thing for the types you’ve called the function with. Let’s say we’ve plugged a vector of vectors into the bubble sort. Using the classic two variable swap, each assignment is going to copy the whole vector, which is probably pretty bad in both time and space. Using iter_swap is, somewhere underneath it all, going to find the std::vector specialisation of std::swap, which is going to call the swap member function on one of those vectors, and that’s going to do it all in am exception-safe heartbeat. Chances are the compiler will inline it all too, so there won’t even be a function call overhead. If we invoke stiX::bubble_sort with a C style array of integers, the magic of std::begin and friends will generate a loop optimise for raw memory access.

Endnotes

This whole endeavour relies on Software Tools in Pascal and Software Tools, both by Brian W Kernighan and PJ Plauger. I love these books and commend them to you. They are both still in print, but new copies are, frankly, just ridiculously expensive. Happily, there are plenty of second-hand copies floating round, or you can borrow them from The Internet Archive using the links above.

For this project I’ve been using JetBrain’s CLion, which I liked enough to buy and renew, because it’s a year already, a license.

The test harness I’m using is Catch. I’ve been aware of Catch pretty much since it was first released, but this project is the first time really getting in and using it. I like it, and it’ll be my first choice in the future.

I recorded the video using OBS, with a cheap noname USB mic and an old, although perfectly servicable, Logitech C525 webcam perched precariously on the top of one of my monitors.


1. Actually this isn’t quite the full picture (and is becoming even less so as I type) but it’s near enough for this exercise.

Tagged code, and software-tools-in-c++


Jez Higgins

Freelance software grandad
software created
extended or repaired

Follow me on Twitter
Applications, Libraries, Code
Talks & Presentations

Hire me
Contact

Older posts are available in the archive or through tags.

Feed