Simple Quick Sort in C++
分割/結合/統治というphaseを経て実行される分割統治法によって実装されるsort algorithmの一つ.似たような例にmerge sortがある.実装方法はいくつかあると思うけど,結構simpleで直感的なものを取り上げた.有名なのはHaskellのやつだけど,あれはどうやら遅いらしい.綺麗さは異次元だけど.
最良/平均時間計算量: O(N * logN)
最悪時間計算量: O(N*2)
code:cpp
void print_int_vec(const std::vector<int> &a)
{
for (auto elem : a)
{
std::cout << elem << " ";
}
std::cout << std::endl;
}
int partition(std::vector<int> &a, int start, int end)
{
int lt_pivot_count = 0;
for (int i = start + 1; i <= end; i++)
{
lt_pivot_count++;
}
int correct_pivot_idx = start + lt_pivot_count;
// set the lauout of vec like | <elements-lteq-pivot>* | pivot | <elements-gt-pivot> |
// i -> the first index of value that is mismatched position and is lt-or-eq pivot
// j -> the first index of value that is mismatched position and is gt pivot
int i = start, j = end;
while (i < correct_pivot_idx && j > correct_pivot_idx)
{
{
i++;
}
{
j--;
}
if (i < correct_pivot_idx && j > correct_pivot_idx)
{
}
}
return correct_pivot_idx;
}
void quick_sort(std::vector<int> &a, int start, int end)
{
// base case
if (start >= end)
return;
int p = partition(a, start, end);
// so we call quick_sort recursively to sort the range actually.
quick_sort(a, start, p - 1);
// the all elements in ap+1..end are just gt ap // so we call quick_sort recursively to sort the range actually.
quick_sort(a, p + 1, end);
}
int main()
{
int N;
std::cin >> N;
std::vector<int> A(N);
for (size_t i = 0; i < N; i++)
quick_sort(A, 0, N - 1);
print_int_vec(A);
return 0;
}