Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

Iterative Quick Sort

, 25 Jan 2008
An iterative implementation of Quicksort
/// >IttvQuickSort.cs
///   This class implements an iterative 'QUICKSORT'. 
///   If the amount of data to be sorted is doubled then the time taken to do the sort is
/// multiplied by a constant 2.8.

using System;
using System.Collections.Generic;
using System.Text;

namespace IterativeQuickSort
{
    class IttvQuickSort
    {
        private int[] nData;
        private int nLength = 0;

        public IttvQuickSort()
        {
        }

        public IttvQuickSort(ref int[] nParaData)
        {
            this.SortData = nParaData; // ensure passed by value, not reference
        }

        public int[] SortData
        {
            set
            {
                if (value != null)
                {
                    nLength = value.GetLength(0);
                    nData = new int[nLength];
                    value.CopyTo(nData, 0);
                }
            }

            get
            {
                return nData;
            }
        }

        // Sort the whole array in ascending order
        public bool PerformSort()
        {
            bool bOK = false;

            if (nData != null)
                bOK = ExecuteActualSort(0, nData.GetUpperBound(0), true);

            return bOK;
        }

        // Sort the whole array in either ascending or descending order
        // Parameters: 
        //      bool bAscend: true  - sort in ascending order
        //                  : false - sort in descending order
        public bool PerformSort(bool bAscend)
        {
            bool bOK = false;

            if (nData != null)
                bOK = ExecuteActualSort(0, nData.GetUpperBound(0), bAscend);

            return bOK;
        }

        // Sort the array between a low and high bound in either ascending or descending order
        // Parameters: 
        //      int  nFirst : must be between 0 and the upper bound of the array.
        //                  : will be clamped to zero if out of range.
        //      int  nLast  : must be between 0 and the upper bound of the array.
        //                  : must be greater than nFirst.
        //                  : will be clamped to the upper bound of the array if out of range.
        //      bool bAscend: true  - sort in ascending order
        //                  : false - sort in descending order
        public bool PerformSort(int nFirst, int nLast, bool bAscend)
        {
            bool bOK = false;

            if (nData != null)
            {
                int nUpperBound = nData.GetUpperBound(0);

                if (nFirst < 0)
                    nFirst = 0;
                else if (nFirst > nUpperBound)
                    nFirst = 0;

                if (nLast <= nFirst)
                    nLast = nUpperBound;

                if (nLast > nUpperBound)
                    nLast = nUpperBound;

                if (nFirst < nLast)
                    bOK = ExecuteActualSort(nFirst, nLast, bAscend);
            }

            return bOK;
        }

        // 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.
        //                  : will be greater than 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;
        }
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

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

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