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

Быстрая сортировка: Начало (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 Пузырьковая сортировка Быстрая сортировка
1000 0,08 0,002
5000 1,80 0,006
15000 17,30 0,019

 

Анти-QuickSort


Для сортировки последовательности чисел широко используется быстрая сортировка - QuickSort. 
Основной шаг алгоритма сортировки — процедура partition, которая переставляет элементы массива a[l…r] типа T нужным образом (пример в псевдокоде):

int partition(a: T[n], int l, int r)
     T v = a[(l + r) / 2]
     int i = l
     int j = r
     while (i <= j) 
        while (a[i] < v)
           i++
        while (a[j] > v)
           j--
        if (i => j) 
           break
        swap(a[i++], a[j--])
     return j


Для сортировки всего массива необходимо выполнить процедуру quicksort(a,0,length[a]−1).
void quicksort(a: T[n], int l, int r)
     if l < r
        int q = partition(a, l, r)
        quicksort(a, l, q)
        quicksort(a, q + 1, r)

Сортировка в языке Python

В языке Python есть встроенная функция быстрой сортировки, которая называется sorted() и sort().  В своей работе она использует алгоритм Timsort.
Рассмотрим применение встроенных функций сортировки:
1) Получение нового массива B, который совпадает с отсортированным в порядке возрастания массивом A (по умолчанию выполняется сортировка по возрастания):

B = sorted(A)
2) Получение нового массива B, который совпадает с отсортированным в порядке убывания массивом A:
B = sorted(A, reverse = True)
reverse - по-английски - обратный

3) Для выполнения нестандартной сортировки, необходимо ключ сортировки - аргумент key.
Для сортировки по возрастанию по последней цифре числа ключом будет являться последняя цифра числа.
Для этого необходимо написать функцию, которая и будет возвращать нам требуемый ключ - в нашем случае последнюю цифру числа
# функция, возвращающая ключ сортировки - последнюю цифру числа
def lastDigit(n):
    return n%10

B = sorted(A, key = lastDigit)
4) Использование лямбда-функции - функции без имени:
Если не хочется писать отдельную функцию, из-за ее простоты, то можно использовать так называемые лямбда-функции. Такие функции записываются прямо при вызове в параметре key
B = sorted(A, key = lambda x: x % 10)
5) Если необходимо отсортировать массив "на месте" (не выделяя дополнительный массив), лучше использовать метод sort()
Например, сортировка массива А по последней цифре в порядке убывания выглядит так:
A.sort(key = lambda x: x % 10, reverse = True)