## quick sort

### Data

in c++

#### Tags

exchange sort, sorting

### Source Code

``````#ifndef QUICKSORT
#define QUICKSORT

/*
Quicksort (partition-exchange sort)
----------
- Fast for large data sets
- Not stable
Time complexity:
- worst:   O(n^2)
- average: O(n*log(n))
- best:    O(n*log(n))
Space complexity:
- average: O(log n)
------------------
This implementation uses atomic swap in <algorithm.h> to implement the partition function in space.
*/

#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdlib>
using namespace std;
//use atomic swap operation to implement partitions in-place.
//return the new pivot position.
template <typename T>
typename vector<T>::iterator mypartition(typename vector<T>::iterator start, typename vector<T>::iterator end, typename vector<T>::iterator pivot) {
//make sure the range is correct
if (start >= end || pivot >= end || pivot < start) return start;

//first swap the pivot to the start position:
swap(*start, *pivot);
pivot = start;
typename vector<T>::iterator index = end - 1;
/*loop invariant:
Every item before the pivot is smaller than the pivot
Every item after the index is larger than the pivot
*/
while (index > pivot) {
if (*index >= *pivot) index = index - 1;
else {
//implement the repositioning through two swap operations.
swap(*(pivot + 1), *index);
swap(*pivot, *(pivot + 1));
pivot = pivot + 1;
}
}
return pivot;
}

template <typename T>
void quicksort(typename vector<T>::iterator start, typename vector<T>::iterator end) {
//make sure the range is correct, also serves as the base case.
if (start >= end) return;

//randomly choose a pivot position
typename vector<T>::iterator pivot = start + rand() % (end - start);
//partition, then recursively call.
pivot = mypartition<T>(start, end, pivot);
quicksort<T>(start, pivot);
quicksort<T>(pivot + 1, end);
}

#endif
``````
``````/*
Test cases for quicksort
*/

#include "quick_sort.h"
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
srand(time(NULL));
//a trivial test case
int myintp[] = {6, 7, 8, 9, 10, 5, 0, 1, 2, 3, 4};
vector<int> a(myintp, myintp + 11);
quicksort<int>(a.begin(), a.end());
for (int i = 0 ; i < a.size(); i++) cout<<a[i]<<' ';
cout<<endl;

//a large test case for randomly generated inputs
vector<int> b(10000);
for (int i = 0; i < b.size(); i++) b[i] = rand();
quicksort<int>(b.begin(), b.end());
for (int i = 0; i < b.size(); i++) cout<<b[i]<<' ';
cout<<endl;

return 0;
}
``````