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

Thursday 31 December 2020 The Forest Road Reader, No 2.60 : STinC++ - quick sort, part 2

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

When I headed off to bed last night, our quick sort implementation looked pretty good.

template<class Iterator>
void quick_sort(Iterator begin, Iterator end) {
  if(std::distance(begin, end) <= 1)
    return;

  auto pivot = *begin;
  auto left = std::next(begin);
  auto right = std::prev(end);

  while (left != right) {
    while ((left != right) && (*left < pivot))
      left = std::next(left);

    while ((left != right) && (*right >= pivot))
      right = std::prev(right);

    if (left != right)
      std::iter_swap(left, right);
  }

  if (*left >= pivot)
    left = std::prev(left);
  std::iter_swap(left, begin);

  quick_sort(begin, left);
  quick_sort(right, end);
} // quick_sort

Today I want to fill that out so we can pass in a custom comparator, extending the interface to match std::sort [1].

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

I’m still on my laptop, but at the dining table this morning. I have a cup of coffee on my right, and a teenager who might ask me to help with his A-level physics on my left. I’m all set.

Let’s start by getting the default comparator, std::less, into place. If the tests all still run - and, you know, they should - that’s a happy start.

Add it to the function definition first.

template<class Iterator, class Comparator = std::less<>>
void quick_sort(Iterator begin, Iterator end, Comparator comparator = Comparator()) {
  ...

And then hook it up in the body of the function, where

  while ((left != right) && (*left < pivot))
    left = std::next(left);

  while ((left != right) && (*right >= pivot))
    right = std::prev(right);

becomes

  while ((left != right) && comparator(*left, pivot))
    left = std::next(left);

  while ((left != right) && !comparator(*right, pivot))
    right = std::prev(right);

Tests pass. No A-level questions. Looking good so far.

The tests I dropped in yesterday included a set with a custom comparator. I’ll enable those and see what happens.

Sorts up, but not down

Sigh

Oh wait. I’m a twit.

  if (*left >= pivot)
    left = std::prev(left);
  std::iter_swap(left, begin);

The pivot point shuffling is no longer correct now we’ve got a comparator.

  if (!comparator(*left, pivot))
    left = std::prev(left);
  std::iter_swap(left, begin);

That helps a bit, but it wasn’t a miracle cure.

Sorts a bit more down. 10 of 17 tests now passing."
Look, Then Look Again

When I added the comparator parameter, I defaulted the value. I wanted to make the smallest possible change I could, because if I’ve learned anything over the past thirty years it’s the less I type the fewer bugs I put in the code.

Sometimes though, not typing enough will also put bugs in. Here’s one of the test failures.

---------------------------------------------------------------------------
Chapter 4 - quick sort
  reverse sort { 3, 10, 9, 12, 8, 4, 1, 6, 5, 13, 2, 7, 11 }
---------------------------------------------------------------------------
/home/jez/work/jezuk/stiX/c++/chapter_4/0_sorts/quick_sort.cpp:81
...........................................................................

/home/jez/work/jezuk/stiX/c++/chapter_4/0_sorts/quick_sort.cpp:88: FAILED:
  REQUIRE( under_test == expected )
with expansion:
  { 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 3, 1, 2 }
  ==
  { 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

If we momentarily set aside the last three values, this sequence is beautifully sorted. In ascending order. Where’s that less-than comparator coming from? It’s coming from exactly where I asked the compiler to add it for me.

  quick_sort(begin, left);
  quick_sort(right, end);

Quick sort is a recursive algorithm. If there’s a custom comparator passed in at the top, I need to pass that on down as we recurse.

  quick_sort(begin, left, comparator);
  quick_sort(right, end, comparator);
/home/jez/work/jezuk/stiX/c++/cmake-build-debug/0_quick_sort
===========================================================================
All tests passed (28 assertions in 1 test case)

Process finished with exit code 0

Hurrah. Tests - they save you from yourself.

Quick Sort

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

  auto pivot = *begin;
  auto left = std::next(begin);
  auto right = std::prev(end);

  while (left != right) {
    while ((left != right) && comparator(*left, pivot))
      left = std::next(left);

    while ((left != right) && !comparator(*right, pivot))
      right = std::prev(right);

    if (left != right)
      std::iter_swap(left, right);
  }

  if (!comparator(*left, pivot))
    left = std::prev(left);
  std::iter_swap(left, begin);

  quick_sort(begin, left, comparator);
  quick_sort(right, end, comparator);
} // quick_sort

This is, as far as my tests are telling me, a complete quick sort implementation. There’s more that could be done, especially around selecting a good pivot value. Just grabbing the first value works, but for sequences which are already sorted it’s the worst case, and it’s not great for partially sorted sequences. Robert Sedgewick, who wrote his PhD on quick sort and whose Algorithms is pretty much the standard text, proposes the median of the first, middle, and last element.

I am leaving all that good stuff to the library implementers. This is an exercise, and I am exercised. See you in the New Year, friends.

Kernighan and Plauger’s code

{ quick -- quicksort for lines }
procedure quick (var linepos : posbuf; nlines : pos; var linebuf : charbuf);
{ rquick -- recursive quicksort }
procedure rquick (lo, hi: integer);
var
  i, j : integer;
  pivline : charpos;
begin
  if (lo < hi) then begin
    i := lo;
    j := hi;
    pivline := linepos[j];  { pivot line }
    repeat
      while (i < j)
        and (cmp(linepos[i],pivline,linebuf) <= 0) do
          i := i + 1;
      while (j > i)
        and (cmp(linepos[j],pivline,linebuf) >= 0) do
          j := j - 1
      if (i < j) then     { out of order pair }
        exchange(linepos[i], linepos[j])
    until (i >= j)
    exchange(linepos[i], linepos[hi]); { move pivot to i }
    if (i - lo < hi -i) then begin
      rquick(lo, i-1);
      rquick(i+1, hi)
    end
    else begin
      rquick(i+1, hi);
      rquick(lo, i-1)
    end
  end
end;
begin
  rquick(1, nlines)
end;

Now I’ve written my own implementation, this is reassuring familiar.

I think the reason Karnighan and Plauger can swap the pivot into place without adjustment is because they use the rightmost value as the pivot [2].

They don’t explain the little if at the bottom selecting which order to recurse into the two subsequences, but I believe it’s to minimise the call stack. By recursing into the smaller subsequence first, the depth of the call tree is kept to its minimum. This isn’t something we would think about now, except in exceptionally constrained environments. However, as I was reminded by John Cowan about this time last year, by modern standards the machines Kernighan and Plauger used were constrained environments. There wasn’t a lot of memory to chuck around, so code size was important, stack space was limited. Working within those boundaries was a natural and normal thing to do.

Source Code

Source code for this little routine, indeed the whole project, is available in the stiX GitHub repository.

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 then renew a license for.

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’s what I use by default now.


2. Worked a couple of examples by hand, and this is the reason. Index i ends up pointing to a value equal to or greater than the pivot. The pivot in on the right, so the value being swapped ends up in the proper subsequence

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