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.
Watch the Engine Crank

The breakpoint is set so that we don't do anything if the array we were given contains one or less elements. Because this is a recursive quicksort, this test is necessary to end recursion when an array with one element is passed in (more on this later).

After this test, we pick our pivot and move it to the beginning of the array. Click the Next button until the green arrow points to the call to the swap function. Next continues to the next line without descending into subroutine calls. Step would attempt to step into other subroutines. Now, click Next once more to see what happens.

My machine swapped the 0th and 1st elements of v[], meaning rand() % n returned 1. If you debug this program a few times you may notice that rand() % n always returns 1. Not very random, you say? In this example, by commenting out the call to srand(), the pseudo-random generator is never seeded and rand() returns predictable results.

The chosen pivot will serve to divide numbers smaller than itself from numbers larger than itself. The pivot was moved to v[0] because we don't know where it should be until we examine the entire array.

The “partition” loop steps through each element of the array and compares it to the pivot (the number 12, in my case). Last is pre-incremented, so the element at index 1 is swapped with itself (I know it's a waste). Optimizing this algorithm is left as an exercise for the masochistic reader. Note that you can click Interrupt, then Run to start over at any time.

Click Next until i equals 3 and last equals 2 (watch the Locals display in the graphical Data Window). The “if” test inside the partition loop is now comparing 18 to 12. The test fails (Next), so i is incremented (Next), and last still equals 2.

Keep Next-ing until i equals 9. My array is now { 12 6 4 3 18 27 16 15 19 }. Another click on Next and 3 is swapped with 12, seated between the smaller numbers from the larger ones.

After restoring the pivot value to its original place, we recurse into quicksort, sending a pointer to v[0] and telling it to expect a three-element array (the smaller numbers). Then we recurse into quicksort again, sending a pointer to v[4] and announcing a five-element array (the larger numbers). Those quicksort calls again recurse until only one-element arrays are passed into the recursive calls. Only then will the recursive calls return—deepest call first—until we return to the main function with a sorted array. Whew!

Handy Features

If you get deep into recursive quicksort() calls, you'll notice that the v[0]@n display is disabled. Adding a button makes re-creating this display a snap. To create the button, click Commands-->Edit Buttons...-->Data Buttons. Into the text entry field, enter:

graph display v[0]@n // Varray

A button titled Varray should pop up at the top of the Data Window. When the v[0]@n display reads (Disabled), right-click on the display and select Undisplay. Then, click the new Varray button. If it is still disabled, try Next-ing a few times and clicking the button again.

Stack Backtrace

Previously, I had you turn on the stack backtrace window. It's interesting when you're deep in quicksort() calls to examine the stack by clicking on other lines in the backtrace window. You can see how the current calling context was reached and what the data looked like at different points in the stack.

Machine Code Window

If you're really sick and twisted, try View-->Machine Code Window to see the actual assembler instructions being executed.

Other Algorithms/Data Structures to Try

DDD is great at displaying linked lists and other data structures. Try it! Also, I've mentioned that this quicksort implementation is nowhere near optimized. To see a highly optimized version, check out qsort.c in the GNU C library.

Resources

email: adamm@wazamatta.com

Adam Monsen is a recovering Pre-Med student, now a “software engineer” at a Seattle, Washington-based startup called Classmates.com. His hobbies include playing the piano, surfing and cat juggling. Adam likes coding Perl, Java and sometimes even C on his Red Hat GNU/Linux 7.3 desktop.

______________________

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