Understand Quicksort with DDD

Two fundamental steps in your programming education are to learn a good debugger and to understand Quicksort. Let's do them at the same time.

Sorting is one of the most common functions performed by a computer, and Quicksort is one of the most efficient ways to do it. This article demonstrates the usefulness of a graphical debugger for learning how Quicksort works.

DDD (Data Display Debugger) is a free, visual front end that can control many popular debuggers. This article uses DDD to work through a simple C implementation of Quicksort.

First, find a copy of DDD and install it. Binary and source packages are available for RPM-based distributions at rpmfind.net, and Debian packages are available at debian.org. This article was written using DDD version 3.3.1 on Red Hat 7.3. This article also makes the following assumptions: 1) you have a GNU/Linux-enhanced computer and it is plugged in; 2) you know basic C concepts including arrays, loops and recursion; and 3) you have a capable C compiler, such as GNU's GCC. Even if you don't know anything about programming, try stepping through the code anyway. It's good for you.

A Simplistic Quicksort

CAR Hoare described the Quicksort algorithm in a much-cited 1962 paper, and it is still in common use 40 years later. The divide-and-conquer approach of Quicksort is probably where it got the prefix quick; by segregating smaller elements from larger elements it eliminates the need for many comparisons. In contrast, a selection sort compares every element to every other element. This is not to say that Quicksort is always faster or that it's the best way to sort; it's simply cool to know. The implementation in this article is not an optimized or extensible quicksort. It only works on integer arrays.

This code was largely borrowed from The Practice of Programming by Brian W. Kernighan and Rob Pike:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* from: The Practice of Programming (pp: 32-34)
 *   by: Brian W. Kernighan and Rob Pike
 */
/* swap: interchange v[i] and v[j] */
void swap( int v[], int i, int j )
{
  int tmp;
  tmp = v[i];
  v[i] = v[j];
  v[j] = tmp;
}
/* quicksort: sort v[0]..v[n-1] into increasing
 * order
 */
void quicksort( int v[], int n )
{
  int i = 0, last = 0;
  if ( n <= 1 )              /* nothing to do */
    return;
  swap( v, 0, rand() % n );  /* move pivot elem
                                to v[0] */
  for ( i = 1; i < n; i++ )  /* partition */
    if ( v[i] < v[0] )
      swap( v, ++last, i );
  swap( v, 0, last );        /* restore pivot */
  quicksort( v, last );      /* sort smaller
                                values */
  quicksort( v+last+1, n-last-1 );  /* sort larger
                                       values */
}
void print_array( const int array[], int elems )
{
  int i;
  printf("{ ");
  for ( i = 0; i < elems; i++ )
    printf( "%d ", array[i] );
  printf("}\n");
}
#define NUM 9
int main( void )
{
  int arr[NUM] = { 6, 12, 4, 18, 3,
                  27, 16, 15, 19 };
  /* commented out to aid in predictability
   * srand( (unsigned int) time(NULL) ); */
  print_array(arr, NUM);
  quicksort(arr, NUM);
  print_array(arr, NUM);
  return EXIT_SUCCESS;
}
Step by Step

Save the code to a file called easy_qsort.c. Next, compile the code:

$ gcc -Wall -pedantic -ansi -o qsortof -g \
easy_qsort.c

The most important argument to GCC is notably -g, which adds debugging symbols to the code.

Try running the program to make sure everything is kosher:

$ ./qsortof
{ 6 12 4 18 3 27 16 15 19 }
{ 3 4 6 12 15 16 18 19 27 }

The first line of output is the unsorted array, the second line is the array after running through the quicksort function.

So how does it work? Let's turn to our new friend DDD:

$ ddd qsortof

This should bring up DDD. Close any Tips and About:Help windows that pop up, and you should see something like Figure 1.

Figure 1. Freshly Started DDD

It would be a good idea to turn on line numbering now. Click the check box next to Display Source Line Numbers in the Edit-->Preferences-->Source menu. Now we can add a breakpoint and start debugging.

First, select the nothing to do line by clicking on its line number in the margin. Then, click the Set/Delete Breakpoint at () button, and click the Run button in the floating command tool.

At this point you should see a red stop sign at the line with the breakpoint and a green arrow on the same line (the code that is about to execute). Let's use DDD to display some inside information.

To begin, select Data-->Display Local Variables. Next, select Data-->Display Arguments, and then select Status-->Backtrace. Finally, type graph display v[0]@n into the console window, and press Enter. This displays elements 0 through n of the v[] array (see Figure 2).

Figure 2. Break at if (n <= 1)

______________________

Adam Monsen is a seasoned software engineer and FLOSS zealot. He lives with his wonderful wife and children in Seattle, Washington. He blogs semi-regularly at adammonsen.com.

White Paper
Linux Management with Red Hat Satellite: Measuring Business Impact and ROI

Linux has become a key foundation for supporting today's rapidly growing IT environments. Linux is being used to deploy business applications and databases, trading on its reputation as a low-cost operating environment. For many IT organizations, Linux is a mainstay for deploying Web servers and has evolved from handling basic file, print, and utility workloads to running mission-critical applications and databases, physically, virtually, and in the cloud. As Linux grows in importance in terms of value to the business, managing Linux environments to high standards of service quality — availability, security, and performance — becomes an essential requirement for business success.

Learn More

Sponsored by Red Hat

White Paper
Private PaaS for the Agile Enterprise

If you already use virtualized infrastructure, you are well on your way to leveraging the power of the cloud. Virtualization offers the promise of limitless resources, but how do you manage that scalability when your DevOps team doesn’t scale? In today’s hypercompetitive markets, fast results can make a difference between leading the pack vs. obsolescence. Organizations need more benefits from cloud computing than just raw resources. They need agility, flexibility, convenience, ROI, and control.

Stackato private Platform-as-a-Service technology from ActiveState extends your private cloud infrastructure by creating a private PaaS to provide on-demand availability, flexibility, control, and ultimately, faster time-to-market for your enterprise.

Learn More

Sponsored by ActiveState