12,304,322 members (68,123 online)
Add your own
alternative version

36.2K views
232 downloads
14 bookmarked
Posted

# Iterative Quick Sort

, 25 Jan 2008 CPOL
 Rate this:
Please Sign up or sign in to vote.
An iterative implementation of Quicksort

## Introduction

This article was originally written in response to a discussion initiated by GurliGebis within the interesting article The ELMO Principle - Part 2 - Sorting Algorithms by UsualDosage. GurliGebis asked why Quicksort was not included to be tested. UsualDosage did not cover Quicksort, as he said that he was testing only non-recursive sorting algorithms. As I show here, there is no reason why Quicksort cannot be implemented iteratively and, indeed, such an implementation can show significant speed and memory-overhead advantages over a recursive implementation.

## Background

First off, I should say that I am not talking about the simple conversion of a recursive algorithm to an iterative implementation. Early versions of BASIC that some of us are unfortunately old enough to remember did not implement recursion and, as a consequence, if a recursive algorithm had to be implemented in these languages, then programmers would simply copy it and use explicit stack operations to mimic the recursive calls.

With Quicksort, although this can of course be done (any recursive algorithm can be converted to an iterative equivalent; whether it's a good idea or not is another matter!), it turns out that there are significant advantages in terms of both memory utilisation and, for typical input data, speed, if a modified iterative implementation is provided that does not have a direct recursive equivalent.

The advantages of using an explicit stack and iteration in place of a recursive implementation are essentially three-fold:

1. Using an explicit stack allows the sort to avoid the temporary storage of unnecessary information.
2. Rather than placing two partitions on a stack in arbitrary order, as a typical recursive Quicksort would implicitly do, the sizes of the partitions are checked first and the pointers indicating the larger of the two are stacked. The smaller partition's pointers are not stacked at all: we are able to do this since we can guarantee that the smaller partition would always be equivalent to the second recursive call, which is at the tail-end of the function. This leads to the third advantage:
3. Any tail-end recursion can be eliminated and replaced with a simple loop.

This combination of ensuring end-recursion removal and always processing the smaller of the two partitions ensures that the stack only has to contain a maximum of O(log(n)) entries, hence the potential memory savings mentioned earlier. Note that in the worst case (in which, for example, the input data is already sorted), the stack-size for a recursive implementation would grow to be as large as the number of records in the array.

## Using the Code

The program is extremely simple to operate. Simply press the "Generate New Data" button and then "Do Sort!" Use the numeric up/down box to set the maximum number of integers to be randomly generated by pressing the generate button. The "Do Sort!" button is only enabled when a change to the input data has been completed. The radio option buttons allow the user to select whether they wish the data to be sorted in ascending or descending order.

## Code

Here is the sorting function from the `IttvQuickSort` class that actually does the work. Note that when timing, it's typically best to ignore the first run. Sorting a million integers takes an average of around half a second on my machine: AMD Sempron 2600+, 1GB memory, Windows XP SP2. Any variation is, of course, due to the order in which the input data is presented to the sort, as well as any other processes that may be calling for the processor's attention.

```/// Sort the array between a low and high bound in either ascending or descending order
/// Parameters:
///      int  nFirst : between 0 and the upper bound of the array.
///      int  nLast  : between 0 and the upper bound of the array.
///                  : must be guaranteed >= nFirst.
///      bool bAscend: true  - sort in ascending order
///                  : false - sort in descending order
private bool ExecuteActualSort(int nFirst, int nLast, bool bAscend)
{
bool bSortOK = false;

try
{
int i, j, nStkPtr = 0, nTmp;
bool bSortCompleted = false, bDirection = true;

// get the maximum size of stack required:
int nStackMax = (int)((Math.Log(nLast) + 3) * 2); // from Knuth Vol 3.
// Note, +3 is added because:
// +1 to round up rather than down,
// +1 because it's a full bottom-up stack (ie Stack[0] is never used),
// +1 because data array is zero-indexed.

int[,] nStack = new int[nStackMax, 2];

do
{
do
{
i = nFirst;
j = nLast;
bDirection = true;

do
{
if ((nData[i] > nData[j]) == bAscend)
{
// Swap the two items in the list pointed to by i and j
nTmp = nData[i];
nData[i] = nData[j];
nData[j] = nTmp;
bDirection = !bDirection;
}

if (bDirection)
j--;
else
i++;

}
while (i < j);

if (i + 1 < nLast)
{
// There's another partition to be sorted
nStkPtr++;
nStack[nStkPtr, 0] = i + 1;
nStack[nStkPtr, 1] = nLast;
}
nLast = i - 1;

}
while (nFirst < nLast);

if (nStkPtr == 0)
{
// No more partitions to sort, so by definition we've finished!
bSortCompleted = true;
}

else
{
// Pop the most recently stored partition and sort that
nFirst = nStack[nStkPtr, 0];
nLast = nStack[nStkPtr, 1];
nStkPtr--;
}
}

while (!bSortCompleted);

bSortOK = true;
}

catch { }

return bSortOK;
}```

This is a C# conversion of an iterative Quicksort that I wrote in BBC BASIC around 1988 that ran on an ARM2-based machine. However, it should be mentioned that BBC BASIC was highly advanced for its time and, ironically, given the subject matter of this article, most certainly did support recursion!

## History

• 25 January, 2008 -- First version

## References

• Knuth (1998) (2nd Ed), The Art of Computer Programming Vol. 3 pp115-123. Addison-Wesley.
• Sedgewick (1983), Algorithms pp103-113. Addison-Wesley.
• Quillinan (1985), Better BASIC pp98. Newnes. (For an example of a straight conversion without the advantages)

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

## About the Author

 Software Developer United Kingdom
No Biography provided

## Comments and Discussions

 First Prev Next
 Descending does not work Member 320393823-Mar-12 0:37 Member 3203938 23-Mar-12 0:37
 int nStackMax = (int)((Math.Log(nLast) + 3) * 2); // from Knuth Vol 3. riccardo682-Mar-12 4:42 riccardo68 2-Mar-12 4:42
 Re: int nStackMax = (int)((Math.Log(nLast) + 3) * 2); // from Knuth Vol 3. Pete Goodsall3-Mar-12 0:47 Pete Goodsall 3-Mar-12 0:47
 Re: int nStackMax = (int)((Math.Log(nLast) + 3) * 2); // from Knuth Vol 3. riccardo685-Mar-12 0:08 riccardo68 5-Mar-12 0:08
 I apologize but sometimes it breaks preallocated stack size riccardo682-Mar-12 4:39 riccardo68 2-Mar-12 4:39
 not qsort Shona31-Jan-08 8:24 Shona 31-Jan-08 8:24
 Re: not qsort Pete Goodsall31-Jan-08 14:31 Pete Goodsall 31-Jan-08 14:31
 Yes it is! If you follow the algorithm through you'll see that all it's doing is partitioning the data and finding a new pivot in each of the new partitions: a left partition containing elements < the pivot and a right partition containing elements > the pivot. Each sub-pivot is then treated in the same way until the entire array is sorted. The pointers to the beginning and end of the partition are stored on an explicit stack rather than using recursion. This is why it superficially doesn't look like a quicksort, which you typically expect to be recursive. However, although this idea leads to greater code complexity, as I detail in the article there are speed and memory advantages. See the book links I gave above for more information, or simply Google "quicksort iterative" for numerous examples.
 Last Visit: 31-Dec-99 18:00     Last Update: 31-May-16 5:29 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160530.1 | Last Updated 25 Jan 2008
Article Copyright 2008 by Pete Goodsall
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid