Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
static int split(std::vector<int>& data, const int beg, const int end)
{
if (beg >= end || end <= 0)
{
return -1;
}
int idx = beg;
const int base = data[end - 1];
for (int i = beg; i < end; i++)
{
if (data[i] < base)
{
std::swap(data[i], data[idx]);
idx++;
}
}
std::swap(data[idx], data[end - 1]);
return idx;
}
static void quick_sort(std::vector<int>& data, const int beg, const int end)
{
if (beg >= end - 1)
{
return;
}
const int mid = beg + (end - beg) / 2;
const int idx = split(data, beg, end);
if (idx == -1)
{
return;
}
quick_sort(data, beg, idx);
//mid: pass
quick_sort(data, idx + 1, end);
}
static void sort(std::vector<int>& data)
{
//quick sort
{
quick_sort(data, 0, data.size());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.