Алгоритмы сортировки

Complexity: Good — это O(n log n) and bad — это O(n2)

Устойчивость (англ. stability) — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами

Shell sort (Сортировка Шелла) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами.

Реализация на C

// BaseType - любой перечисляемый тип

// typedef int BaseType - пример

void ShellsSort(BaseType *A, unsigned N)

{ unsigned i,j,k;

BaseType t;

for(k = N/2; k > 0; k /=2)

for(i = k; i < N; i++)

{

t = A[i];

for(j = i; j>=k; j-=k)

{

if(t < A[j-k])

A[j] = A[j-k];

else

break;

}

A[j] = t;

}

}

Comb sort - Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.

Сложность:O(n \log{n})

Реализация на Java

public static <E extends Comparable<? super E>> void sort(E[] input) {

int gap = input.length;

boolean swapped = true;

while (gap > 1 || swapped) {

if (gap > 1)

gap = (int) (gap / 1.247330950103979);

int i = 0;

swapped = false;

while (i + gap < input.length) {

if (input[i].compareTo(input[i + gap]) > 0) {

E t = input[i];

input[i] = input[i + gap];

input[i + gap] = t;

swapped = true;

}

i++;

}

}

}

Quicksort - qsort (по имени в стандартнойбиблиотеке языка Си)

Общая идея алгоритма состоит в следующем:

• Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива или же число, вычисленное на основе значений элементов; от выбора этого числа сильно зависит эффективность алгоритма (см.ниже).
• Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».[1]
• Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

Достоинства:

• Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения.
• Прост в реализации.

• Требует лишь дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае памяти)
• Хорошо сочетается с механизмами кэширования и виртуальной памяти.
• Допускает естественное распараллеливание (сортировка выделенных подмассивов в параллельно выполняющихся подпроцессах).
• Допускает эффективную модификацию для сортировки по нескольким ключам (в частности — алгоритм Седжвика для сортировки строк): благодаря тому, что в процессе разделения автоматически выделяется отрезок элементов, равных опорному, этот отрезок можно сразу же сортировать по следующему ключу.
• Работает на связных списках и других структурах с последовательным доступом, допускающих эффективный проход как от начала к концу, так и от конца к началу.

Недостатки:

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

• Прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека, так как в худшем случае ей может потребоваться сделать вложенных рекурсивных вызовов.
• Неустойчив.

Tree sort (Сортировка с помощью двоичного дерева)-

1. Построение двоичного дерева.

2. Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.

Эффективность: От O(n log(n)) до O(n²), в зависимости от сбалансированности.

Selection sort (Сортировка выбором) - Алгоритм без дополнительного выделения памяти

Шаги алгоритма:

1. находим номер минимального значения в текущем списке
2. производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции)
3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

Bubble sort - алгоритм — простейший, но эффективен он лишь для небольших массивов.

Cocktail sort (Сортировка перемешиванием) — разновидность пузырьковой сортировки:

• Проходы вверх - вниз.
• Если на части массива не было перестановок, то она отсортирована.

Сложность:O(n^2).

Gnome sort (Гномья сортировка) - сортировка пузырьком начиная от массива из 2-х компонентов, добавляю по 1 отсортированному элементу.

Сложность:O(n^2).

Insertion sort (Сортировка вставками) - алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов

Сложность:O(n^2).

Псевдокод

for j = 2 to A.length

key = A[j]

i = j - 1

while i > 0 and A[i] > key

A[i+1] = A[i]

i = i - 1

A[i+1] = key

.

Merge sort (Сортировка слиянием) -

/**

* Сортирует массив используя рекурсивную сортировку слиянием

* up - указатель на массив который нужно сортировать

* down - указатель на массив с, как минимум, таким же размером как у 'up', используется как буфер

* left - левая граница массива, передайте 0 чтобы сортировать массив с начала

* right - правая граница массива, передайте длину массива - 1 чтобы сортировать массив до последнего элемента

* возвращает: указатель на отсортированный массив. Из за особенностей работы данной реализации

* отсортированная версия массива может оказаться либо в 'up' либо в 'down'

**/

int* merge_sort(int *up, int *down, unsigned int left, unsigned int right)

{

if (left == right)

{

down[left] = up[left];

return down;

}

unsigned int middle = (unsigned int)((left + right) * 0.5);

// разделяй и сортируй

int *l_buff = merge_sort(up, down, left, middle);

int *r_buff = merge_sort(up, down, middle + 1, right);

// слияние двух отсортированных половин

int *target = l_buff == up ? down : up;

unsigned int width = right - left, l_cur = left, r_cur = middle + 1;

for (unsigned int i = left; i <= right; i++)

{

if (l_cur <= middle && r_cur <= right)

{

if (l_buff[l_cur] < r_buff[r_cur])

{

target[i] = l_buff[l_cur];

l_cur++;

}

else

{

target[i] = r_buff[r_cur];

r_cur++;

}

}

else if (l_cur <= middle)

{

target[i] = l_buff[l_cur];

l_cur++;

}

else

{

target[i] = r_buff[r_cur];

r_cur++;

}

}

return target;

}

Timsort- Сочетает сортировку вставками и сортировку слиянием

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

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

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

Counting sort (Сортировка подсчётом) - для большого количества одинаковых элементов в массиве. Считаем количество каждого значения а потом пере заполняем массив на основании подсчетов. Сложность: O(n+k)

Bucket sort (Блочная сортировка)

Сложность:O(n). Требуется O(k) дополнительной памяти

Odd–even sort (чёт-нечет) - Этот относительно простой алгоритм сортировки, разработанный для использования на параллельных процессорах, является модификацией пузырьковой сортировки

Реализация на С++

template < typename T >

void oddEvenSorting(T *array, int arrayLength){

for (int i = 0; i < arrayLength; i++){

for (int j = (i % 2) ? 0 : 1; j < arrayLength - 1; j += 2){

if (array[j] > array[j + 1]){

std::swap(array[j], array[j + 1]);

}

}

}

}