15,169,285 members
Articles / Programming Languages / C#
Article
Posted 25 Jan 2008

56K views
14 bookmarked

# Iterative Quick Sort

Rate me:
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.

C#
/// 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)

## Share

 Software Developer United Kingdom
No Biography provided

 First Prev Next
 Descending does not work Member 320393823-Mar-12 1:37 Member 3203938 23-Mar-12 1:37
 int nStackMax = (int)((Math.Log(nLast) + 3) * 2); // from Knuth Vol 3. riccardo682-Mar-12 5:42 riccardo68 2-Mar-12 5:42
 Re: int nStackMax = (int)((Math.Log(nLast) + 3) * 2); // from Knuth Vol 3. Pete Goodsall3-Mar-12 1:47 Pete Goodsall 3-Mar-12 1:47
 Re: int nStackMax = (int)((Math.Log(nLast) + 3) * 2); // from Knuth Vol 3. riccardo685-Mar-12 1:08 riccardo68 5-Mar-12 1:08
 I apologize but sometimes it breaks preallocated stack size riccardo682-Mar-12 5:39 riccardo68 2-Mar-12 5:39
 You could try to duplicate elements (case 3) to reproduce the worse scenario: private void GenerateExampleData(int t = 0) { int i; btnDoQuickSort.Enabled = false; Cursor Csr = this.Cursor; this.Cursor = Cursors.WaitCursor; nDataSz = (int)numUpDnSz.Value; TestData = new int[nDataSz]; //---- switch (t) { case 0: { Random PRNG = new Random(System.DateTime.Now.Second); for (i = 0; i < nDataSz; i++) TestData[i] = PRNG.Next(); break; } case 1: { for (i = 0; i < nDataSz; i++) TestData[i] = i; break; } case 2: { for (i = 0; i < nDataSz; i++) TestData[i] = nDataSz - i; break; } case 3: { Random PRNG = new Random(System.DateTime.Now.Second); int nDiv = (int)numUpDnDiv.Value; for (i = 0; i < nDataSz; i++) TestData[i] = PRNG.Next() % (nDataSz / nDiv); break; } } ....
 not qsort Shona31-Jan-08 9:24 Shona 31-Jan-08 9:24
 Re: not qsort Pete Goodsall31-Jan-08 15:31 Pete Goodsall 31-Jan-08 15:31
 Last Visit: 31-Dec-99 19:00     Last Update: 18-Jan-22 15:34 Refresh 1