-
-
Save byCodeXp/7e389f2f0bb09b3c2aff58b95fc10de7 to your computer and use it in GitHub Desktop.
quicksort (recursive implementation)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Quick Sort in c++ | |
// Modified from http://www.snippets.24bytes.com/2010/06/quick-sort.html | |
#include <iostream> // ostream | |
#include <vector> | |
#define SIZE 10 | |
using namespace std; | |
void print_all(vector <long unsigned int> & v) { for(unsigned int i=0; i<v.size(); i++) cout << v[i] << " ";} | |
void print(vector <long unsigned int> & v, unsigned int st, unsigned int end) { for(unsigned int i=st; i<=end; i++) cout << v[i] << " ";} | |
/* | |
Partitions the vector between indices start and end. | |
Uses the first element as pivot. | |
Precondition: | |
Postcondition: All elements smaller than or equal to the pivot | |
will be moved the left part of the vector, while the others to | |
the right. The pivot is moved to a position between the left | |
and right parts. | |
Returns: The position of the pivot after it has been moved. | |
*/ | |
int partition(vector<long unsigned int> & a, int start, int end) { | |
unsigned int pivot = a[start]; | |
unsigned int from_left = start+1; | |
unsigned int from_right = end; | |
unsigned int tmp; | |
//cout << "Vector entering partition:"; | |
//print (a,start,end); | |
//cout << endl; | |
while (from_left != from_right) { | |
if (a[from_left] <= pivot) from_left++; | |
else { | |
while (( from_left != from_right) && (pivot < a[from_right])) from_right--; | |
//cout << "swaping " << a[from_left] << " with "<< a[from_right] << endl; | |
tmp = a[from_right]; | |
a[from_right] = a[from_left]; | |
a[from_left] = tmp; | |
} | |
} | |
if (a[from_left]>pivot) from_left--; | |
a[start] = a[from_left]; | |
a[from_left] = pivot; | |
//cout << "Vector after partition: "; | |
//print (a,start,end); | |
//cout << endl; | |
return (from_left); | |
} | |
/* | |
Recursive QS function. Base case is an empty vector. | |
Precondition: | |
Postcondition: The vector that was passed as parameter will be | |
sorted in ascending order. | |
*/ | |
void quickSort(vector <long unsigned int> & a, int p, int r) { | |
if (p < r) { | |
int q = partition(a, p, r); | |
quickSort(a, p, q - 1); | |
quickSort(a, q + 1, r); | |
} | |
} | |
/* | |
Fills a vector of size SIZE with randomly generated numbers. | |
Then QuickSorts it. | |
*/ | |
int main() { | |
vector<long unsigned int> a(SIZE); | |
srand ( time(NULL) ); | |
for (long unsigned int i=0; i<SIZE; i++) a[i] = rand()%(SIZE*10); | |
quickSort(a, 0, SIZE-1); | |
print_all (a); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment