QuickSort and Radix Sorts on Lists

If the data is included in the nodes themselves, you need to modify the list to exchange nodes. That implies lots of pointer manipulations. On the other hand, if the data is referenced by a pointer in the list node, swapping two nodes reduces to the exchange of the two data pointers, which is faster and simpler than actually modifying the list itself.

What happens when you have a simply linked list with a pointer to the next element? QuickSort can't be applied as easily. Of course, you can promote the list to a doubly linked list, incurring complications such as reallocating new nodes, moving data, sorting, then demoting it back to a simply linked list. But there is actually a better way — radix sorting.

Radix sorting sorts an array in linear time. That is, it requires not O(n lg n) operations but O(n), with a hidden constant that doesn't depend on n at all, but on the maximum number of bits of the numbers (or keys) to sort. (For more information on radix sorting, see "QuickSort and Three-Way Radix Sorting," by Jon Bentley and Robert Sedgewick, DDJ, November 1998.) In this article, I present code and methods to QuickSort doubly linked lists, both by exchanging only the data pointer and by modifying the list itself. I also present the radix sort algorithms for arrays and simply linked lists and compare the performance of these algorithms.

QuickSorting Lists

The basic QuickSort algorithm is surprisingly simple. You start with an array of (unsorted) numbers. At each end of the array, there's a pointer — the left pointer on the left end and right pointer on the other. You first choose the pivot value; that is, a value taken at random within the array. It is important that this value be drawn from the array. You split the array into two parts, one containing only values less or equal to the pivot value, and the other with values above or equal to the pivot value. This is the "invariant" — the condition that must be satisfied at all times. You do this by advancing the left pointer while the value pointed to is less than or equal to the pivot value. The left pointer stops on a value that is greater than the pivot value. Then do the opposite with the right pointer — rewind the right pointer while the value pointed to is greater than or equal to the pivot value. The right pointer stops on a value that is less than the pivot value. Swap the values pointed to by the left and right pointers (or the nodes themselves), thus restoring the invariant. Repeat this until the right and left pointers meet. When the left and right pointers meet somewhere in the array, you are done for this step and the array is divided in two. Reapply, recursively, QuickSort on each newly created subarray. Eventually, you have to sort subarrays of length 2 or 1, which ends the recursion. After all recursive calls return, the array is completely sorted.

If the pivot value is wisely chosen, you split the array nearly in half. You then reapply QuickSort on each half. But the number of cuts is at most about lg n, which means log base 2, since you cut in half each time. QuickSort performs about O(n lg n) steps to sort an array, as long as the pivot's values are well chosen.

If the pivot value is poorly chosen, you could split the array in, say, one element on one side and (n-1) on the other. This leads to a catastrophic number of operations of (1/2)n(n+1)=O(n²) steps instead of O(n lg n) — QuickSort's worst case. To avoid this, pick the pivot value as the value that is at the center of the presently examined subarray. This even lets already sorted arrays be QuickSorted in O(n lg n) steps rather than O(n²).

ListQuickSort.cpp (available electronically; see "Resource Center," page 5) is code for QuickSorting a list. A first version, QuickSortList(cList * head, cList * tail, int count), sorts the list by changing only the node contents and without modifying the list itself. The second version, QuickSortList2(cList* &head, cList* &tail, int count), sorts the list by modifying the list itself: It leaves the node's data untouched, only modifying the way the nodes are linked together. Figure 1 shows how to rethread the list.

A Deck of Cards

To illustrate radix sorting, say you have a deck of 52 playing cards, distributed into the four usual suits (diamonds, hearts, spades, and clubs) and having the normal markings from ace to king. All cards are numbered 0 to 51 — 0 to 12 are diamonds, 13 to 25 are hearts, and so on for spades and clubs.

Assume the deck is sufficiently shuffled and you want to sort it. One possibility is to sort it using an insertion sort. You start with the unsorted deck in the right hand and, looking at the cards one by one, insert them in the right place in the sorted part of the deck that you hold in the left hand. This procedure requires essentially (1/2)n² steps to sort a deck of n cards. But there's a way to sort the cards in linear time.

Rather than using an insertion-based technique, you use a stack-based technique. In Figure 2, you distribute the unsorted deck into 13 stacks, one for each card rank. You distribute all the aces to the same stack, all the deuces to another stack, and so on, up to the stack for the kings. Eventually, all the cards are dealt to one of the 13 stacks. The next step consists of taking each of these stacks, starting with the lowest ranking stack, the aces, and redistributing all the cards into four new stacks, the stacks of suits. You start with the stack of aces. The four aces are still in some random order, but you can send each of them to the right suit stack. You do the same with deuces, and so on, up to kings. After this, each of the suit stacks contains a complete suite and a complete sorted suit. You are nearly done. All that is left to do is to combine the suit stacks to get a sorted deck. Listing One does this.

Radix Sorting Arrays

Of course, a card deck example is not especially realistic. To "sort" a deck, it suffices to fill the array with the numbers from 0 to 51. However, it does illustrate how radix sorting works. You can adapt the method to integers instead of card denominations. In the card example, the first "digit" of the card number is its rank and the second "digit" its suit. Radix sorting is all about digits of the numbers to sort. In the card example, the numbers are base-13. However, base-16 (or more) is often more suitable for sorting integers.

Radix sort on integers works much the same as on cards. Suppose you have an array filled with positive integers in some range, with at most K bits used. You treat those K-bit numbers as base-16 numbers; that is, looking at only 4 bits at a time. You need 16 stacks. Start by distributing all numbers according to their first (least significant) digit. All numbers ending in 0 (mod 16) are stacked onto stack 0, all numbers ending in 1 (mod 16) onto stack 1, and up to numbers ending in 15 (mod 16) onto the last stack, stack 15. Once all numbers have been distributed onto the stacks, unstack them into the original array. Copy the contents of each stack, at the end of each other, in the original array, but without changing the order of the contents of the stacks. Repeat the procedure, but now using the second base-16 digit of each number. Once they are all distributed, unstack them again and proceed to the third pass, using the third digit as the key. Repeat the process as many times as needed to process all the digits of the numbers. When you unstack them for the last time, they are all sorted.

This works because the unstacking is an order-preserving operation. Indeed, simply copying the contents of the stack to the array doesn't change the order of its contents. Figure 3, for instance, is a radix sort where the keys are 3 bits long and considered binary numbers. You start with the unsorted array. Scanning the array from left to right, construct two stacks — one with numbers ending in 0, the other ending in 1. When all numbers have been distributed, copy the stacks back into the array (without changing the order of the numbers as you do so). When you repeat the procedure, you still construct two stacks: The first stack contains numbers whose second bit is 0, the second contains numbers whose second bit is 1. As the ordering of the numbers is not affected by unstacking, at the beginning of the third pass, the array is filled by the numbers that end in 00, then by those that end in 01, then in 10, and finally by the numbers that end in 11. Repeat the process as many times as needed to sort all the numbers in the array. In Figure 3, you need to repeat the process three times, since the numbers are 3 bits long.

The number of times you repeat the process does not depend on the number of items in the array at all; only on the number of bits in the keys. If you treat the bits one by one and have K bits by key, the sorting process is O(Kn). That is, it needs about Kn steps to sort an array of n items. Since treating bits one by one is somewhat inefficient, treat keys by chunks of c bits. Typically, you set either c=4 or c=8. The number of steps is now (K/c)n, which is still c times better than just Kn.

Listing Two sorts an array of integers. This code doesn't literally use 2^c stacks. Instead, it interleaves multiple stacks within the same array. Figure 4 shows how it works. First, you have 2^c stack pointers that indicate where the top of each stack is in the shared array. A second array, a predecessor array, indicates the location of the predecessor for each element in the shared array. This way, you can share this array amongst many stacks without having to allocate an array for each stack. Allocating as many arrays as stacks would waste quite a lot of memory. This method only asks for a second array of integers.

The Algorithm for Lists

Okay, this algorithm is not faster than QuickSort on any reasonably sized flat array but does have a considerable advantage over QuickSort in how it scans the array.

Often it is not an array you have to sort, but a list. And often, it's a simply linked list that does not allow easy reverse scanning. That is, the only easy way to scan each of the elements is to start from the head of the list and move to the next element, one element at a time, until you reach its tail.

Should you think of using QuickSort on such a list, you would have to promote it to a doubly linked list, incurring all the complications that this situation is prone to: allocating new memory for the new nodes, copying data or at least linking to it, destroying the original list after sorting, and finally demoting the doubly linked list to a simply linked list again. That's a lot of work, besides actually sorting the list.

Radix sort naturally uses simply linked lists. ListSort.cpp (available electronically) is a C++ implementation of a radix sort on simply linked lists. Like the previous version of the algorithm, it also uses stacks. Instead of interleaving the stacks together in an array, it uses pointers to the base to the top element of each stack. Moving a list node to a stack doesn't require much of an operation: It suffices to set the "next" pointer of the topmost element of a stack to the current list node, and set the topmost pointer to this newly added element. You don't need to reallocate or move the actual node nor its contents. This is most efficient when the node's contents are large. The other advantage of using such a stack is that the unstacking costs just about nothing: To unstack, it's enough to make the last element of stack 0 point to the first element of stack 1, the last element of stack 1 point to the first element of stack 2, and so on until all of the stacks have been "sewn" together effortlessly. This means that the cost of unstacking is proportional to the number of stacks and not of elements that they contain. Figure 5 shows the process of sewing stacks together. The "sewn together" stacks become the list on which you iterate the algorithm until all bits of the keys are processed.

Speed Comparison

Table 1 compares the timings resulting from the algorithms and their variations. I used a Toshiba 2510 laptop with a 266-MHz Pentium Pro processor as the workbench. The timings are precise within about 10 ms (this is clock()'s usual granularity). The radix sort beats QuickSort on lists of 100,000 elements and more. Here, a 1 million element list takes 3.84 seconds to be sorted, while the QuickSort variation that doesn't modify the list structure takes 5.44 seconds. The QuickSort variation that actually modifies the list is far behind at 14.53 seconds.

Conclusion

The radix sort algorithm is much slower than QuickSort when applied to unsorted numbers contained within a flat array, but proves itself useful when dealing with lists whose keys are integers. The way it scans the list — forward only — makes it more suitable than QuickSort for simple lists. Furthermore, radix sorting is faster than QuickSort on very large lists. This is additional proof that the algorithm alone isn't everything. QuickSort, powerful on flat arrays, leaves something to be desired on linked lists. Radix sort, on the other hand, is well suited for linked lists.

DDJ

Listing One

#include <stdlib.h>
#include <stdio.h>
template <typename T> void swap(T & a, T & b) { T t=a; a=b; b=t; }
///////////////////////////////////////
int rank(int i) { return i % 13; }
int suit(int i) { return i / 13; }

///////////////////////////////////////
void SortDeck(int deck[52])
 {
  int rank_stack_ptr[13];
  int suit_stack_ptr[4];
  int rank_stack[13][4];
  int suit_stack[4][13];
  // hash by rank
  for (int r=0; r<13; r++) rank_stack_ptr[r]=0;
  for (int i=0; i<52; i++)
   {
    int r = rank( deck[i] );
    rank_stack[ r ][ rank_stack_ptr[r]++ ] = deck[i];
   }
  // hash by suite
  for (int s=0; s<4; s++) suit_stack_ptr[s]=0;
  for (int i=0; i<13; i++)
   for (int j=0; j<4; j++)
    {
     int s = suit( rank_stack[i][j] );
     suit_stack[ s ] [ suit_stack_ptr[s]++] = rank_stack[i][j];
    }
  // copy cards backs into the deck
  for (int d=0, i=0; i<4; i++)
   for (int j=0; j<13; j++, d++)
    deck[d] = suit_stack[i][j];
  // here, deck is sorted
 }
///////////////////////////////////////
void main()
 {
  int deck[52];
  for (int i=0;i<52;i++) deck[i]=i;
  for (int i=0;i<1000;i++)
   swap(deck[rand() % 52], deck[rand() % 52]);
  SortDeck(deck);
 }

Back to Article

Listing Two

void DistributionSort4(int tas[], int l, int h, int logMax)
 {
  int head[16];
  int *stack = new int[h-l];
  int *pred  = new int[h-l];
  for (int offset=0, i=0; offset < logMax; i++, offset+=4)
   {
    for (int j=0;j<16;j++) head[j]=-1;

    for (int d=0,j=l;j<h;j++,d++)
     {
      int s = (tas[j] >> offset) & 0xf;
      stack[d]=tas[j];
      pred[j]=head[s];
      head[s]=d;
     }
    for (int k=h-1, j=15; j>=0; j--)
     while (head[j]!=-1)
      {
       tas[k]=stack[head[j]];
       head[j]=pred[head[j]];
       k--;
      }
   }
  delete[] stack;
  delete[] pred;
 }

Back to Article