Skip to content

Instantly share code, notes, and snippets.

Created April 26, 2012 20:54
Show Gist options
  • Save anonymous/2503116 to your computer and use it in GitHub Desktop.
Save anonymous/2503116 to your computer and use it in GitHub Desktop.
Quick sort implementation
#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