Why do we use quicksort instead of heapsort?

Why isn't this quicksort working?

• We were given code for quicksort as part of a larger project and are supposed to modify it to have a random pivot value instead of using the last element, as given in the initial implementation. However, my attempt at randomizing the pivot isn't working (the original worked just fine); when I sort the sequence and output it, it gives me only some of the values in the sequence in order with extra repetitions and leaves some out. What am I doing wrong? template <typename Object, typename Comp> class QuickSort { // QuickSort class protected: Comp comp; void quickSortStep(VectorSequence<Object>& S, int leftBound, int rightBound); // recursive utility public: QuickSort() : comp() {} void sort(VectorSequence<Object>& S); // main entry point }; template <typename Object, typename Comp> void QuickSort<Object, Comp>:: // recursive portion quickSortStep(VectorSequence<Object>& S, int leftBound, int rightBound) { if (leftBound >= rightBound) return; // 0 or 1 elements /***Pivot choice 1: last element. Commented out when not in use*****************/ // Object pivot = S.atRank(rightBound).element(); // select last as pivot /*************************************... /***Pivot choice 2: random element in sequence. Commented out when not used.**************/ srand(time(NULL)); Object pivot = S.atRank(leftBound + rand()%(rightBound-leftBound + 1)).element(); /*************************************... int leftIndex = leftBound; // will scan rightward int rightIndex = rightBound - 1; // will scan leftward while (leftIndex <= rightIndex) { while ((leftIndex <= rightIndex) && // scan right to larger comp(S.atRank(leftIndex).element(), pivot) <= 0) leftIndex++; while ((rightIndex >= leftIndex) && // scan left to smaller comp(S.atRank(rightIndex).element(), pivot) >= 0) rightIndex--; if (leftIndex < rightIndex) // both elements found S.swapElements(S.atRank(leftIndex), S.atRank(rightIndex)); } // until indices cross // Shift right the right half of the sequence // instead of swapping the last element with the middle element int i = rightBound; while (i > leftIndex) { S.replaceAtRank(i, S.atRank(i-1).element()); i--; } // pivot at leftIndex S.replaceAtRank(leftIndex, pivot); // Swap the last element with the middle element //S.swapElements(S.atRank(leftIndex), S.atRank(rightBound)); quickSortStep(S, leftBound, leftIndex-1); // recur on both sides quickSortStep(S, leftIndex+1, rightBound); } template <typename Object, typename Comp> void QuickSort<Object, Comp>:: sort(VectorSequence<Object>& S) { // main entry point if (S.size() <= 1) return; // 0 or 1 elements quickSortStep(S, 0, S.size()-1); // call sort utility }

• Answer:

  I guess some thing you are missing. Usually three possibilities arises: All n-1 elements are less than pivot All the n-1 elements are more than pivot Some of the n-1 are more and some or less. In the first two cases quicksort has to be called only once. Where as in the third case quicksort has to be recusrively called on two portions. I am dont know you have taken care of this or not