Click here to Skip to main content
Click here to Skip to main content

Iterative Quick Sort

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

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)

Share

About the Author

Pete Goodsall
Software Developer
United Kingdom United Kingdom
No Biography provided

Comments and Discussions

 
Generalnot qsort PinmemberShona31-Jan-08 8:24 
GeneralRe: not qsort PinmemberPete Goodsall31-Jan-08 14:31 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

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

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