1 октября 2013 в 13:49

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


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

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

Речь идёт о 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-визуализация
Валерий Макаров @valemak
карма
59,2
рейтинг 0,1
Похожие публикации
Самое читаемое Разработка

Комментарии (19)

  • +1
    Скорее это эвристика к какому-нибудь основному алгоритму. Вырожденный случай — сортировка подсчетом.
  • +5
    Более надёжный метод — поразрядная сортировка. Классы предопределены заранее, за один проход считаем мощность классов, за другой — ставим классы на места. Дальше рекурсия. От равномерности распределения сложность почти не зависит.
  • 0
    Если знать исходное распределение, то и quicksort заработает быстрее, ведь там опорный элемент в идеале должен являться медианой. Тогда зачем еще один алгоритм.
    Основная проблема чисто конструктивная. Все привыкли, что функции сортировки делают все сами, а в данном случае надо как то описывать распределение, границы значений.
    В каком то узком спец софте, возможно стоит заморочиться.
    • +1
      Quicksort никак не удастся заставить работать быстрее, чем за O(n*log(n)). А зная место элемента, мы можем приблизить скорость к O(n) — чем точнее знаем место, тем лучше получится.
    • 0
      Даже если Quicksort будет знать исходное распределение, то быстрее не заработает.

      Основа Quicksort — это random shuffle в самом начале. А затем идет секционирование и сама сортировка.
      Shuffle нужен для вероятностной гарантии того, что секционирование пройдет правильно.
      Без «перетасовки» можно нарваться на производительность O(N^2) — это худший случай для Quicksort.

      А в лучшем случае, как уже сказали, Quicksort имеет O(N*lg(N)) и никак не меньше.
      • 0
        С перетасовкой тоже можно попасть на N^2 — если неудачно перетасовать. И на N — если удачно.
        А наивный квиксорт не предполагает сортировку. Просто кандидата в медианы берёт из первой позиции.
        Перетасовка, на самом деле, несущественна. Достаточно брать кандидата из позиции наугад.
  • 0
    Стабильность: Нестабильная


    Мне кажется все же это называется устойчивость сортировки, а «стабильность» — калька с английского.
    • 0
      «Стабільність покращено» (полит.-укр.). Дельное замечание, спасибо. Подправил.

      Я ещё размышляю над другим моментом. В результате FlashSort элементы попадают на примерно свои позиции, которые, при необходимости корректируются сортировкой вставками. Спорный вопрос, является ли FlashSort устойчивой или неустойчивой сортировкой, скорее речь идёт о некой "условной устойчивости" или "частичной устойчивости", если, конечно, в теории алгоритмов есть такие понятия.

  • –1
    GIF-анимация, длительность более 2-х минут

    Мсье знает толк…
    • 0
      137 кадров )))

      Способ приготовления следующий: алгоритм реализуется в Excel с помощью макросов VBA, каждый шаг экспортируется в изображения. Потом быстренько их сцепляем в анимацию. )))

      Я так уже нарисовал почти три десятка сортировок, недавно скатерть Улама симпатично получилась. Статьи про алгоритмы с «мультиками» ещё будут, идей много, реализация поставлена на поток. )))
      • 0
        Уважаю, труд немалый.
        А если сделать еще один шаг, то станет вообще шикарно, а именно — перевести в видео и, например, залить на youtube
        (Сделать такое можно с помощью www.virtualdub.org — открыть гифку и сохранить как .avi, дальше — ясно).
        Просматривать так будет намного удобнее — можно будет поставить на паузу и потупить, потому что гифка не оставляет шансов, приходится очень быстро думать :)
        • 0
          Ваша правда. Залил на Ютуб, видео в статье находится в разделе «Визуализация».
    • 0
      По-моему хабрастораж эту анимацию съел…
      • 0
        В Опере, Хроме, Мозилле работает… Какой браузер?
        • 0
          Видимо, это была какая-то особенность кэширования. Сейчас переоткрыл — всё замелькало.
  • 0
    А можно ссылку на формальное доказательство того, что мы можем приблизится к O(n)?
    • 0
      Есть doc-документ за авторством самого Нойберта, где он даёт разъяснения по поводу алгоритма. Я не силён в английском, по поводу временной сложности там вроде обоснование есть.
  • 0
    Почему-то до сих пор нет комментария о том, что m и n неспроста связаны именно таким коэффициентом.
    • 0
      sqrt(2)-1? И что в нём особенного?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.