template<class RandomIt>
void sort(RandomIt first, RandomIt last);
template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);
Jez Higgins
Freelance software grandad
software created
extended or repaired
Follow me on Mastodon
Applications, Libraries, Code
Talks & Presentations
Sunday 08 November 2020 The Forest Road Reader, No 2.56 : STinC++ - Shell sort
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.)
Shell Sort
As before, I’m going to implement a sort algorithm and put a nice C++ standard library face on it. You know, like this
std::sort
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.
How Shell Sort Works
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.
Pass One
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.
Second Pass
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.
Third Pass
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(N2) which is no better than a bubble sort. However, a bubble sort’s average complexity is also O(N2), 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.
Ok, let’s code
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?
Sort with a Sort
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
Simple insertion sort
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_sortThis 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.
Insertion sort with gap
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_sortThere 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 oopsyThe 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:
|
|
-
nextis not equal tobeginand the two values should be swapped -
swap the values
-
repoint
nextto point to the item pointed at byref -
move
refto point the prior item in the sequence, but there isn’t an item to move to becauserefis 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.
Defined behaviour
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_sortThere, all the unpleasantness is hidden away in the back_propagate function. Oh, what does that look like?
back_propagate
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_propagateThe 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.
At last, Shell sort!
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_sortThis 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.
And that’s that
Post script
How do you know your sort implementation worked when its implementation uses another sort implementation that will non-optimally 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.
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 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.
Tagged code, and software-tools-in-c++