Сортировка за константное время

Такой вопрос я задал одному из наших Российских AI-ассистент разработчика, который ускоряет создание ПО
ответ был такой:

Вот пример кода на Golang для сортировки подсчетом:

package main

import (
“fmt”
)

// countingSort сортирует массив с использованием алгоритма сортировки подсчетом.
func countingSort(arr []int) {
minValue := arr[0]
maxValue := arr[len(arr)-1]
count := make([]int, maxValue-minValue+1)

for _, num := range arr {
    count[num-minValue]++
}

for i := 1; i < len(count); i++ {
    count[i] += count[i-1]
}

index := 0
for _, num := range arr {
    for count[num-minValue] > 0 {
        arr[index] = num
        index++
        count[num-minValue]--
    }
}

}

func main() {
inputArray := []int{5, 2, 3, 4, 1, 6, 7, 8, 9}
sortedArray := make([]int, len(inputArray))

copy(sortedArray, inputArray) // Копируем исходный массив в новый для сохранения результатов

countingSort(sortedArray)

for _, num := range sortedArray {
    fmt.Printf("%d ", num)
}
fmt.Println()

}

Этот код сначала определяет минимальное и максимальное значения в массиве, затем создает массив count, который будет использоваться для подсчета количества каждого элемента. После этого он проходит по массиву и увеличивает счетчик для каждого элемента. Затем он проходит по счетчику и добавляет к нему предыдущее значение, чтобы определить индекс для каждого элемента после сортировки. В конце он проходит по массиву и заменяет элементы на их индексы.

Далее я задал вопрос: Что делает данных код, подробней можешь описать?

Этот код выполняет сортировку подсчетом на слайсе arr.
Алгоритм сортировки подсчетом заключается в следующем:

1. Подсчитываем количество каждого элемента в массиве. Для этого мы используем счетчики count.
2. Используем эти подсчеты для определения индекса каждого элемента после сортировки. Мы создаем массив count и заполняем его нулями. Затем проходим по каждому элементу массива и увеличиваем счетчик для соответствующего элемента.
3. После того как мы подсчитали количество каждого элемента, мы проходим по счетчикам и добавляем к ним предыдущее значение, чтобы определить индекс для каждого элемента после сортировки.
4. Наконец, мы проходим по массиву и заменяем каждый элемент на его индекс.
5. В результате мы получаем отсортированный массив.

Следующим вопросом был: Какая сложность данного алгоритма в нотации O?

Сложность алгоритма сортировки подсчетом в нотации O равна O(n). Это означает, что время выполнения алгоритма пропорционально количеству элементов в массиве.

Далее я спросил: А есть более быстрые алгоритмы сортировки?

Да, есть более быстрые алгоритмы сортировки. Например, сортировка выбором (selection sort), которая имеет сложность O(n^2), или сортировка вставками (insertion sort), которая имеет сложность O(n^2) для массивов с неравномерным распределением элементов. Однако, если распределение элементов близко к равномерному, то сортировка подсчетом может быть быстрее.

Но на самом деле не стоит спрашивать у AI-ассистента разработчика, а лучше разобраться самому.
Поехали….

https://habr.com/ru/articles/335920/

Вступление

На эту тему написано уже немало статей. Однако я еще не видел статьи, в которой сравниваются все основные сортировки на большом числе тестов разного типа и размера. Кроме того, далеко не везде выложены реализации и описание набора тестов. Это приводит к тому, что могут возникнуть сомнения в правильности исследования. Однако цель моей работы состоит не только в том, чтобы определить, какие сортировки работают быстрее всего (в целом это и так известно). В первую очередь мне было интересно исследовать алгоритмы, оптимизировать их, чтобы они работали как можно быстрее. Работая над этим, мне удалось придумать эффективную формулу для сортировки Шелла.

Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.

Описание основных сортировок и их реализация

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

Сортировка пузырьком / Bubble sort

Будем идти по массиву слева направо. Если текущий элемент больше следующего, меняем их местами. Делаем так, пока массив не будет отсортирован. Заметим, что после первой итерации самый большой элемент будет находиться в конце массива, на правильном месте. После двух итераций на правильном месте будут стоять два наибольших элемента, и так далее. Очевидно, не более чем после n итераций массив будет отсортирован. Таким образом, асимптотика в худшем и среднем случае – O(n2), в лучшем случае – O(n).

Реализация:
void bubblesort(int* l, int* r) {
int sz = r - l;
if (sz <= 1) return;
bool b = true;
while (b) {
b = false;
for (int* i = l; i + 1 < r; i++) {
if (*i > *(i + 1)) {
swap(*i, *(i + 1));
b = true;
}
}
r–;
}
}

Шейкерная сортировка / Shaker sort

(также известна как сортировка перемешиванием и коктейльная сортировка). Заметим, что сортировка пузырьком работает медленно на тестах, в которых маленькие элементы стоят в конце (их еще называют «черепахами»). Такой элемент на каждом шаге алгоритма будет сдвигаться всего на одну позицию влево. Поэтому будем идти не только слева направо, но и справа налево. Будем поддерживать два указателя begin и end, обозначающих, какой отрезок массива еще не отсортирован. На очередной итерации при достижении end вычитаем из него единицу и движемся справа налево, аналогично, при достижении begin прибавляем единицу и двигаемся слева направо. Асимптотика у алгоритма такая же, как и у сортировки пузырьком, однако реальное время работы лучше.

Реализация:
void shakersort(int* l, int* r) {
int sz = r - l;
if (sz <= 1) return;
bool b = true;
int* beg = l - 1;
int* end = r - 1;
while (b) {
b = false;
beg++;
for (int* i = beg; i < end; i++) {
if (*i > *(i + 1)) {
swap(*i, (i + 1));
b = true;
}
}
if (!b) break;
end–;
for (int i = end; i > beg; i–) {
if (*i < *(i - 1)) {
swap(*i, *(i - 1));
b = true;
}
}
}
}

Сортировка расческой / Comb sort

Еще одна модификация сортировки пузырьком. Для того, чтобы избавиться от «черепах», будем переставлять элементы, стоящие на расстоянии. Зафиксируем его и будем идти слева направо, сравнивая элементы, стоящие на этом расстоянии, переставляя их, если необходимо. Очевидно, это позволит «черепахам» быстро добраться в начало массива. Оптимально изначально взять расстояние равным длине массива, а далее делить его на некоторый коэффициент, равный примерно 1.247. Когда расстояние станет равно единице, выполняется сортировка пузырьком. В лучшем случае асимптотика равна O(nlogn), в худшем – O(n2). Какая асимптотика в среднем мне не очень понятно, на практике похоже на O(nlogn).

Реализация:
void combsort(int* l, int* r) {
int sz = r - l;
if (sz <= 1) return;
double k = 1.2473309;
int step = sz - 1;
while (step > 1) {
for (int* i = l; i + step < r; i++) {
if (*i > *(i + step))
swap(*i, (i + step));
}
step /= k;
}
bool b = true;
while (b) {
b = false;
for (int i = l; i + 1 < r; i++) {
if (*i > *(i + 1)) {
swap(*i, *(i + 1));
b = true;
}
}
}
}

Об этих сортировках (пузырьком, шейкерной и расческой) также можно почитать здесь.

Сортировка вставками / Insertion sort

Создадим массив, в котором после завершения алгоритма будет лежать ответ. Будем поочередно вставлять элементы из исходного массива так, чтобы элементы в массиве-ответе всегда были отсортированы. Асимптотика в среднем и худшем случае – O(n2), в лучшем – O(n). Реализовывать алгоритм удобнее по-другому (создавать новый массив и реально что-то вставлять в него относительно сложно): просто сделаем так, чтобы отсортирован был некоторый префикс исходного массива, вместо вставки будем менять текущий элемент с предыдущим, пока они стоят в неправильном порядке.

Реализация:
void insertionsort(int* l, int* r) {
for (int *i = l + 1; i < r; i++) {
int* j = i;
while (j > l && *(j - 1) > j) {
swap((j - 1), *j);
j–;
}
}
}

Сортировка Шелла / Shellsort

Используем ту же идею, что и сортировка с расческой, и применим к сортировке вставками. Зафиксируем некоторое расстояние. Тогда элементы массива разобьются на классы – в один класс попадают элементы, расстояние между которыми кратно зафиксированному расстоянию. Отсортируем сортировкой вставками каждый класс. В отличие от сортировки расческой, неизвестен оптимальный набор расстояний. Существует довольно много последовательностей с разными оценками. Последовательность Шелла – первый элемент равен длине массива, каждый следующий вдвое меньше предыдущего. Асимптотика в худшем случае – O(n2). Последовательность Хиббарда – 2n — 1, асимптотика в худшем случае – O(n1,5), последовательность Седжвика (формула нетривиальна, можете ее посмотреть по ссылке ниже) — O(n4/3), Пратта (все произведения степеней двойки и тройки) — O(nlog2n). Отмечу, что все эти последовательности нужно рассчитать только до размера массива и запускать от большего от меньшему (иначе получится просто сортировка вставками). Также я провел дополнительное исследование и протестировал разные последовательности вида si = a * si — 1 + k * si — 1 (отчасти это было навеяно эмпирической последовательностью Циура – одной из лучших последовательностей расстояний для небольшого количества элементов). Наилучшими оказались последовательности с коэффициентами a = 3, k = 1/3; a = 4, k = 1/4 и a = 4, k = -1/5.

Несколько полезных ссылок:

Сортировка Шелла в русскоязычной Википедии
Сортировка Шелла в англоязычной Википедии
Статья на Хабре

Реализации:
void shellsort(int* l, int* r) {
int sz = r - l;
int step = sz / 2;
while (step >= 1) {
for (int *i = l + step; i < r; i++) {
int *j = i;
int *diff = j - step;
while (diff >= l && *diff > *j) {
swap(diff, j);
j = diff;
diff = j - step;
}
}
step /= 2;
}
}
void shellsorthib(int l, int r) {
int sz = r - l;
if (sz <= 1) return;
int step = 1;
while (step < sz) step <<= 1;
step >>= 1;
step–;
while (step >= 1) {
for (int *i = l + step; i < r; i++) {
int *j = i;
int *diff = j - step;
while (diff >= l && *diff > *j) {
swap(diff, j);
j = diff;
diff = j - step;
}
}
step /= 2;
}
}
int steps[100];
void shellsortsedgwick(int l, int r) {
int sz = r - l;
steps[0] = 1;
int q = 1;
while (steps[q - 1] * 3 < sz) {
if (q % 2 == 0)
steps[q] = 9 * (1 << q) - 9 * (1 << (q / 2)) + 1;
else
steps[q] = 8 * (1 << q) - 6 * (1 << ((q + 1) / 2)) + 1;
q++;
}
q–;
for (; q >= 0; q–) {
int step = steps[q];
for (int *i = l + step; i < r; i++) {
int *j = i;
int *diff = j - step;
while (diff >= l && *diff > *j) {
swap(diff, j);
j = diff;
diff = j - step;
}
}
}
}
void shellsortpratt(int l, int r) {
int sz = r - l;
steps[0] = 1;
int cur = 1, q = 1;
for (int i = 1; i < sz; i++) {
int cur = 1 << i;
if (cur > sz / 2) break;
for (int j = 1; j < sz; j++) {
cur *= 3;
if (cur > sz / 2) break;
steps[q++] = cur;
}
}
insertionsort(steps, steps + q);
q–;
for (; q >= 0; q–) {
int step = steps[q];
for (int *i = l + step; i < r; i++) {
int *j = i;
int *diff = j - step;
while (diff >= l && *diff > *j) {
swap(diff, j);
j = diff;
diff = j - step;
}
}
}
}
void myshell1(int l, int r) {
int sz = r - l, q = 1;
steps[0] = 1;
while (steps[q - 1] < sz) {
int s = steps[q - 1];
steps[q++] = s * 4 + s / 4;
}
q–;
for (; q >= 0; q–) {
int step = steps[q];
for (int *i = l + step; i < r; i++) {
int *j = i;
int *diff = j - step;
while (diff >= l && *diff > *j) {
swap(diff, j);
j = diff;
diff = j - step;
}
}
}
}
void myshell2(int l, int r) {
int sz = r - l, q = 1;
steps[0] = 1;
while (steps[q - 1] < sz) {
int s = steps[q - 1];
steps[q++] = s * 3 + s / 3;
}
q–;
for (; q >= 0; q–) {
int step = steps[q];
for (int *i = l + step; i < r; i++) {
int *j = i;
int *diff = j - step;
while (diff >= l && *diff > *j) {
swap(diff, j);
j = diff;
diff = j - step;
}
}
}
}
void myshell3(int l, int r) {
int sz = r - l, q = 1;
steps[0] = 1;
while (steps[q - 1] < sz) {
int s = steps[q - 1];
steps[q++] = s * 4 - s / 5;
}
q–;
for (; q >= 0; q–) {
int step = steps[q];
for (int *i = l + step; i < r; i++) {
int *j = i;
int *diff = j - step;
while (diff >= l && *diff > *j) {
swap(*diff, *j);
j = diff;
diff = j - step;
}
}
}
}

Сортировка деревом / Tree sort

Будем вставлять элементы в двоичное дерево поиска. После того, как все элементы вставлены достаточно обойти дерево в глубину и получить отсортированный массив. Если использовать сбалансированное дерево, например красно-черное, асимптотика будет равна O(nlogn) в худшем, среднем и лучшем случае. В реализации использован контейнер multiset.

Здесь можно почитать про деревья поиска:

Википедия
Статья на Хабре
И ещё статья на Хабре

Реализация:
void treesort(int* l, int* r) {
multiset m;
for (int *i = l; i < r; i++)
m.insert(*i);
for (int q : m)
*l = q, l++;
}

Гномья сортировка / Gnome sort

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

Реализация:
void gnomesort(int* l, int* r) {
int *i = l;
while (i < r) {
if (i == l || *(i - 1) <= i) i++;
else swap((i - 1), *i), i–;
}
}

Сортировка выбором / Selection sort

На очередной итерации будем находить минимум в массиве после текущего элемента и менять его с ним, если надо. Таким образом, после i-ой итерации первые i элементов будут стоять на своих местах. Асимптотика: O(n2) в лучшем, среднем и худшем случае. Нужно отметить, что эту сортировку можно реализовать двумя способами – сохраняя минимум и его индекс или просто переставляя текущий элемент с рассматриваемым, если они стоят в неправильном порядке. Первый способ оказался немного быстрее, поэтому он и реализован.

Реализация:
void selectionsort(int* l, int* r) {
for (int *i = l; i < r; i++) {
int minz = *i, *ind = i;
for (int *j = i + 1; j < r; j++) {
if (*j < minz) minz = *j, ind = j;
}
swap(*i, *ind);
}
}

Пирамидальная сортировка / Heapsort

Развитие идеи сортировки выбором. Воспользуемся структурой данных «куча» (или «пирамида», откуда и название алгоритма). Она позволяет получать минимум за O(1), добавляя элементы и извлекая минимум за O(logn). Таким образом, асимптотика O(nlogn) в худшем, среднем и лучшем случае. Реализовывал кучу я сам, хотя в С++ и есть контейнер priority_queue, поскольку этот контейнер довольно медленный.

Почитать про кучу можно здесь:

Википедия
Статья на Хабре

Реализация:
template
class heap {
public:
int size() {
return n;
}
int top() {
return h[0];
}
bool empty() {
return n == 0;
}
void push(T a) {
h.push_back(a);
SiftUp(n);
n++;
}
void pop() {
n–;
swap(h[n], h[0]);
h.pop_back();
SiftDown(0);
}
void clear() {
h.clear();
n = 0;
}
T operator [] (int a) {
return h[a];
}
private:
vector h;
int n = 0;
void SiftUp(int a) {
while (a) {
int p = (a - 1) / 2;
if (h[p] > h[a]) swap(h[p], h[a]);
else break;
a–; a /= 2;
}
}
void SiftDown(int a) {
while (2 * a + 1 < n) {
int l = 2 * a + 1, r = 2 * a + 2;
if (r == n) {
if (h[l] < h[a]) swap(h[l], h[a]);
break;
}
else if (h[l] <= h[r]) {
if (h[l] < h[a]) {
swap(h[l], h[a]);
a = l;
}
else break;
}
else if (h[r] < h[a]) {
swap(h[r], h[a]);
a = r;
}
else break;
}
}
};
void heapsort(int* l, int* r) {
heap h;
for (int *i = l; i < r; i++) h.push(*i);
for (int *i = l; i < r; i++) {
*i = h.top();
h.pop();
}
}

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

Выберем некоторый опорный элемент. После этого перекинем все элементы, меньшие его, налево, а большие – направо. Рекурсивно вызовемся от каждой из частей. В итоге получим отсортированный массив, так как каждый элемент меньше опорного стоял раньше каждого большего опорного. Асимптотика: O(nlogn) в среднем и лучшем случае, O(n2). Наихудшая оценка достигается при неудачном выборе опорного элемента. Моя реализация этого алгоритма совершенно стандартна, идем одновременно слева и справа, находим пару элементов, таких, что левый элемент больше опорного, а правый меньше, и меняем их местами. Помимо чистой быстрой сортировки, участвовала в сравнении и сортировка, переходящая при малом количестве элементов на сортировку вставками. Константа подобрана тестированием, а сортировка вставками — наилучшая сортировка, подходящая для этой задачи (хотя не стоит из-за этого думать, что она самая быстрая из квадратичных).

Реализация:
void quicksort(int* l, int* r) {
if (r - l <= 1) return;
int z = *(l + (r - l) / 2);
int* ll = l, *rr = r - 1;
while (ll <= rr) {
while (*ll < z) ll++;
while (*rr > z) rr–;
if (ll <= rr) {
swap(*ll, *rr);
ll++;
rr–;
}
}
if (l < rr) quicksort(l, rr + 1);
if (ll < r) quicksort(ll, r);
}
void quickinssort(int* l, int* r) {
if (r - l <= 32) {
insertionsort(l, r);
return;
}
int z = *(l + (r - l) / 2);
int* ll = l, *rr = r - 1;
while (ll <= rr) {
while (*ll < z) ll++;
while (*rr > z) rr–;
if (ll <= rr) {
swap(*ll, *rr);
ll++;
rr–;
}
}
if (l < rr) quickinssort(l, rr + 1);
if (ll < r) quickinssort(ll, r);
}

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

Сортировка, основанная на парадигме «разделяй и властвуй». Разделим массив пополам, рекурсивно отсортируем части, после чего выполним процедуру слияния: поддерживаем два указателя, один на текущий элемент первой части, второй – на текущий элемент второй части. Из этих двух элементов выбираем минимальный, вставляем в ответ и сдвигаем указатель, соответствующий минимуму. Слияние работает за O(n), уровней всего logn, поэтому асимптотика O(nlogn). Эффективно заранее создать временный массив и передать его в качестве аргумента функции. Эта сортировка рекурсивна, как и быстрая, а потому возможен переход на квадратичную при небольшом числе элементов.

Реализация:
void merge(int* l, int* m, int* r, int* temp) {
int cl = l, cr = m, cur = 0;
while (cl < m && cr < r) {
if (cl < cr) temp[cur++] = cl, cl++;
else temp[cur++] = cr, cr++;
}
while (cl < m) temp[cur++] = cl, cl++;
while (cr < r) temp[cur++] = cr, cr++;
cur = 0;
for (int i = l; i < r; i++)
i = temp[cur++];
}
void _mergesort(int l, int r, int temp) {
if (r - l <= 1) return;
int m = l + (r - l) / 2;
_mergesort(l, m, temp);
_mergesort(m, r, temp);
merge(l, m, r, temp);
}
void mergesort(int l, int r) {
int temp = new int[r - l];
_mergesort(l, r, temp);
delete temp;
}
void _mergeinssort(int l, int r, int temp) {
if (r - l <= 32) {
insertionsort(l, r);
return;
}
int m = l + (r - l) / 2;
_mergeinssort(l, m, temp);
_mergeinssort(m, r, temp);
merge(l, m, r, temp);
}
void mergeinssort(int l, int* r) {
int* temp = new int[r - l];
_mergeinssort(l, r, temp);
delete temp;
}

Сортировка подсчетом / Counting sort

Создадим массив размера r – l, где l – минимальный, а r – максимальный элемент массива. После этого пройдем по массиву и подсчитаем количество вхождений каждого элемента. Теперь можно пройти по массиву значений и выписать каждое число столько раз, сколько нужно. Асимптотика – O(n + r — l). Можно модифицировать этот алгоритм, чтобы он стал стабильным: для этого определим место, где должно стоять очередное число (это просто префиксные суммы в массиве значений) и будем идти по исходному массиву слева направо, ставя элемент на правильное место и увеличивая позицию на 1. Эта сортировка не тестировалась, поскольку большинство тестов содержало достаточно большие числа, не позволяющие создать массив требуемого размера. Однако она, тем не менее, пригодилась.

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

(также известна как корзинная и карманная сортировка). Пусть l – минимальный, а r – максимальный элемент массива. Разобьем элементы на блоки, в первом будут элементы от l до l + k, во втором – от l + k до l + 2k и т.д., где k = (r – l) / количество блоков. В общем-то, если количество блоков равно двум, то данный алгоритм превращается в разновидность быстрой сортировки. Асимптотика этого алгоритма неясна, время работы зависит и от входных данных, и от количества блоков. Утверждается, что на удачных данных время работы линейно. Реализация этого алгоритма оказалась одной из самых трудных задач. Можно сделать это так: просто создавать новые массивы, рекурсивно их сортировать и склеивать. Однако такой подход все же довольно медленный и меня не устроил. В эффективной реализации используется несколько идей:

1. Не будем создавать новых массивов. Для этого воспользуемся техникой сортировки подсчетом – подсчитаем количество элементов в каждом блоке, префиксные суммы и, таким образом, позицию каждого элемента в массиве.

2. Не будем запускаться из пустых блоков. Занесем индексы непустых блоков в отдельный массив и запустимся только от них.

3. Проверим, отсортирован ли массив. Это не ухудшит время работы, так как все равно нужно сделать проход с целью нахождения минимума и максимума, однако позволит алгоритму ускориться на частично отсортированных данных, ведь элементы вставляются в новые блоки в том же порядке, что и в исходном массиве.

4. Поскольку алгоритм получился довольно громоздким, при небольшом количестве элементов он крайне неэффективен. До такой степени, что переход на сортировку вставками ускоряет работу примерно в 10 раз.

Осталось только понять, какое количество блоков нужно выбрать. На рандомизированных тестах мне удалось получить следующую оценку: 1500 блоков для 107 элементов и 3000 для 108. Подобрать формулу не удалось – время работы ухудшалось в несколько раз.

Реализация:
void _newbucketsort(int* l, int* r, int* temp) {
if (r - l <= 64) {
insertionsort(l, r);
return;
}
int minz = *l, maxz = *l;
bool is_sorted = true;
for (int *i = l + 1; i < r; i++) {
minz = min(minz, *i);
maxz = max(maxz, *i);
if (i < (i - 1)) is_sorted = false;
}
if (is_sorted) return;
int diff = maxz - minz + 1;
int numbuckets;
if (r - l <= 1e7) numbuckets = 1500;
else numbuckets = 3000;
int range = (diff + numbuckets - 1) / numbuckets;
int cnt = new int[numbuckets + 1];
for (int i = 0; i <= numbuckets; i++)
cnt[i] = 0;
int cur = 0;
for (int i = l; i < r; i++) {
temp[cur++] = *i;
int ind = (i - minz) / range;
cnt[ind + 1]++;
}
int sz = 0;
for (int i = 1; i <= numbuckets; i++)
if (cnt[i]) sz++;
int run = new int[sz];
cur = 0;
for (int i = 1; i <= numbuckets; i++)
if (cnt[i]) run[cur++] = i - 1;
for (int i = 1; i <= numbuckets; i++)
cnt[i] += cnt[i - 1];
cur = 0;
for (int i = l; i < r; i++) {
int ind = (temp[cur] - minz) / range;
(l + cnt[ind]) = temp[cur];
cur++;
cnt[ind]++;
}
for (int i = 0; i < sz; i++) {
int r = run[i];
if (r != 0) _newbucketsort(l + cnt[r - 1], l + cnt[r], temp);
else _newbucketsort(l, l + cnt[r], temp);
}
delete run;
delete cnt;
}
void newbucketsort(int l, int r) {
int *temp = new int[r - l];
_newbucketsort(l, r, temp);
delete temp;
}

Поразрядная сортировка / Radix sort

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

LSD (least significant digit):

Представим каждое число в двоичном виде. На каждом шаге алгоритма будем сортировать числа таким образом, чтобы они были отсортированы по первым k * i битам, где k – некоторая константа. Из данного определения следует, что на каждом шаге достаточно стабильно сортировать элементы по новым k битам. Для этого идеально подходит сортировка подсчетом (необходимо 2k памяти и времени, что немного при удачном выборе константы). Асимптотика: O(n), если считать, что числа фиксированного размера (а в противном случае нельзя было бы считать, что сравнение двух чисел выполняется за единицу времени). Реализация довольно проста.

Реализация:
int digit(int n, int k, int N, int M) {
return (n >> (N * k) & (M - 1));
}
void _radixsort(int* l, int* r, int N) {
int k = (32 + N - 1) / N;
int M = 1 << N;
int sz = r - l;
int* b = new int[sz];
int* c = new int[M];
for (int i = 0; i < k; i++) {
for (int j = 0; j < M; j++)
c[j] = 0;
for (int* j = l; j < r; j++)
c[digit(*j, i, N, M)]++;
for (int j = 1; j < M; j++)
c[j] += c[j - 1];
for (int* j = r - 1; j >= l; j–)
b[–c[digit(j, i, N, M)]] = j;
int cur = 0;
for (int j = l; j < r; j++)
j = b[cur++];
}
delete b;
delete c;
}
void radixsort(int l, int r) {
_radixsort(l, r, 8);
}

MSD (most significant digit):

На самом деле, некоторая разновидность блочной сортировки. В один блок будут попадать числа с равными k битами. Асимптотика такая же, как и у LSD версии. Реализация очень похожа на блочную сортировку, но проще. В ней используется функция digit, определенная в реализации LSD версии.

Реализация:
void _radixsortmsd(int* l, int* r, int N, int d, int* temp) {
if (d == -1) return;
if (r - l <= 32) {
insertionsort(l, r);
return;
}
int M = 1 << N;
int* cnt = new int[M + 1];
for (int i = 0; i <= M; i++)
cnt[i] = 0;
int cur = 0;
for (int* i = l; i < r; i++) {
temp[cur++] = i;
cnt[digit(i, d, N, M) + 1]++;
}
int sz = 0;
for (int i = 1; i <= M; i++)
if (cnt[i]) sz++;
int run = new int[sz];
cur = 0;
for (int i = 1; i <= M; i++)
if (cnt[i]) run[cur++] = i - 1;
for (int i = 1; i <= M; i++)
cnt[i] += cnt[i - 1];
cur = 0;
for (int i = l; i < r; i++) {
int ind = digit(temp[cur], d, N, M);
(l + cnt[ind]) = temp[cur];
cur++;
cnt[ind]++;
}
for (int i = 0; i < sz; i++) {
int r = run[i];
if (r != 0) _radixsortmsd(l + cnt[r - 1], l + cnt[r], N, d - 1, temp);
else _radixsortmsd(l, l + cnt[r], N, d - 1, temp);
}
delete run;
delete cnt;
}
void radixsortmsd(int l, int r) {
int temp = new int[r - l];
_radixsortmsd(l, r, 8, 3, temp);
delete temp;
}

Битонная сортировка / Bitonic sort:

Идея данного алгоритма заключается в том, что исходный массив преобразуется в битонную последовательность – последовательность, которая сначала возрастает, а потом убывает. Ее можно эффективно отсортировать следующим образом: разобьем массив на две части, создадим два массива, в первый добавим все элементы, равные минимуму из соответственных элементов каждой из двух частей, а во второй – равные максимуму. Утверждается, что получатся две битонные последовательности, каждую из которых можно рекурсивно отсортировать тем же образом, после чего можно склеить два массива (так как любой элемент первого меньше или равен любого элемента второго). Для того, чтобы преобразовать исходный массив в битонную последовательность, сделаем следующее: если массив состоит из двух элементов, можно просто завершиться, иначе разделим массив пополам, рекурсивно вызовем от половинок алгоритм, после чего отсортируем первую часть по порядку, вторую в обратном порядке и склеим. Очевидно, получится битонная последовательность. Асимптотика: O(nlog2n), поскольку при построении битонной последовательности мы использовали сортировку, работающую за O(nlogn), а всего уровней было logn. Также заметим, что размер массива должен быть равен степени двойки, так что, возможно, придется его дополнять фиктивными элементами (что не влияет на асимптотику).

Реализация:
void bitseqsort(int* l, int* r, bool inv) {
if (r - l <= 1) return;
int *m = l + (r - l) / 2;
for (int *i = l, *j = m; i < m && j < r; i++, j++) {
if (inv ^ (*i > j)) swap(i, j);
}
bitseqsort(l, m, inv);
bitseqsort(m, r, inv);
}
void makebitonic(int l, int r) {
if (r - l <= 1) return;
int m = l + (r - l) / 2;
makebitonic(l, m);
bitseqsort(l, m, 0);
makebitonic(m, r);
bitseqsort(m, r, 1);
}
void bitonicsort(int l, int r) {
int n = 1;
int inf = *max_element(l, r) + 1;
while (n < r - l) n = 2;
int a = new int[n];
int cur = 0;
for (int *i = l; i < r; i++)
a[cur++] = *i;
while (cur < n) a[cur++] = inf;
makebitonic(a, a + n);
bitseqsort(a, a + n, 0);
cur = 0;
for (int *i = l; i < r; i++)
*i = a[cur++];
delete a;
}

Timsort

Гибридная сортировка, совмещающая сортировку вставками и сортировку слиянием. Разобьем элементы массива на несколько подмассивов небольшого размера, при этом будем расширять подмассив, пока элементы в нем отсортированы. Отсортируем подмассивы сортировкой вставками, пользуясь тем, что она эффективно работает на отсортированных массивах. Далее будем сливать подмассивы как в сортировке слиянием, беря их примерно равного размера (иначе время работы приблизится к квадратичному). Для этого удобного хранить подмассивы в стеке, поддерживая инвариант — чем дальше от вершины, тем больше размер, и сливать подмассивы на верхушке только тогда, когда размер третьего по отдаленности от вершины подмассива больше или равен сумме их размеров. Асимптотика: O(n) в лучшем случае и O(nlogn) в среднем и худшем случае. Реализация нетривиальна, твердой уверенности в ней у меня нет, однако время работы она показала довольно неплохое и согласующееся с моими представлениями о том, как должна работать эта сортировка.

Подробнее timsort описан здесь:

Здесь
Здесь

Реализация:
void _timsort(int* l, int* r, int* temp) {
int sz = r - l;
if (sz <= 64) {
insertionsort(l, r);
return;
}
int minrun = sz, f = 0;
while (minrun >= 64) {
f |= minrun & 1;
minrun >>= 1;
}
minrun += f;
int* cur = l;
stack<pair<int, int*>> s;
while (cur < r) {
int* c1 = cur;
while (c1 < r - 1 && c1 <= *(c1 + 1)) c1++;
int* c2 = cur;
while (c2 < r - 1 && *c2 >= (c2 + 1)) c2++;
if (c1 >= c2) {
c1 = max(c1, cur + minrun - 1);
c1 = min(c1, r - 1);
insertionsort(cur, c1 + 1);
s.push({ c1 - cur + 1, cur });
cur = c1 + 1;
}
else {
c2 = max(c2, cur + minrun - 1);
c2 = min(c2, r - 1);
reverse(cur, c2 + 1);
insertionsort(cur, c2 + 1);
s.push({ c2 - cur + 1, cur });
cur = c2 + 1;
}
while (s.size() >= 3) {
pair<int, int*> x = s.top();
s.pop();
pair<int, int*> y = s.top();
s.pop();
pair<int, int*> z = s.top();
s.pop();
if (z.first >= x.first + y.first && y.first >= x.first) {
s.push(z);
s.push(y);
s.push(x);
break;
}
else if (z.first >= x.first + y.first) {
merge(y.second, x.second, x.second + x.first, temp);
s.push(z);
s.push({ x.first + y.first, y.second });
}
else {
merge(z.second, y.second, y.second + y.first, temp);
s.push({ z.first + y.first, z.second });
s.push(x);
}
}
}
while (s.size() != 1) {
pair<int, int*> x = s.top();
s.pop();
pair<int, int*> y = s.top();
s.pop();
if (x.second < y.second) swap(x, y);
merge(y.second, x.second, x.second + x.first, temp);
s.push({ y.first + x.first, y.second });
}
}
void timsort(int l, int r) {
int* temp = new int[r - l];
_timsort(l, r, temp);
delete temp;
}

Тестирование

Железо и система

Процессор: Intel Core i7-3770 CPU 3.40 GHz
ОЗУ: 8 ГБ
Тестирование проводилось на почти чистой системе Windows 10 x64, установленной за несколько дней до запуска. Использованная IDE – Microsoft Visual Studio 2015.

Тесты

Все тесты поделены на четыре группы. Первая группа – массив случайных чисел по разным модулям (10, 1000, 105, 107 и 109). Вторая группа – массив, разбивающийся на несколько отсортированных подмассивов. Фактически брался массив случайных чисел по модулю 109, а далее отсортировывались подмассивы размера, равного минимуму из длины оставшегося суффикса и случайного числа по модулю некоторой константы. Последовательность констант – 10, 100, 1000 и т.д. вплоть до размера массива. Третья группа – изначально отсортированный массив случайных чисел с некоторым числом «свопов» — перестановок двух случайных элементов. Последовательность количеств свопов такая же, как и в предыдущей группе. Наконец, последняя группа состоит из нескольких тестов с полностью отсортированным массивом (в прямом и обратном порядке), нескольких тестов с исходным массивом натуральных чисел от 1 до n, в котором несколько чисел заменены на случайное, и тестов с большим количеством повторений одного элемента (10%, 25%, 50%, 75% и 90%). Таким образом, тесты позволяют посмотреть, как сортировки работают на случайных и частично отсортированных массивах, что выглядит наиболее существенным. Четвертая группа во многом направлена против сортировок с линейным временем работы, которые любят последовательности случайных чисел. В конце статьи есть ссылка на файл, в котором подробно описаны все тесты.

Размер входных данных

Было бы довольно глупо сравнивать, например, сортировку с линейным временем работы и квадратичную, и запускать их на тестах одного размера. Поэтому каждая из групп тестов делится еще на четыре группы, размера 105, 106, 107и 108 элементов. Сортировки были разбиты на три группы, в первой – квадратичные (сортировка пузырьком, вставками, выбором, шейкерная и гномья), во второй – нечто среднее между логарифмическим временем и квадратом, (битонная, несколько видов сортировки Шелла и сортировка деревом), в третьей все остальные. Кого-то, возможно, удивит, что сортировка деревом попала не в третью группу, хотя ее асимптотика и O(nlogn), но, к сожалению, ее константа очень велика. Сортировки первой группы тестировались на тестах с 105элементов, второй группы – на тестах с 106и 107, третьей – на тестах с 107и 108. Именно такие размеры данных позволяют как-то увидеть рост времени работы, при меньших размерах слишком велика погрешность, при больших алгоритм работает слишком долго (или же недостаток оперативной памяти). С первой группой я не стал заморачиваться, чтобы не нарушать десятикратное увеличение (104 элементов для квадратичных сортировок слишком мало), в конце концов, сами по себе они представляют мало интереса.

Как проводилось тестирование

На каждом тесте было производилось 20 запусков, итоговое время работы – среднее по получившимся значениям. Почти все результаты были получены после одного запуска программы, однако из-за нескольких ошибок в коде и системных глюков (все же тестирование продолжалось почти неделю чистого времени) некоторые сортировки и тесты пришлось впоследствии перетестировать.

Тонкости реализации

Возможно, кого-то удивит, что в реализации самого процесса тестирования я не использовал указатели на функции, что сильно сократило бы код. Оказалось, что это заметно замедляет работу алгоритма (примерно на 5-10%). Поэтому я использовал отдельный вызов каждой функции (это, конечно, не отразилось бы на относительной скорости, но… все же хочется улучшить и абсолютную). По той же причине были заменены векторы на обычные массивы, не были использованы шаблоны и функции-компараторы. Все это более актуально для промышленного использования алгоритма, нежели его тестирования.