Data Structures - Quick Sort

Basic programming - Quick Sort

Approach:

Take one element as the pivot to separate two parts from another elements. For the convenient, we always takes the last element as the pivot.

There is a partition function, search the elements in the range [left:right - 1], if the element vec[j] is smaller than vec[piovt], call swap() for putting the smaller element to left side. On the contrary, put the larger element to right side.

Finally, ++i is very important, it means shifting the index to point the right side with larger elements. And, call swap() to move pivot to the middle between left side and right side.

Time complexity:

Best Case：Ο(nlogn)

Worst Case：Ο(n²)

Average Case：Ο(nlogn)

Space complexity: O(1)

Stable/Unstable: Unstable

Source code

Version 1

#include <iostream>
#include <vector>

using namespace std;

void print(vector<int> vec){
    for(int i = 0; i < vec.size(); ++i){
        cout << vec[i] << " ";
    }
    cout << endl;
};

void swap(int& l, int& r){
    int temp = l;
    l = r;
    r = temp;
};

int partition(vector<int>& vec, int l, int r){
  int i = l - 1;
  int pivotValue = vec[r];
  for(int j = l; j < r; ++j){
      if(vec[j] < pivotValue){
          i++;
          swap(vec[i], vec[j]);
      }
  }
  ++i;
  swap(vec[i], vec[r]);
  print(vec);
  return i;
};

void quickSort(vector<int>& vec, int l, int r){
    if(l < r){
        int pivot = partition(vec, l, r);
        quickSort(vec, l, pivot - 1);
        quickSort(vec, pivot + 1, r);
    }
};

int main()
{
    vector<int> vec = {65,54,35,93,99,40,46,64,76,15};
    quickSort(vec, 0, vec.size() - 1);
    
    cout << "Final answer:" << endl;
    print(vec);

    return 0;
}