template<class RandomIt>
void sort(RandomIt first, RandomIt last);
template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);
Freelance software grandad
software created
extended or repaired
Follow me on Twitter
Applications, Libraries, Code
Talks & Presentations
STinC++ rewrites the programs in Software Tools in Pascal using C++
I described last time that I was using the opening of chapter four as excuse to do something a little different. I’m going to do the same different thing again. (Although I don’t know if that means it’s still different, or is now the same? Language is so confusing.)
As before, I’m going to implement a sort algorithm and put a nice C++ standard library face on it. You know, like this
template<class RandomIt>
void sort(RandomIt first, RandomIt last);
template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);
Last time was bubble sort, this time we’ll look at Shell sort. Bubble sort is relatively easy to implement. As we run passes through the data the biggest values get carried  bubbled up  through to the end. We just keep doing that and everything drops out. It’s straightforward to understand and to visualise.
Shell sort is a little more involved.
The key idea in Shell sort, named for Donald Shell who described it in his PhD thesis in 1959, is to compare elements which are far apart first. Elements will be rapidly moved nearer to their destination. Subsequent comparisons with their nearer neighbours will then move them into place relatively quickly. We still make a number of passes though the data, but there are significantly fewer comparisons and fewer swaps than in a bubble sort or a simple insertion sort.
In each pass, we split the sequence into a number of sublists, each made of elements n apart. We sort each these sublists, using a simple insertion sort. We then reduce n and repeat the process, until n is 1 when the final pass will produce the fully sorted sequence.
To usefully visualise a Shell sort we need a few more elements than last time, so let’s put aside the dice and deal out some cards.
Let’s start with sublists formed of elements 6 apart. The first sublist will be the Three, Ace, and Jack.
We sort just those cards, giving us
We move on to our next sublist, which is the Ten and the Six
We sort those two and move on again, taking us to the Nine and Five
We continue in this way until we’ve considered all the cards
That’s the end of our first pass. It’s not immediately obvious that the cards are more sorted, although the lower value cards are mainly to the left, and the higher value cards mainly to the right.
For our second pass, we’ll reduce the gap between cards to 3. We can see there will be fewer sublists to consider than in the first pass, but each sublist will be longer. However, hopefully we won’t have to make too many swaps because our first pass has partly sorted the cards already.
That completes the second pass, and it’s looking pretty good.
For the third pass, we’ll reduce gap once more. We’ll take it to 1, so this will be our final pass.
Some of the cards  Ace, Two, Eight, and King  are already in place, and several more  Three & Four, Five & Six, and Ten  are only one position away, so we’ll only have to do a few swaps to move each card to its final place. I’ve animated this final insertion sort, highlighting compares and swaps.
Weird, huh? You can see the cards moving along into their final positions, but the sudden emergence of order always seems remarkable to me.
And that’s that. The sequence is sorted.
Sorting thirteen cards with a bubble sort would need 78 comparisons. We’ve done rather better than here. The actual number of compare and swaps depends on the gap we use in each pass, the length of the sequence, and how sorted the sequence is initially. On average, for this gap progression, as originally described by Shell, the worst case complexity is O(N^{2}) which is no better than a bubble sort. However, a bubble sort’s average complexity is also O(N^{2}), while Shell sort’s average complexity is considerably better. The gap sequence can make quite a difference, with Robert Sedgewick, who knows a thing or two about sorting algorithms, reducing the worst case complexity to O(N^{⁴⁄₃}) with two different gap sequences. There are, presumably, still PhDs to be had from studying Shell sort.
Even though Shell sort is only a small step up in complexity from bubble sort, I still had to go through the process by hand several times before it clicked. Frankly, all sort algorithms more involved than a bubble sort or insertion sort seem like magic.
I was going to record another video, but never quite managed to line everything up. Probably a good thing. I ended up writing the code in three little episodes of about a two and half hours in total, so it would probably have dragged a bit.
For the bubble sort, I focussed my tests on shaping the interface to the function. This time, I took that as a given.
template<class Iterator, class Comparator = std::less<>>
void shell_sort(Iterator begin, Iterator end, Compare comparator = Comparator()) {
}
Well, that was easy. But what goes in the function body?
Performing a Shell sort involves repeated applying insertion sort to different parts of the sequence. The insertion sorted seemed, therefore, like the place to start. Before long, I came up with this little eyesore
template<class Iterator, class Comparator = std::less<>>
void insertion_sort(Iterator begin, Iterator end, Comparator comparator = Comparator()) {
for (auto cur = begin; cur != std::prev(end); cur = std::next(cur)) {
auto ref = cur;
auto next = std::next(ref);
while ((next != begin) && comparator(*next, *ref)) {
auto prev = std::prev(ref);
std::iter_swap(ref, next);
next = ref;
ref = prev;
}
}
} // insertion_sort
This is a simple insertion sort  scan through the sequence, comparing pairs of adjacent items. When a pair need to be swapped, walk back down the sequence to see if we need to do any more swaps.
As shown above though, the Shell sort we need to consider items which are some distance apart. I did consider building a list of iterators to those items, but it was easier to pass the gap we wanted in as a parameter.
template<class Iterator, class Comparator = std::less<>>
void insertion_sort(Iterator begin, Iterator end, size_t gap, Comparator comparator = Comparator()) {
auto boundary = std::distance(begin, end)  gap;
auto cur = begin;
for (auto i = 0; i < boundary; i += gap) {
auto ref = cur;
auto next = std::next(ref, gap);
while ((next != begin) && comparator(*next, *ref)) {
auto prev = std::prev(ref, gap);
std::iter_swap(ref, next);
next = ref;
ref = prev;
}
cur = std::next(cur, gap);
}
} // insertion_sort
There were a couple of intermediate steps, but the evolution is pretty obvious. Applying this insertion sort, in the way described above, sorted the sequence in the correct way. Hurrah, I guess? Two problems  it’s ugly as hell, and it steps squarely into undefined behaviour. It might have sorted the sequence, but the presence of undefined behaviour means I can’t claim that it actually works. The naughty line of code is
auto prev = std::prev(ref); // possibly oopsy
The iterators next
and ref
point to the two values we’re looking at. If they need to be swapped, then we start checking back through the sequence to see if we need to do further swaps. Consider:


next
is not equal to begin
and the two values should be swapped
swap the values
repoint next
to point to the item pointed at by ref
move ref
to point the prior item in the sequence, but there isn’t an item to move to because ref
is already at the start of the sequence
In this case, ref
would be moved beyond the beginning of the sequence. That’s undefined behaviour and, as the old timers have it, the compiler writers are free to halt and catch fire. In practice, simply decrementing off the beginning is unlikely to be bad, but let’s not even entertain the possibility.
It took me a little while to think my way around this, but eventually I got to this. It’s longer, but I believe both correct and easier to read.
template<class Iterator, class Comparator = std::less<>>
void insertion_sort(Iterator begin, Iterator end, size_t gap, Comparator comparator = Comparator()) {
auto length = std::distance(begin, end);
if (length <= gap)
return;
auto steps = length  gap;
auto current = begin;
for (auto i = 0; i < steps; i += gap) {
auto next = std::next(current, gap);
if (comparator(*next, *current)) {
std::iter_swap(current, next);
back_propagate(current, begin, gap, comparator);
}
current = next;
}
} // insertion_sort
There, all the unpleasantness is hidden away in the back_propagate
function. Oh, what does that look like?
template<class Iterator, class Comparator>
void back_propagate(Iterator current, Iterator const begin, size_t gap, Comparator comparator) {
if (current == begin)
return;
do {
auto prev = std::prev(current, gap);
if (comparator(*current, *prev))
std::iter_swap(prev, current);
current = prev;
} while (current != begin);
} // back_propagate
The back_propagate
function is only concerned with checking to see how far back down the sequence we need to go. As soon as our current position hits the start of the sequence it bails out, so we only ever move back when it’s safe to do so. The earlier code was trying to do two similar but subtly different things, and that’s why it was broken.
Watching me go back and forth on this would have comprised about 95% of any video I’d made. With a sound insertion sort implementation, putting together the Shell sort took about three minutes.
template<class Iterator, class Comparator = std::less<>>
void shell_sort(Iterator begin, Iterator end, Comparator comparator = Comparator()) {
auto length = std::distance(begin, end);
for (auto gap = length/2; gap != 0; gap /= 2) {
auto from = begin;
for (auto offset = 0; offset != gap; ++offset, std::advance(from, 1))
insertion_sort(from, end, gap, comparator);
}
} // shell_sort
template<class Container, class Comparator = std::less<>>
void shell_sort(Container&& sample, Comparator comparator = Comparator()) {
shell_sort(std::begin(sample), std::end(sample), comparator);
} // shell_sort
This is the 'classic' Shell sort, with the gap progression of ᴺ⁄₂, ᴺ⁄₄, …, 1 first proposed by Shell. For other progressions, you’d need some different formula for gap or possibly even a look up table. I did a quick search but couldn’t find any online examples that did anything more complex than this. Now this code is part of that collection of basic Shell sorts too.
How do you know your sort implementation worked when its implementation uses another sort implementation that will nonoptimally sort the input even if you got the outer sort wrong? is an interesting question, and one I had to deal with here. In the end I did it by inspection. I put together a known test case  the hand of cards shown above  and stepped through the code in the debugger to verify each pass. If I was feeling particularly motivated, I could have put together a special test container type to help verify things. Perhaps it would record each change or count the number of assignments or something like that. Algorithmic complexity is one of those areas it’s hard to test without specialised tooling.
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 secondhand 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 a license for, because it’s gone a year already.
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.
Freelance software grandad
software created
extended or repaired
Follow me on Twitter
Applications, Libraries, Code
Talks & Presentations