Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

J-сортировка

Anna | 1.06.2014 | нет комментариев

Пирамидальная сортировка (она же сортировка кучей) – типичный алгорифм тот, что, вероятно, должен знать всякий программист. Ветхая добросердечная «пирамидка» знаменательна тем, что в автономности от комплекта данных у неё одна и та же трудность по времени (причём, дюже приличная) – O(n log n). Наилучших и вырожденных случаев для неё нет.

С момента изобретения способа (а в этом году алгорифм празднует свой полувековой юбилей) было много охочих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом – вот неполный список инноваций. Перечисленные алгорифмы правда при тестировании и опережают оригинал по безусловной скорости кто на 12, а кто и на 25%, в оценке временной трудности всё равно вертятся вокругO(n log n). При этом данные способы крайне изощрённо реализованы.

Своё видение пирамидальной сортировки предложил и скромный труженик Института Манитобы Джейсон Моррисон. При этом метод в некоторых случаях по скорости приближается к O(n).

HeapSort

Для тех кто не в теме, кратенько обрисую как работает пирамидальная сортировка.


Массив дозволено отсортировать, если на его основе строить и перестраивать сортирующее дерево, знаменитое как двоичная куча либо легко пирамида.

Что есть сортирующее дерево? Это дерево, у которого всякий родитель огромнее (либо поменьше, смотря в какую сторону оно сортирующее) чем его потомки.

Как из обыкновенного дерева сделать сортирующее дерево? Дюже легко – необходимо двигаться от потомков вверх к родителям и если потомок огромнее родителя, то менять местами. Если такой обмен произошёл, опустившегося на один ярус родителя необходимо сравнить с потомками ниже – может и там тоже будет причина для обмена.

Преобразовывая неотсортированную часть массива в сортирующее дерево, в результате в корень «всплывёт» крупнейший элемент. Обмениваем максимум с последним ключом неотсортированного подмассива. Конструкция перестанет быть сортирующим деревом, но в качестве моральной компенсации его неотсортированная часть станет поменьше на один узел. К этой неотсортированной части снова применим всю процедуру, то есть преобразуем её в сортирующее дерево с дальнейшей перегруппировкой обнаруженного максимума в конец. И так действуем до тех пор, пока неотсортированная часть не скукожится до одного-исключительного элемента.

Подход, что и говорить, сатирический, но при этом эксперты по алгорифмам подмечают у сортировки кучей целую кучу недостатков, как-то: малоустойчивость, хаотичность выборки, нечувствительность к примерно упорядоченным массивам и пр. Смущает всех также неулучшаемая скорость O(n log n), демонстрируемая сортировкой безусловно при всяких комплектах входящих данных.


Выдающиеся умы computer science предлагают разные мозговыносящие идеи (тернарные пирамидычисла Леонардодекартовы деревья) с поддержкой которых дозволено усовершенствовать алгорифм. Джейсон Моррисон (Jason Morrison, сортировка названа в честь автора) предложил что-то противоположное – для оптимизации нужно не усложнять, а максимально упрощать.

JSort

Канадский учёный пришёл к итогу, что снова перестраивать кучу для всякого элемента – дорогое наслаждение. Так уж ли нужно массив из n элементов решительно перелопачивать n раз?

Если для массива построить каждого пару куч (нисходящую и восходящую), то это гораздо его упорядочит в обоих направлениях.


Вначале необходимо осуществить построениеневозрастающей кучи. В итоге меньшие элементы повсплывают в верхние узлы пирамиды (что будет соответствовать левой половине массива), минимальный элемент вообще окажется в корне. Чем выше элементы находятся в сортирующем дереве – тем больше упорядоченной будет соответствующая часть массива. Элементы находящиеся ближе к листьям дерева (им будет соответствовать вторая половина массива) будут иметь менее упорядоченный вид, от того что они не сравнивались друг с ином, а легко были оттеснены на задворки в итоге перемещения их родителей.

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

Соорудив такие себе близняшки-пирамидки, получаем во многом упорядоченный массив. Довершает делосортировка вставками. Данный алгорифм имеет крайне скромную среднюю трудность по времени O(n2), но творит чудеса на массивах, которые теснее примерно отсортированы. Их сортировка вставками щёлкает как орешки.

Трудность по времени

Испробуем оценить при самом благоприятном раскладе. Однократное пирамидостроение – это O(n). Куч мы наложили две, так что получаем O(2n). Примерно упорядоченный массив сортировка вставками может отсортировать за высокие O(n). Всеобщая трудность получается O(3n), что тоже самое что и O(n).

Однако, на практике всё выглядит скромнее. Возьмём, скажем, такой неотсортированный массив, содержащий числа от 1 до 30:

Возведем обыкновенную невозрастающую кучу:

Первая треть массива приняла абсолютно благообразный вид, в середине – кто в лес кто по дрова, конец массива пока тоже не впечатляет.

Возведем сейчас «зеркальную» неубывающую кучу:

Конец массива приметно похорошел. В середине отслеживаются некие зачатки упорядоченности, но выглядит не так гламурно, как левый и правый сектор. В тезисе, массив абсолютно созрел, Дабы скормить его сортировке вставками.

Обратите внимание на ключ со значением 20.Отчего данный элемент завязнул в первой трети массива? Тривиально не повезло – перед построением «зеркальной» неубывающей кучи все родители вверх по ветке оказались огромнее по значению (в корне теперь 17, но данный ключ утонет в левой половине дерева и уступит место 30). Следственно в пирамиде ему не суждено возвыситься правда бы на ступеньку.

Чем длиннее массив, тем Почаще такие вырожденные узлы будет появляться. А значит, в средней полосе длинных массивов сортировке вставками придётся довольно потрудиться. Подаваемый ей массив для обработки будет не то Дабы примерно отсортированным, а скорее примерно примерно отсортированным. На дюже длинных списках временная трудность у Insertion Sort будет, безусловно, не её средние/худшие O(n2), но и до O(n) будет вдалеке.

Между прочим

Есть ещё один алгорифм сортировки с дюже схожим названием – J sort, которую разработал Джон Коен (John Cohen). Это тоже гибридный алгорифм, применяется для обработки двусвязных списков. Комбинирует в себенитевидную сортировку (Strand sort) и сортировку перетасовкой (Shuffle sort). Но это теснее иная история.

Колляции алгорифма

Наименование Jsort (J-сортировка)
Автор Джейсон Моррисон (Jason Morrison)
Класс Гибридная сортировка (кучей вставками)
Стабильность Неустойчивая
Сопоставления Есть
Временная трудность лучшая O(n)
средняя ?
худшая O(n2)
Трудность по памяти каждого O(n)
добавочные данные O(1)

Добавочно

Heap sort на Java

/**
 * Демонстрационный алгорифм для пирамидальной сортировки
 * Авторы алгорифма - J. W. J. Williams и R. W. Floyd
 *
 * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
 *
 * @author Jason Harrison@cs.ubc.ca
 * @version 	1.0, 23 Jun 1995
 */ 

class HeapSortAlgorithm extends SortAlgorithm {

	//Сортировка кучей
    void sort(int a[]) throws Exception {	

		int N = a.length;

		//Создаём из массива сортирующее дерево
		//Максимальный элемент окажется в корне.
		for (int k = N / 2; k > 0; k--) downheap(a, k, N);

		//Избавляемся от максимумов 
		//и перетряхиваем сортирующее дерево
		do {

			//Меняем максимум с последним элементом...
			int T = a[0];
			a[0] = a[N - 1];
			a[N - 1] = T;

			//... и перестравиваем сортирующее дерево
			//для неотсортированной части массива			
			N = N - 1;		
			downheap(a, 1, N);		

		} while (N > 1); //До последнего элемента

    }

	//Просматриваем ветку и в её корень перемещаем крупнейший узел
    void downheap(int a[], int k, int N) throws Exception {		

		//В корне поддерева
		//запоминаем родителя
		int T = a[k - 1];

		//Смотрим потомков в пределах ветки
		while (k <= N / 2) {		

			int j = k   k;//Левый потомок

			//Если есть правый потомок, 
			//то сопоставляем его с левым
			//и из них выбираем крупнейший
			if ((j < N) && (a[j - 1] < a[j])) j  ;	

			//Если родитель огромнее (либо равен) наибольшего потомка...
			if (T >= a[j - 1]) {

				//... то значит всё в порядке в этой ветке		
				break;	

			} else { //Если родитель поменьше наибольшего потомка...	

				//... то потомок становится на место родителя
				a[k - 1] = a[j - 1];
				k = j;

			}
		}

		//Родитель в результате меняется местами с наибольшим из потомков
		//(либо остаётся на своём месте, если все потомки поменьше его)
		a[k - 1] = T;

    }

}

 

YouTube-версия анимации Heap sort

 

Jsort на Java

/**
 * Демонстраицонный алгорифм для J-сортировки (JSort).
 * Автор алгорифма - Джейсон Моррисон (Jason Morrison) 
 * <http://www.scs.carleton.ca/~morrison>	
 * 
 * JSortAlgorithm.java
 *
 * Автор реализации - Патрик Морин
 * @author Patrick Morin
 */ 
class JSortAlgorithm extends SortAlgorithm {

	//С помошью неполной НЕУБЫВАЮЩЕЙ кучи 
	//крупные элементы закидываем поближе к концу массива
    void reheap (int a[], int length, int i) throws Exception {

		//С этим родителем ещё не разобрались
		boolean done = false;

		//Запоминаем отдельно родителя 
		//и глядим на его потомка слева
		int T = a[i];
		int parent = i;
		int child = 2 * (i   1) - 1;

		//Просматриваем потомков, а также потомков потомков
		//и сопоставляем их с родителем (если что - передвигаем потомков налево)
		//Цикл продолжается пока не вывалимся за пределы массива
		//или пока не обменяем какого-нибудь потомка на родителя.		
		while ((child < length) && (!done)) {

			//Если правый потомок в пределах массива
			if (child < length - 1) {
				//То из левого и правого потомка выбираем наименьшего
				if (a[child] >= a[child   1]) {
					child  = 1;
				}
			}

			//Родитель поменьше потомков?
			if (T < a[child]) {

				//Тогда с этим родителем и его потомками разобрались
				done = true;

			//Родитель НЕ поменьше чем минимальный из его потомков.
			//Перемещаем потомка на место родителя
			//и с родителем в цикле сопоставляем теснее потомков этого потомка			
			} else {			

				a[parent] = a[child];
				parent = child;
				child = 2 * (parent   1) - 1;

			}
		}

		//Родитель, с которого всё начиналось
		//передвигается ближе к концу массива
		//(либо остаётся на месте если не повезло)
		a[parent] = T;

    }

	//С помошью неполной НЕВОЗРАСТАЮЩЕЙ кучи 
	//мелкие элементы закидываем поближе к началу массива
    void invreheap (int a[], int length, int i) throws Exception {

		//С этим родителем ещё не разобрались
		boolean done = false;

		//Запоминаем отдельно родителя 
		//и глядим на его потомка слева
		int T = a[length - 1 - i];
		int parent = i;
		int child = 2 * (i   1) - 1;

		//Просматриваем потомков, а также потомков потомков
		//и сопоставляем их с родителем (если что - передвигаем потомков)
		//Цикл продолжается пока не вывалимся за пределы массива
		//или пока не обменяем какого-нибудь потомка на родителя.
		while ((child < length) && (!done)) {

			//Если левый потомок в пределах массива
			if (child < length - 1) {

				//То из левого и правого потомка выбираем наибольшего
				if (a[length - 1 - child] <= a[length - 1 - (child   1)]) {
					child  = 1;
				}

			}

			//Родитель огромнее потомков?
			if (T > a[length - 1 - child]) {

				//Тогда с этим родителем и его потомками разобрались
				done = true;

			} else {

				//Родитель НЕ огромнее чем крупнейший из его потомков.
				//Перемещаем потомка на место родителя
				//и с родителем в цикле сопоставляем теснее потомков этого потомка	
				a[length - 1 - parent] = a[length - 1 - child];
				parent = child;
				child = 2 * (parent   1) - 1;

			}
		}

		//Родитель, с которого всё начиналось
		//передвигается ближе к началу массива
		//(либо остаётся на месте если не повезло)
		a[length - 1 - parent] = T;

    }

	//Основная процедура сортировки
    void sort(int a[]) throws Exception {

		//Строим неубывающую кучу
		//Большие элементы из начала массива
		//закидываем поближе к концу
		for (int i = a.length-1; i >= 0; i--)
			reheap (a, a.length, i);

		//Строим невозрастающую кучу
		//Меньшие элементы из конца массива
		//закидываем поближе к началу
		for (int i = a.length - 1; i >= 0; i--)
			invreheap (a, a.length, i);

		//Массив ПРИМЕРНО упорядочен
		//Досортировываем вставками
		for (int j = 1; j < a.length; j  ) {
			int T = a[j];
			int i = j - 1;
			while (i >= 0 && a[i] > T) {
				a[i   1] = a[i];
				i -= 1;
			}
			a[i   1] = T;
		}

    }
}

 

YouTube-версия анимации Jsort

 

Ссылки

Jsort в Википедии
Страница Джейсона Моррисона на сайте Института Манитобы
Страница Джейсона Моррисона на LinkedIn

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB