Algorithms: Quick sort

Quick Sort:

In general, quick sort has O(nlgn) running time, but in worst case, it's about O(n^2). One advantage of this sort is that it uses only exchange elements inside to realize the sort. In this way, it's able to sort without introducing extra memory, or the space consumption could be lower to O(1)--strictly speaking, cause backtracking is used, the stack usage is not O(1).

The general procedure is listed below (back tracking is used):

The detailed example is shown below:

/////////////////////////////////////////////////////////////////////
//codes

class Solution {

public:

       // s[first, last] -- is part of the data in s that needs to be sorted.

       vector<int> QuickSort(vector<int> s, int first, int last)

       {

              int lower = first + 1, upper = last, bound = s[(last + first) / 2];

              //put the bound (middle one) in the first place

              //to ensure that it's not moved around. Later it

              //will be moved back

              swap(s[first],s[(last+first)/2]);

              //swap according to bound

              while (lower <= upper){

                     while (s[lower] < bound){

                           lower++;

                     }

                     while (s[upper] > bound){

                           upper--;

                     }

                     if (lower < upper) swap(s[lower++], s[upper--]);

                     else lower++;

              }

           //move bound back to it's proper position

           swap(s[first], s[upper]);

              //partition and call quicksort, the previous bound is not counted in.

              if (first < upper - 1) s=QuickSort(s, first, upper-1);

              if (upper + 1 < last) s=QuickSort(s, upper + 1, last);

        return s; //up to now, the input s has been sorted!

       }

};