GameDev.netUnderstanding the QuickSort Algorithm

The QuickSort is one of the fastest methods around for sorting an array. There are a few different versions of it floating around, and optimizations to go along with them, but this article will concentrate on what I believe to be the most straightforward and easy-to-understand method. The file that goes along with this article contains documented code examples for the QuickSort, one written in C and the other in QuickBASIC. ## How it WorksThe QuickSort is a recursive function that works using a "divide and conquer" method. It chooses one element, called the partition element, then shifts the elements of the array so that everything less than the partition element comes before it in the array, and everything greater than the partition element comes after it. The partition element is then at its permanent place in the array, and QuickSort calls itself twice: once to sort the upper half of the array, and once to sort the bottom half. A QuickSort function should take two parameters, which we’ll call A partition element is chosen. The choice is irrelevant; you can make it whatever you want. In the included code examples, I have chosen it to be the center element, or the closest integer to ( The pointers are moved in the following manner. First, The array is not sorted yet, though; only the partition element has taken its final place. So now, QuickSort calls itself twice. The first call sorts the first half of the array, which is from positions ## PerformanceWell, they don’t call it a QuickSort for nothing. :) The QuickSort is an excellent way to get things ordered in a hurry, but there are some cases where other options may be better. This algorithm is best used with large numbers of elements. If all you have is an array of twenty elements, you’ll probably be just as happy with something simple like an insertion sort, and that’s a lot easier to implement. The other case in which you may want to use another method is when you know that your data are going to be very close to sorted before applying the algorithm. In this case, the insertion sort is also a good way to go. One thing I should mention for DOS users in particular... recursive functions are a fantastic way to run out of stack space. :) So don’t be surprised if you try to QuickSort 20,000 integers and you come up against a memory problem! This is another time when it would be best to find another sort routine, one that is non-recursive. A shell sort might be a good option here. This is my first attempt at an article for GameDev.net, so let me know how I’m doing! Send questions, comments, or hate mail to jdfarrell@students.wisc.edu.
© 1999-2011 Gamedev.net. All rights reserved. |