Когда речь заходит об эффективных алгоритмах сортировок, эрудированный хабраюзер сразу же припомнит неувядаемую «быструю сортировку», новомодную «сортировку Тима», легендарную «сортировку слиянием» и даже мудрёную «интроспективную сортировку».
Не подвергая сомнению эффективность вышеприведённых методов, предлагаю Вашему вниманию сортировку, которая при определённых входных условиях легко уделывает по скорости любой другой алгоритм.
Речь идёт о FlashSort, хорошо обрабатывающей очень большие массивы с равномерно распределёнными данными.
Способ в 1998 году представил немецкий учёный Карл-Дитрих Нойберт. Его научная деятельность посвящена не столько теории алгоритмов, сколько физике твёрдого тела, биофизическим системам, физике элементарных частиц. Анализируя результаты экспериментов, Нойберт пришёл к выводу что большие массивы статистических данных вполне логично сортировать, прибегнув к теории вероятностей.
Суть
Принцип действия легко пояснить на конкретном примере.
Предположим, есть большой массив из n элементов, значения которых варьируются в диапазоне от 1 до 100. Если мы встречаем элемент со значением 50, то резонно полагаем, что его законное место – посередине массива. Аналогично обстоят дела и с другими элементами: 5, наверное, должно находиться поближе к началу структуры, 95 уместно задвинуть почти в конец. В результате таких небрежных манипуляций быстро получим почти отсортированный массив.
Перераскидав на скорую руку элементы, остаётся применить какой-нибудь метод, который быстро доупорядочивает недоупорядоченное (сортировка вставками вполне сгодится).
Матан
Основная задача сводится к тому, что все элементы массива в зависимости от их величин нужно распределить по нескольким классам. Самые маленькие числа находятся в первом классе, самые большие – в последнем, остальные числа – в промежуточных группах.
Если за количество классов взять m, а также известны минимальный Amin и максимальный Amax элементы в массиве, то номер класса для элемента Ai вычисляется по следующей формуле:
С точки зрения теории вероятностей класс K — не что иное как квантиль, указывающий на место элемента Ai в нашей модели распределения.
Квадратные скобки в выражении означают целую часть. Классы таким образом будут перенумерованы от 1 до m. В дополнительном массиве Q[1..m] на позицию Q[K] заносится количество элементов из основного массива, принадлежащих соответствующему классу.
Затем, используя дополнительный массив, перераспределяем элементы основного массива, вставляя их на почти свои места. Алгоритмические нюансы – в коде java-программы приведённой ниже.
Визуализация
Длительность более 2-х минут. Станет понятно, почему сортировку окрестили «мелькающей».
YouTube-версия
Эффективность по времени
Как уже упоминалось, алгоритм весьма эффективен на больших массивах с равномерно распределёнными данными. В этом случае FlashSort со средней временной сложностью O(n) существенно опережает и QuickSort и прочие эффективные методы сортировок.
В остальных ситуациях дела не столь блестящи. На коротких массивах, на длинных массивах с данными неравномерно распределёнными по величине, «мельтешащая сортировка» показывает хоть и приемлемые, но куда более скромные результаты.
Нет также смысла применять главный алгоритм к не до конца упорядоченным массивам, проще сразу перейти к сортировке вставками. Почти отсортированный массив для FlashSort — вырожденный случай, и в особо неудачных ситуациях наблюдается худшая временная сложность O(n2).
Эффективность по памяти
Метод не шибко требователен к памяти, хотя и требует ресурсы под новый массив, количество элементов в котором – это количество классов. Весьма актуален вопрос: какое m брать? Чем больше классов – тем более качественным будет распределение, но и тем выше цена в виде дополнительной памяти. В большинстве случаев приемлемое соотношение «цена/качество» даёт формула
m ≈ 0.42 n,
выведенная Нойбертом эмпирическим путём.
Если диапазон возможных значений элементов основного массива достаточно мал, то в качестве m можно (и даже желательно) взять целое расстояние между минимальным и максимальным элементами. В таких случаях, при соблюдении условия «1 значение = 1 класс», скорость сортировки по времени достигает лучшего результата O(n) при незначительных затратах на дополнительную память.
Реализация
FlashSort на Java.
import java.util.Arrays;
public class FlashSortAlgorithm extends SortAlgorithm {
void sort(int[] a) throws Exception {
FlashSort(a); //Сначала FlashSort
InsertionSort(a); //Напоследок сортировка вставками
}
//FlashSort, применив которую получим
//почти упорядоченный массив
private void FlashSort(int [] a) throws Exception {
int n = a.length; //Размерность массива
int m = n * 0.42; //Количество классов
int [] l = new int[m]; //Вспомогательный массив
int i = 0, j = 0, k = 0; //Счётчики в циклах
int anmin = a[0]; //Минимальный элемент
int nmax = 0; //Индекс максимального элемента
//Ищем минимальный и максимальный элементы
for (i = 1; i < n; i++) {
if (a[i] < anmin)
anmin = a[i];
if (a[i] > a[nmax])
nmax = i;
}
//Минимум = максимум? Тогда массив
//состоит из одинаковых элементов.
//А значит, он отсортирован!
if (anmin == a[nmax])
return;
//Неизменяемая часть квантиля
double c1 = ((double) m - 1) / (a[nmax] - anmin);
//Заполняем массив распределения
//Каждый элемент вспомогательного массива -
//это количество чисел соответствующего класса
for (i = 0; i < n; i++) {
k = (int) (c1 * (a[i] - anmin));
l[k]++;
}
//Во вспомогательном массиве каждый элемент
//(начиная со 2-го)увеличим на величину предыдущего.
//После этого каждый элемент вспомогательного массива
//это индекс элемента в основном массиве на котором
//должны заканчиваются числа соответсвующего класса
for (k = 1; k < m; k++){
l[k] += l[k - 1];
}
//Меняем местами первый и максимальный элемент в массиве
//Это делается для того чтобы в основном цикле алгоритма
//максимальный элемент сразу поставить на своё место
int hold = a[nmax];
a[nmax] = a[0];
a[0] = hold;
//Основной алгоритм
//Количество элементов, перемещённых
// в их правильные классы
int nmove = 0;
//Временный контейнер, в которую будем помещать элементы
//на чьи места только что вставили "правильные" элементы
int flash;
//Индекс неупорядоченного элемента
//начинающего новый класс, элементы которого ещё
//не перемещены
j = 0;
//Класс очередного перемещаемого элемента
//это число всегда в пределах от 1..m-1
k = m - 1;
while (nmove < n - 1) {
while (j > (l[k] - 1)) {
j++;
k = (int) (c1 * (a[j] - anmin));
}
flash = a[j];
while (!(j == l[k])) {
k = (int) (c1 * (flash - anmin));
hold = a[l[k] - 1];
a[l[k] - 1] = flash;
flash = hold;
l[k]--;
nmove++;
}
}
}
//Финальная сортировка простыми вставками
//Досортировывает то что не отсортировало FlashSort
private void InsertionSort(int [] a) throws Exception {
int i, j, hold;
for (i=a.length-3; i>=0; i--) {
if (a[i+1] < a[i]) {
hold = a[i];
j=i;
while (a[j+1] < hold) {
a[j] = a[j+1];
j++;
}
a[j] = hold;
}
}
}
}
Код взят отсюда, комментарии мои.
Коллекцию реализаций на различных ЯП (Ада, Си, Бейсик, Форт, Фортран, Ява, Паскаль) можно обнаружить на сайте профессора.
Характеристики алгоритма
| Название | FlashSort (Мелькающая сортировка; Мигающая сортировка; Проблесковая сортировка) | |
|---|---|---|
| Автор | Карл-Дитрих Нойберт | |
| Год публикации | 1998 | |
| Класс | Сортировка распределением | |
| Устойчивость | Неустойчивая | |
| Сравнения | Без сравнений | |
| Временная сложность | худшая | O(n2) |
| средняя | O(n+m) | |
| лучшая | O(n) | |
| Сложность по памяти | всего | O(n+m) |
| дополнительные данные | O(m) | |
Ссылки
FlashSort в английской Википедии
Карл-Дитрих Нойберт, персональный сайт.
FlashSort на Dr. Dobb's Journal
Java-визуализация
