Pull to refresh

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

Reading time5 min
Views29K

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

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

Речь идёт о 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-визуализация
Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
Total votes 36: ↑35 and ↓1+34
Comments19

Articles