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

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
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.

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.

Three of Spades Ten of Spades Nine of Spades Queen of Spades Eight of Spades Four of Spades Ace of Spades Six of Spades Five of Spades King of Spades Two of Spades Seven of Spades Jack of Spades

Pass One

Let’s start with sublists formed of elements 6 apart. The first sublist will be the Three, Ace, and Jack.

Three of Spades, selected Ten of Spades Nine of Spades Queen of Spades Eight of Spades Four of Spades Ace of Spades, selected Six of Spades Five of Spades King of Spades Two of Spades Seven of Spades Jack of Spades, selected

We sort just those cards, giving us

Ace of Spades, swapped Ten of Spades Nine of Spades Queen of Spades Eight of Spades Four of Spades Three of Spades, swapped Six of Spades Five of Spades King of Spades Two of Spades Seven of Spades Jack of Spades

We move on to our next sublist, which is the Ten and the Six

Ace of Spades Ten of Spades, selected Nine of Spades Queen of Spades Eight of Spades Four of Spades Three of Spades Six of Spades, selected Five of Spades King of Spades Two of Spades Seven of Spades Jack of Spades

We sort those two and move on again, taking us to the Nine and Five

Ace of Spades Six of Spades, moved Nine of Spades, selected Queen of Spades Eight of Spades Four of Spades Three of Spades Ten of Spades, moved Five of Spades, selected King of Spades Two of Spades Seven of Spades Jack of Spades

We continue in this way until we’ve considered all the cards

Ace of Spades Six of Spades Five of Spades, moved Queen of Spades, selected Eight of Spades Four of Spades Three of Spades Ten of Spades Nine of Spades, moved King of Spades, selected Two of Spades Seven of Spades Jack of Spades

Ace of Spades Six of Spades Five of Spades Queen of Spades Eight of Spades, selected Four of Spades Three of Spades Ten of Spades Nine of Spades King of Spades Two of Spades, selected Seven of Spades Jack of Spades

Ace of Spades Six of Spades Five of Spades Queen of Spades Two of Spades, moved Four of Spades, selected Three of Spades Ten of Spades Nine of Spades King of Spades Eight of Spades, moved Seven of Spades, selected Jack of Spades

Ace of Spades Six of Spades Five of Spades Queen of Spades Two of Spades Four of Spades Three of Spades Ten of Spades Nine of Spades King of Spades Eight of Spades Seven of Spades Jack of Spades

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.

Ace of Spades, selected Six of Spades Five of Spades Queen of Spades, selected Two of Spades Four of Spades Three of Spades, selected Ten of Spades Nine of Spades King of Spades, selected Eight of Spades Seven of Spades Jack of Spades, selected

Ace of Spades Six of Spades, selected Five of Spades Three of Spades, moved Two of Spades, selected Four of Spades Jack of Spades, moved Ten of Spades, selected Nine of Spades Queen of Spades, moved Eight of Spades, selected Seven of Spades King of Spades, moved

Ace of Spades Two of Spades, moved Five of Spades, selected Three of Spades Six of Spades, moved Four of Spades, selected Jack of Spades Eight of Spades, moved Nine of Spades, selected Queen of Spades Ten of Spades, moved Seven of Spades, selected King of Spades

Ace of Spades Two of Spades Four of Spades, moved Three of Spades Six of Spades Five of Spades, moved Jack of Spades Eight of Spades Seven of Spades, moved Queen of Spades Ten of Spades Nine of Spades, moved King of Spades

That completes the second pass, and it’s looking pretty good.

Ace of Spades Two of Spades Four of Spades Three of Spades Six of Spades Five of Spades Jack of Spades Eight of Spades Seven of Spades Queen of Spades Ten of Spades Nine of Spades King of Spades

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.

A final pass through the cards

Weird, huh? You can see the cards moving along into their final positions, but the sudden emergence of order always seems remarkable to me.

Ace of Spades Two of Spades Three of Spades Four of Spades Five of Spades Six of Spades Seven of Spades Eight of Spades Nine of Spades Ten of Spades Jack of Spades Queen of Spades King of Spades

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_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.

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_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:

  [ 99, 1, ...]
    ^   ^
    !   \------ next
    +---------- ref
    !
    \---------- begin
  while ((next != begin) && comparator(*next, *ref)) { (1)
    std::iter_swap(ref, next); (2)
    next = ref; (3)
    ref = std::prev(ref); (4)
  }
  1. next is not equal to begin and the two values should be swapped

  2. swap the values

  3. repoint next to point to the item pointed at by ref

  4. 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.

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_sort

There, 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_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.

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_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.

And that’s that

Hey friends, this feels like it’s been a long one. Thanks for sticking with me. Please do get in touch by email or on Twitter if you feel so moved.

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 interest 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++


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