Skip to content

Instantly share code, notes, and snippets.

@lawliet89
Last active October 12, 2015 23:58
Show Gist options
  • Save lawliet89/4106929 to your computer and use it in GitHub Desktop.
Save lawliet89/4106929 to your computer and use it in GitHub Desktop.
C++ Generic Quicksort
// Quicksort - see makefile for compiling options with G++.
// Will not compile in VS2012 due to initialiser syntax in main() for std::vector
#include <iostream>
#include <vector>
#include <algorithm> // Required
#include <iterator> //Required
#include <stdlib.h> // Required
#include <time.h> // Required
// Function Prototypes
int randomNumber(int start, int end); // Generate a number between start and end
// Perform QuickSort
// Data provided will be modified
template <typename Iterator> void quickSort(Iterator start, Iterator end){
int size = (end - start);
if ( size <= 0 )
return; // Base case
// Partition - in place partitioning that involves only swapping
// https://class.coursera.org/algo/lecture/preview/22 - O(n) time with no extra memory++
/*
Assume pivot is first element of array
Otherwise swap pivot with first element
Idea: Array A is in this form
pivot | < p | > p | unpartitioned/unseen
Let i = index of the first item > p
Let j = index of the first item unpartitioned
Let i = 1
Let j = 1
Let p = pivot value
for j < size
if A[i] < p
swap A[j] with A[i]
i++
swap A[0] with A[i-1]
*/
// Get pivot element
int pivotIndex = randomNumber(0, size);
typename std::iterator_traits<Iterator>::value_type pivot = *(start + pivotIndex);
if (pivotIndex != 0)
std::swap(*(start + pivotIndex), *start);
int i = 1;
for (int j = 1; j < size; j++){
if ( *(start + j) < pivot ){
std::swap( *(start+j), *(start+i));
i++;
}
}
std::swap(*start, *(start + i - 1));
quickSort(start, start+i-1);
quickSort(start+i, end);
}
int main(){
// This is C++11 syntax
// Input must be unsigned
std::vector<unsigned> input = {5,10,15,20,25,50,40,30,20,10,9524,878,17,1,99,18785,3649,164,94,
123,432,654,3123,654,2123,543,131,653,123,533,1141,532,213,2241,824,1124,42,134,411,
491,341,1234,527,388,245,1992,654,243,987};
quickSort(input.begin(), input.end());
// C++11 ranged based for loops
// http://www.cprogramming.com/c++11/c++11-ranged-for-loop.html
for (unsigned it : input){
std::cout << it << std::endl;
}
return 0;
}
// Generate a number between start and end
int randomNumber(int start, int end){
// Seed the randomiser
srand( time(NULL) );
return rand() % end + start;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment