28 апреля 2014 в 09:24

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


Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм который, пожалуй, должен знать любой программист. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени (причём, очень пристойная) – 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
Валерий Макаров @valemak
карма
60,2
рейтинг 0,1
Самое читаемое Разработка

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

  • +1
    PS: вопрос не потеме топика. А из какой колоды карта в заголовке статьи? Я бы прикупил колоду %)
    • +1
      Нашёл в Гугл-Картинках по запросу «joker card».

      По всей видимости, первоисточник тут. Там, правда только карты с картинками, 2-10 придётся нарисовать самому. Также автор не создавал различные масти, несколько карт нарисовал просто just for fun.

      Думаю, можно на основе того что есть «дорисовать» колоду и найти какое-нибудь рекламное агентство, специализирующееся на сувенирной продукции в своём городе, которое напечатает. Было бы время, навыки Фотошопа, деньги и желание.
  • +2
    Эм. А зачем изобретать сортировку с худшим временем O(n2), если такими же характеристиками обладает сортировка Хоара, но работает быстрее?
    • +7
      Во-первых, информатика ничем не хуже других точных наук. Так же как в математике доказываются все возможные теоремы и леммы (даже если они «бесполезные»), а в физике должны быть открыты все законы (даже если это крайне абстрактные рассуждения о петлевой квантовой гравитации). Так и в информатике, развитие будет происходить, если не успокоиться на быстрой сортировке (раз эффективно — зачем ещё что-то изучать?), а дотошно перебрать и остальные алгоритмы. Что-нибудь где-нибудь когда-нибудь — да пригодится.

      Во-вторых, быстрая сортировка — не панацея. Почитайте про «массивы-убийцы» и IntroSort — это интересно.

      В-третьих, изучая сортировки, часто ознакамливаешься с методами которые могут пригодиться где-нибудь ещё, необязательно для упорядочивания массивов. В данном случае более подробно изучаем такую полезную в хозяйстве вещь как двоичная куча.
  • +2
    Устойчивость — Устойчивая

    Серьезно? При построении кучи вся «устойчивость» поломается. Неустойчивая она.
    • 0
      Я, может, чего-то недопонимаю, так что рад любым поправкам. Век живи — век учись, как говорится. Очень может быть что я неверно трактую понятие устойчивость алгоритма.

      Устойчивость ломается не во время строительства кучи, а в момент когда всплывший в корень максимум меняется местами с последним элементом массива. Всё, в неотсортированной части массива больше не выполняется принцип «родитель больше потомков», сортирующее дерево полетело к чертям, перестраиваем заново. Но обмены максимумов на последние элементы неотсортированных подмассивов происходят в heapsort, но не в jsort.

      Сам по себе процесс построения кучи уменьшает энтропию структуры, добавляет ей упорядоченности, во всяком случае, несомненно той части массива, которая ближе к корню сортирующего дерева.

      В jsort строится 2 кучи подряд, причём вторая по счёту куча не ломает ту упорядоченность, которая создана первой кучей, ибо обе пирамиды разнонаправленные — одна двигает элементы поменьше в начало, другая — элементы побольше — в конец. Потом сразу сортировка вставками, которая без сомнения, является устойчивой. Или я всё перепутал?
      • +1
        Устойчивость ломается не во время строительства кучи

        В том числе и во время строительства.
        «2 1 1», первый проход.
                         //То из левого и правого потомка выбираем наименьшего
                        if (a[child] >= a[child + 1]) {
                            child += 1;
                        }
        

        возьмет вторую единицу и поменяет с двойкой. Все.
        • 0
          Нет, не всё.

          Ну, во-первых, в этом месте сравниваются два потомка (1 и 1). Двойка тут не при делах.

          Во-вторых, в этом же месте не происходит перестановка, а всего-навсего выбирается тот из потомков который поменьше (запоминается его индекс).

          В-третьих, обмен происходит (если происходит) сразу после выбора наименьшего потомка:
                      //Родитель меньше потомков?
                      if (T < a[child]) {
                          
                          //Тогда с этим родителем и его потомками разобрались
                          done = true;
                      
                      //Родитель НЕ меньше чем наименьший из его потомков.
                      //Перемещаем потомка на место родителя
                      //и с родителем в цикле сравниваем уже потомков этого потомка			
                      } else {			
          
                          a[parent] = a[child];
                          parent = child;
                          child = 2 * (parent + 1) - 1;
                          
                      }
          


          В данном случае двойка обменяется со второй единицей, то есть продвинется в «своём» направлении.

          • +3
            В данном случае двойка обменяется со второй единицей, то есть продвинется в «своём» направлении.

            С этим я не спорю, но вторая еденица обгонит первую.

            На всякий случай:
            Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. (с) Wikipedia


            Исходный массив:
            2 1a 1b
            


            Отсортированный устойчивой сортировкой:
            1a 1b 2
            


            Отсортированный JSort (1b поменялся с 2):
            1b 1a 2
            
    • 0
      Ах да, ещё нюанс.

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

      В jsort обе кучи использованы таким образом, что они двигают ключи в те стороны, откуда они «родом». То есть первая невозрастающая куча передвигает небольшие элементы в начало (где они и должны быть, ибо сортируем по возрастанию), вторая инвертированная неубывающая куча закидывает крупные элементы поближе к концу. Направление, по которым кучи раскидывают элементы совпадает с «общей линией партии».
      • +1
        То есть первая невозрастающая куча передвигает небольшие элементы в начало (где они и должны быть, ибо сортируем по возрастанию)

        Да, но среди нескольких одинаковых элементвов некоторых она передвинет, а некоторых нет. Причем передвинет не обязательно первых или последних, а каких получится.
        • 0
          Да, передвинет те элементы, которым «повезёт». Но они передвинутся именно в ту сторону, в которую нужно.
          • +2
            ... 1a 1b 1c ...
            


            «В нужную сторону» уехала 1b. Как она потом встанет между 1a и 1c?
            • 0
              Устойчивая сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. (Wiki)

              Jsort меняет местами одинаковые элементы (приходится это делать, чтобы заглянуть вниз по ветке и посмотреть нет ли там чего интересного), а значит она неустойчивая.

              Поэтому Вы правы, а я — нет. Подправил информацию, спасибо что заметили )))

              P.S. Не сразу заметил, что определение из Вики Вы указали в одном из предыдущих комментариев. Пора спать )))
  • +1
    Ничего себе «скромный труженик» — первым делом запатентовал свой алгоритм, а теперь занимающийся патентным троллингом на более-менее схожие алгоритмы.… Почитайте — во сколько он оценивает свою лицензию
    • 0
      Очень интересно ))) Ссылку на источник информации дайте, люблю запатентованные сортировки )))

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