#include <iostream>
#include <vector>
using namespace std;
vector<int> a;
int partition(int start, int end) {
int pivot = a[end], pindex = start;
for (int i = start; i < end; i++) {
if (a[i] <= pivot) {
swap(a[i], a[pindex]);
pindex++;
}
}
swap(a[end], a[pindex]);
return pindex;
}
void quicksort(int start, int end) {
if (start >= end) {
return;
}
int pivot = partition(start, end);
quicksort(start, pivot - 1);
quicksort(pivot + 1, end);
}
int main() {
int n, x;
string s;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x;
a.push_back(x);
}
quicksort(0, (int)a.size() - 1);
for (int i = 0; i < n; i++) {
cout << a[i] << ' ';
}
return 0;
}
-
Работает медленно всегда? Или иногда?– Stanislav Volodarskiy18 сен в 22:00
-
Quicksort имеет право работать медленно (за квадрат) для некоторых массивов. Подумайте каким должне быть массив, чтобы ваш алгоритм работал как можно медленнее.– Stanislav Volodarskiy18 сен в 22:22
Добавить комментарий
|