Ещё одна сортировка распределением

Не подвергая сомнению эффективность вышеприведённых методов, предлагаю Вашему вниманию сортировку, которая при определённых входных данных легко уделывает по скорости любой другой алгоритм.

Речь идёт о FlashSort, хорошо обрабатывающей очень большие массивы с равномерно распределёнными данными.

Способ в 1998 году представил немецкий учёный Карл-Дитрих Нойберт. Его научная деятельность посвящена не столько теории алгоритмов, сколько физике твёрдого тела, биофизическим системам, физике элементарных частиц. Анализируя результаты экспериментов, Нойберт пришёл к выводу что большие массивы статистических данных вполне логично сортировать прибегнув к помощи теории вероятностей.

Суть

Принцип действия легко пояснить на конкретном примере.

Предположим, есть большой массив размерности n, значения элементов которого варьируются в диапазоне от 1 до 100. Если мы встречаем элемент со значением 50, то резонно полагаем, что его законное место – где-то посередине массива. Аналогично обстоят дела и с другими элементами: 5, наверное, должно находиться где-то поближе к началу структуры, 95 уместно задвинуть почти в конец. В результате таких небрежных манипуляций быстро получим почти отсортированный массив.

Раскидав на скорую руку элементы, остаётся применить какой-нибудь метод, который быстро доупорядочивает недоупорядоченное (сортировка вставками вполне сгодится).

Матан

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

Если за количество классов взять m, а также известны минимальный A_min и максимальный A_max элементы в массиве, то номер класса для элемента A_i вычисляется по следующей формуле:

Квадратные скобки в выражении означают целую часть. Классы таким образом будут перенумерованы от 1 до m. В дополнительном массиве Q[1..m] на позицию Q[K] заносится количество элементов из основного массива, принадлежащих соответствующему классу.

Затем, используя дополнительный массив, перераспределяем элементы массива, вставляя их на почти свои места. Алгоритмические нюансы – в коде java-программы приведённой ниже.

Визуализация

GIF-анимация, длительность более 2-х минут. Станет понятно, почему сортировку окрестили «мелькающей».

Эффективность по времени

Как уже упоминалось, алгоритм весьма эффективен на больших массивах с равномерно распределёнными данными. В этом случае FlashSort со средней временной сложностью O(n) легко уделывает и QuickSort и прочие эффективные методы сортировок.

В остальных ситуациях дела не столь блестящи. На коротких массивах, на длинных массивах с данными неравномерно распределёнными по величине, «мельтешащая сортировка» показывает хоть и приемлемые, но куда более скромные результаты. Нет также особого смысла применять основной алгоритм к почти упорядоченным массивам, проще сразу перейти к сортировке вставками.

Эффективность по памяти

Метод не шибко требователен к памяти, хотя и требует ресурсы под новый массив, количество элементов в котором – это количество классов. Весьма актуален вопрос: какое m брать? Чем больше классов – тем более качественным будет распределение, но и тем выше цена в виде дополнительной памяти. В большинстве случаев приемлемое соотношение «цена/качество» даёт формула

m ≈ 0.42 n,

выведенная Норбертом эмпирическим путём.

Если диапазон возможных значений элементов основного массива достаточно мал, то в качестве m можно (и даже желательно) взять целое расстояние между минимальным и максимальным элементами. В таких случаях, при соблюдении условия «1 значение = 1 класс», скорость сортировки по времени достигает лучшего результата O(n) при незначительных затратах на дополнительную память.

Реализация

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-визуализация