Задача

1/8

Быстрая сортировка: начало (Python)

Теория Нажмите, чтобы прочитать/скрыть

Быстрая сортировка

Быстрая сортировкасортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем \(O(n\log n)\) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Быстрый метод сортировки функционирует по принципу "разделяй и властвуй" (рекурсивное разбиение решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинирование их решений для получения ответа к исходной задаче).

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (например, рассмотренной нами "Пузырьковой сортировки"), известного в том числе своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. (Таким образом улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.)

Преимущества QuickSort по сравнению с другими алгоритмами быстрой сортировки заключается в том, что он не использует дополнительных массивов, сортировка происходит "на месте".

Алгоритм состоит из трёх шагов:

  1. Выбор опорного элемента из массива (X).
  2. Этап разделения. Перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные - после.
    A[i] < X
    A[i]>=X
    Теперь элементы расположены так, что ни один элемент из первой группы при сортировке не окажется во второй группе, и наоборот.
    Поэтому достаточно отсортировать отдельно каждую часть массива - это и есть подход "разделяй и властвуй".
  3. Рекурсивное применение первых двух шагов к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один или отсутствуют элементы.
Процедура сортировки должна принимать три параметра:
- массив, который сортируем;
- индекс первого элемента сортируемого участка;
- индекс последнего элемента сортируемого участка.
 
Алгоритм на псевдокоде:
АЛГ QUICKSORT(A[], START, END)
   // если условие выполняется, то в рабочей части массива 
   // меньше двух элементов,   
   // то есть сортировать уже ничего не нужно
   ЕСЛИ START >= END, ТО ВЫЙТИ ИЗ ПРОЦЕДУРЫ   
   
   // в качестве опорного элемента можно брать 
   // случайное число на отрезке сортируемого участка, 
   // можно брать средний элемент 
   X = СЛУЧАЙНЫЙ ЭЛЕМЕНТ МАССИВА НА ОТРЕЗКЕ [START; END]  
   
   L = START, R = END
   ПОКА L <= R
       // ищем элементы для перестановки
       ПОКА A[L] < X
           L += 1
       ПОКА A[R] > X
           R -= 1
       // если нужно делаем перестановку
       ЕСЛИ L <= R, то
           МЕНЯЕМ МЕСТАМИ A[L] И A[R]
           L += 1
           R -= 1

    // осталось отсортировать отдельно первую и вторую части 
    QUICKSORT(A, START, R)
    QUICKSORT(A, L, END)
Данная процедура может отсортировать любую часть массива, для этого достаточно верно указать параметры START и END.

Сравнение времени работы (в секундах) различных алгоритмов сортировки для массивов разного размера (N):
N Пузырьковая сортировка Сортировка вставками Быстрая сортировка
5000 0,039 0,016 0,00031
15000 0,359 0,141 0,00078
50000 3,985 1,469 0,00297

Обратите внимание, что алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементам списка. При таких условиях, быстрая сортировка в худшем случае будет выполняться O(n²).

Задача

Дано число N (1 <= N <= 100000), а затем N натуральных чисел из диапазона от 1 до 100. Выведите N чисел в неубывающем порядке.
 
Примеры
Входные данные Выходные данные
1
5
3 1 2 4 2
1 2 2 3 4