Skip to content

Instantly share code, notes, and snippets.

@gubatron
Created February 3, 2019 03:18
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gubatron/7c659e65d19681476274abe7c39875cc to your computer and use it in GitHub Desktop.
Save gubatron/7c659e65d19681476274abe7c39875cc to your computer and use it in GitHub Desktop.
specific quick sort implementation in C++ for a struct based array
void quickSort(wordItem arr[], int length, bool reverse) {
if (length <= 1) {
return;
}
const int pivot_count = arr[length / 2].count;
int smaller_length = 0;
int bigger_length = 0;
int equal_length = 0;
for (int i = 0; i < length; i++) {
if (!reverse) {
if (arr[i].count < pivot_count) smaller_length++;
if (arr[i].count > pivot_count) bigger_length++;
} else {
if (arr[i].count > pivot_count) smaller_length++;
if (arr[i].count < pivot_count) bigger_length++;
}
if (arr[i].count == pivot_count) equal_length++;
}
auto smaller = new wordItem[smaller_length];
auto bigger = new wordItem[bigger_length];
auto equal = new wordItem[equal_length];
int smaller_i = 0;
int bigger_i = 0;
int equal_i = 0;
// comparisons, this part should be pluggable to make this generic
for (int i = 0; i < length; i++) {
if (!reverse) {
if (arr[i].count < pivot_count) smaller[smaller_i++] = arr[i];
if (arr[i].count > pivot_count) bigger[bigger_i++] = arr[i];
} else {
if (arr[i].count > pivot_count) smaller[smaller_i++] = arr[i];
if (arr[i].count < pivot_count) bigger[bigger_i++] = arr[i];
}
if (arr[i].count == pivot_count) equal[equal_i++] = arr[i];
}
quickSort(smaller, smaller_length, reverse);
quickSort(bigger, bigger_length, reverse);
int j = 0;
// now overwrite the original array with:
// smaller + equal + bigger
for (int i = 0; i < smaller_length; i++) arr[j++] = smaller[i];
for (int i = 0; i < equal_length; i++) arr[j++] = equal[i];
for (int i = 0; i < bigger_length; i++) arr[j++] = bigger[i];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment