12,297,165 members (63,705 online)

36.1K views
14 bookmarked
Posted

# Iterative Quick Sort

, 25 Jan 2008 CPOL
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; } } } ```

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.