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

JavaСовершенный кодАлгоритмы
Из песочницы

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

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

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

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

Суть


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

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

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

Матан


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

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


image

С точки зрения теории вероятностей класс 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-визуализация
Теги:сортировкаflashsortflash sort
Хабы: Java Совершенный код Алгоритмы
+34
27,1k 214
Комментарии 19

Похожие публикации

Лучшие публикации за сутки