Click here to Skip to main content
15,867,308 members
Articles / Programming Languages / C#
Article

Iterative Quick Sort

Rate me:
Please Sign up or sign in to vote.
3.61/5 (7 votes)
25 Jan 2008CPOL3 min read 60.4K   281   14   7
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.

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)

License

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


Written By
Software Developer
United Kingdom United Kingdom
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionDescending does not work Pin
Member 320393823-Mar-12 0:37
Member 320393823-Mar-12 0:37 
Questionint nStackMax = (int)((Math.Log(nLast) + 3) * 2); // from Knuth Vol 3. Pin
riccardo682-Mar-12 4:42
professionalriccardo682-Mar-12 4:42 
AnswerRe: int nStackMax = (int)((Math.Log(nLast) + 3) * 2); // from Knuth Vol 3. Pin
Pete Goodsall3-Mar-12 0:47
Pete Goodsall3-Mar-12 0:47 
GeneralRe: int nStackMax = (int)((Math.Log(nLast) + 3) * 2); // from Knuth Vol 3. Pin
riccardo685-Mar-12 0:08
professionalriccardo685-Mar-12 0:08 
Take your time.

I am supposing that on waste case we need O(n) space ...sigh

Probably we have to use an incremental stack such as a linked list of dynamic array.

Take much more time
if you think to add the use of InsertionSort on small partitions
(Knuts suggested do it when remains 10 elements).
It reduces the probability of waste cases.

MergeSort has O(n) space cost too ... but its performance are predictable.
It is difficult find an iterative version of it .

bye
QuestionI apologize but sometimes it breaks preallocated stack size Pin
riccardo682-Mar-12 4:39
professionalriccardo682-Mar-12 4:39 
Generalnot qsort Pin
Shona31-Jan-08 8:24
Shona31-Jan-08 8:24 
GeneralRe: not qsort Pin
Pete Goodsall31-Jan-08 14:31
Pete Goodsall31-Jan-08 14:31 

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

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