Created
February 3, 2019 03:18
-
-
Save gubatron/7c659e65d19681476274abe7c39875cc to your computer and use it in GitHub Desktop.
specific quick sort implementation in C++ for a struct based array
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
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