Tuesday, December 1, 2009

Simple quicksort implementation

A simple C++ quicksort implementation. This version is not in place and therefore requires O(n) extra space...

#include "math.h"
#include <vector>
#include <iostream>

using namespace std;

template<class value_type>
void quick_sort(vector<value_type> &values,size_t start,size_t end,size_t pivot) {

vector<value_type> less;
vector<value_type> greater;

for(size_t n=start;n<end;n++) {
if(n != pivot)
if(values[n] < values[pivot]) {
less.push_back(values[n]);
} else {
greater.push_back(values[n]);
}
}

value_type pivot_temp = values[pivot];
for(size_t n=0;n<less.size();n++) {
values[n+start] = less[n];
}

values[start+less.size()] = pivot_temp;

for(size_t n=0;n<greater.size();n++) {
values[n+start+less.size()+1] = greater[n];
}

if(less.size() > 1) { quick_sort(values,start ,start+less.size(),start+(less.size()/2)); }
if(greater.size() > 1) { quick_sort(values,less.size(),end ,less.size()+(end/2) ); }
}

int main() {

vector<size_t> values;

for(size_t n=0;n<10;n++) {
values.push_back(rand());
}

cout << "start values..." << endl;
for(size_t n=0;n<values.size();n++) {
cout << "val[" << n << "]: " << values[n] << endl;
}

quick_sort(values,0,values.size(),5);
cout << "sorted values..." << endl;
for(size_t n=0;n<values.size();n++) {
cout << values[n] << endl;
}
}

No comments: