0
#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;
}
2
  • Работает медленно всегда? Или иногда? 18 сен в 22:00
  • Quicksort имеет право работать медленно (за квадрат) для некоторых массивов. Подумайте каким должне быть массив, чтобы ваш алгоритм работал как можно медленнее. 18 сен в 22:22

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Посмотрите другие вопросы с метками или задайте свой вопрос.