5

In the recursion section of K&R's ANSI C book, they demonstrate a

version of quicksort [that] is not the fastest possible, but it's one of the simplest.

--The C Programming Language (ANSI C) - pg. 87

In its entirety:

/*qsort: sort v[left]...v[right] into increasing order*/
void qsort(int v[], int left, int right){

  int i, last;

  /*do nothing if array has less than 2 elements*/      
  if(left >= right)
    return;

  swap(v, left, (left + right) / 2); 
  last = left;

  /*partition*/
  for(i = left + 1; i <= right; i++)
    if(v[i] < v[left])
      swap(v, ++last, i);

  swap(v, left, last);  /*reset partition element*/
  qsort(v, left, last - 1);
  qsort(v, last + 1, right);
}

where swap(v, i, j) swaps two members of the array v.

I'm trying to figure out how this sorts the array. It looks like last is an array element that separates the array into two smaller arrays and then swapped with the left bounding element. It is then compared to all elements up to the right bound, swapping each smaller element with ++last (why?).

Finally, the partition element is swapped back in and the two subarrays are sorted separately.


If I understand the recursion correctly, this algorithm means at the end of one pass all the elements to the left of last are smaller than all the elements to the right of last. I am having trouble finding an explanation because most qsort algorithms are more complicated than this one.

  • it's lumuto partition method which is different than the original partition method given by C.A.R. Hoare. – mightyWOZ May 28 '18 at 13:06
9

The algorithm here is:

  • Take the value in the middle of the array, and move it to the front (by swapping). This value is the pivot.
  • Loop through the rest of the array. Each time you see a value less than the pivot, swap it to closer to the front of the array. Specifically we have an index (named last) that keeps track of where the last lesser value was swapped to. Each time we find a lesser value we increment it to find a spot to put that value.
  • When you reach the end, the array consists of:
    • the pivot
    • all values less than the pivot
    • all values greater than or equal to the pivot
  • Swap the pivot with the location of the last found lesser value.

At this point you know have a sub-array on either side of the pivot. To the left you have the values less than the pivot, to the right all values greater than or equal to the pivot. So you know that the pivot is in exactly the correct spot for the final sorted array. You also know that no values from either sub-array will need to swap with those on the other side. So you can now:

  • sort the left sub-array with the same algorithm
  • sort the right sub-array with the same algorithm.

Each time you recurse, you have smaller sub-arrays, so the next level of recursion is quicker. Also each time, you move one element into the correct position, before going deeper. Eventually you reach the point where there is only zero or one element in a sub-array, which of course means that sub-array is already sorted. What you end up with at any level is an element in the right spot, with a sorted sub-array of lesser values to the left, and a sorted sub-array of greater or equal values to the right, so you know the whole (sub-)array at that level is sorted.

  • Do you know what issues there are with this implementation that keep it from performing faster? – user2023861 Aug 30 '16 at 19:39
  • 1
    There are a variety of ways to speed up quicksort. None are implemented here, except picking the middle element as the pivot, which is a minor optimization over picking the first or last element as the pivot. You can improve performance by switching to a simpler non-recursive algorithm when you reach sufficiently small sub-arrays, since at a small enough size, the recursive function calls become more expensive than using a normally slower algorithm. – Kevin Cathcart Aug 30 '16 at 19:55
  • 1
    There are also better pivot selection algotithms that tend to make the sub-arrays more even in size, which speeds things up. See the Wikipedia Quicksort page which gives a fairly comprehensive overview of how such a basic implementation could be sped up. – Kevin Cathcart Aug 30 '16 at 19:58
  • This is entirely clear to me now, thanks largely to your sentence Swap the pivot with the location of the last found lesser value. Knowing why the variable is named last cleared it all up! – user1717828 Aug 30 '16 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.