Created
April 26, 2012 20:54
-
-
Save anonymous/2503116 to your computer and use it in GitHub Desktop.
Quick sort 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
#include<stdlib.h> | |
#include<string.h> | |
/** | |
* Output: lines contains the partitioned array | |
* @return the index of the pivot element | |
*/ | |
int partition(const char **lines, int start, int end) | |
{ | |
const char *temp; | |
int index; | |
int store_index = start; | |
// There is at least one element, use the last element as the pivot | |
// lines[end]: pivot element. | |
// Loop invariant: | |
// for all i : start <= i < store_index ==> lines[i] < lines[end] | |
// for all i : store_index <= i < index ==> lines[i] >= lines[end] | |
for (index = start; index < end; index++) | |
{ | |
// If current element is lower than pivot | |
// then swap it with the element at store_index | |
// and move the store_index to the right. | |
if (strcmp(lines[index], lines[end]) < 0) | |
{ | |
temp = lines[store_index]; | |
lines[store_index] = lines[index]; | |
lines[index] = temp; | |
store_index++; | |
} | |
} | |
// Now move the pivot to the right place. | |
temp = lines[end]; | |
lines[end] = lines[store_index]; | |
lines[store_index] = temp; | |
return store_index; | |
} | |
void quick_sort(const char **lines, int start, int end) | |
{ | |
// If the array to sort contains at most one element, it is | |
// already sorted. | |
if (start >= end) | |
{ | |
return; | |
} | |
// We have more than one element: partition and sort recursively. | |
else | |
{ | |
const int pivot_index = partition(lines, start, end); | |
quick_sort(lines, start, pivot_index - 1); | |
quick_sort(lines, pivot_index + 1, end); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment