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

Когда речь заходит об эффективных алгоритмах сортировок, эрудированный читатель сразу же припомнит неувядаемую «быструю сортировку ^[1]», новомодную «сортировку Тима ^[2]», легендарную «сортировку слиянием ^[3]» и даже мудрёную «интроспективную сортировку ^[4]».

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

Речь идёт о 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;			
			}
		}
	}

}

Код взят отсюда ^[5], комментарии мои.

Характеристики алгоритма

Название	FlashSort (Мелькающая сортировка; Проблесковая сортировка)
Автор	Карл-Дитрих Нойберт
Год публикации	1998
Класс	Сортировка распределением
Стабильность	Нестабильная
Сравнения	Без сравнений
Временная сложность	худшая	O(n2)
	средняя	O(n+m)
	лучшая	O(n)
Сложность по памяти	всего	O(n+m)
	дополнительные данные	O(m)

Ссылки

FlashSort в английской Википедии ^[6]
Карл-Дитрих Нойберт, персональный сайт. ^[7]
FlashSort на Dr. Dobb's Journal ^[8]
Java-визуализация ^[5]

Автор: valemak

Источник ^[9]