Сортирорвки

Ссылки:

Сортировки

Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.

QuickSort

  1. Находится опорная точка (первая / последняя / середина) по значению

  2. Относительно нее на текущем обрабатываемом участке массива происходит перестановка для всех элементов (>=) нее - вправо, и соответственно влево для (<=). При этом находится середина, относительно которой справа будут большие (или равные) элементы чем опорная точка, а слева меньшие (или равные).

  3. Сортировка повторяется для двух участков, разделенных найденной серединой

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[lo + (hi - lo) / 2]
    i := lo - 1
    j := hi + 1
    loop forever
        do i := i + 1 while A[i] < pivot

        do j := j - 1 while A[j] > pivot

        if i >= j then return j

        swap A[i] with A[j]

// Находится опорная точка
pivot := A.pop()

// Создается массив с меньшими элементами чем опорная точка от исходного
lA := A.filter(where e < pivot)

// Создается массив с большими элементами чем опорная точка от исходного
rA := A.filter(where e >= pivot)

// вернуть массив состоящий из отсортированной левой части, опорного и отсортированной правой части
return quicksort(lA) + [pivot] + quicksort(rA)

Ссылки:

Википедия

../../_images/Sorting_quicksort_anim.gif

Пирамидальная сортировка (HeapSort)

Строится пирамида (двоичная куча), последовательно удаляются узлы, начиная с вершины. гарантированная сложность Θ(n log n)

MergeSort

  1. Сортируемый массив разбивается на две части примерно одинакового размера.

  2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом.

  3. Два упорядоченных массива половинного размера соединяются в один.

Ссылки:

Википедия

../../_images/Merge-sort-example-300px.gif

TimSort

Гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием (MergeSort)

  1. По специальному алгоритму входной массив разделяется на подмассивы.

  2. Каждый подмассив сортируется сортировкой вставками.

  3. Отсортированные подмассивы собираются в единый массив с помощью модифицированной сортировки слиянием.

RadixSort

Исходный массив: a. Максимальное число разрядов: k. Число различных цифр в пределах одного разряда d

  1. Создается дополнительная структура (Массив массивов) b для каждой цифры (размерностью d).

  2. Для каждого разряда (k_cur : k), начиная с наименьшего:

    2.1. Занести все число a[i] в массив b под индексом a[i].get(k_cur) (число в текущем разряде k_cur):

    b.add( a[i].get(k_cur) ) = a[i]

    2.2. После прохода по всему массиву a, выполняется проход по сформировавшемуся массиву b, начиная от наименьшего числа, выписывая все элементы в массив a начиная с первого записанного

  3. После всех проходов, полученный результат сортировки будет храниться в массиве a

[40, 34, 32, 2, 14, 24]     k = 2    d = 5  (0, 1, 2, 3, 4)

Для младшего разряда:

{
    0: 40,
    1:
    2: 32, 2
    3:
    4: 34, 14, 24
}

[40, 32, 2, 34, 14, 24]

Для старшего разряда:

{
    0: 2,
    1: 14
    2: 24
    3: 32, 34
    4: 40
}

[2, 14, 24, 32, 34, 40]

Алгоритм сортировки выполняется за линейное время.

GravitySort


Ссылки:

https://en.wikipedia.org/wiki/Bead_sort