38 lines
1.1 KiB
C
38 lines
1.1 KiB
C
|
#ifndef CHATGPT_QS_H
|
||
|
|
#define CHATGPT_QS_H
|
||
|
|
|
||
|
|
std::vector<uint32_t> gpt_quicksort(const std::vector<uint32_t> &arr) {
|
||
|
|
if (arr.size() <= 1) {
|
||
|
|
return arr;
|
||
|
|
}
|
||
|
|
|
||
|
|
uint32_t pivot = arr[arr.size() / 2];
|
||
|
|
std::vector<uint32_t> left;
|
||
|
|
std::vector<uint32_t> middle;
|
||
|
|
std::vector<uint32_t> right;
|
||
|
|
|
||
|
|
for (uint32_t x : arr) {
|
||
|
|
if (x < pivot) {
|
||
|
|
left.push_back(x);
|
||
|
|
} else if (x == pivot) {
|
||
|
|
middle.push_back(x);
|
||
|
|
} else {
|
||
|
|
right.push_back(x);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
std::vector<uint32_t> sorted_left = gpt_quicksort(left);
|
||
|
|
std::vector<uint32_t> sorted_right = gpt_quicksort(right);
|
||
|
|
|
||
|
|
// Concatenate sorted_left + middle + sorted_right
|
||
|
|
std::vector<uint32_t> result;
|
||
|
|
result.reserve(sorted_left.size() + middle.size() + sorted_right.size());
|
||
|
|
result.insert(result.end(), sorted_left.begin(), sorted_left.end());
|
||
|
|
result.insert(result.end(), middle.begin(), middle.end());
|
||
|
|
result.insert(result.end(), sorted_right.begin(), sorted_right.end());
|
||
|
|
|
||
|
|
return result;
|
||
|
|
}
|
||
|
|
|
||
|
|
#endif // CHATGPT_QS_H
|