10 ноября 2013 в 07:53

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


Данная разновидность поразрядной MSD-сортировки «заточена» для строк. Впрочем, алгоритм так назван отнюдь не за лексическую специализацию. Автор Аллен Бичик (Allen Beechick) выбрал название в честь себя любимого, ABCsort расшифровывается как Allen Beechick Character sort.

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

Что касается алгоритма, то это единственно известная мне сортировка, за использование которой её изобретатель требует деньги.


Бичик



Баптист-консерватор, ярый противник претеризма. Протестантская ересь разгромлена Алленом ещё 30 лет назад в его неувядаемом бестселлере «Вознесение в преддверии Великой Скорби» («The Pre-Tribulation Rapture», 1980 г., переиздание в 1999 г.). Итогом многолетних религиозных изысканий нашего героя является книга «Разгадка Вознесения – соберём паззл вместе» («The Rapture Solution, Putting the Puzzle Together»).

Преимущества


Автору очень нравится расхваливать свой алгоритм и он с нескрываемым удовольствием на сайте сортировки (web-архив) перечисляет её многочисленные достоинства:

  • В среднем в 2-3 раза быстрее чем быстрая сортировка, в зависимости от списка.
  • Устойчивость.
  • Нет вырожденных случаев.
  • Не использует сравнения.
  • Не использует обмены.
  • Не использует опорные элементы.
  • Работает одинаково хорошо с короткими и с длинными списками.
  • Экономична по памяти.
  • Первые отсортированные элементы уже доступны для использования в других процессах, пока сортируется оставшаяся часть списка (другими словами – сортировка устойчива).


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

Чем ещё хороша сортировка – в отличие от классической MSD-radix sort сортирует не по всем разрядам. Процесс прекращается сразу как только список будет отсортирован, а не до тех пор пока не обработаются все разряды. Так же можно указать количество первых разрядов по которым произведётся упорядочивание, если старшинство по младшим разрядам не имеет особого значения.

Алгоритм


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

Один из них назовём трекер слов (WT – word tracker), с помощью него мы будем группировать слова, имеющих одинаковые буквы в i-м разряде. Для самого первого найденного такого слова в списке заносится значение 0. Для каждого последующего найденного слова с той же буквой в i-м разряде в трекере слов отмечается индекс предыдущего слова, соответствующего этому же признаку.



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

Ещё один массив – трекер символов (LT – letter tracker). В нём отмечаются индексы самого первого (или последнего) слова в списке, в котором в соответствующем разряде находится определённый символ. Отталкиваясь от этого слова, с помощью трекера слов восстанавливается цепочка всех остальных лексем, имеющих в i-м разряде соответствующую букву.


Сейчас в таблице приведены индексы последних слов из списка, которые начинаются с той или иной буквы.

В данных момент с помощью этих двух таблиц можно вытащить все слова, к примеру, начинающиеся на букву «B». Для этого нужно взять значение ячейки LT[1, b] = 9 – это индекс последнего слова из списка начинающегося на «b» — Beckie. У данного слова в трекере слов трек-значение сейчас: WT[9] = 8. Это индекс предыдущего слова на «b» — Belinda. В ячейке WT[8] хранится значение 6 – под этим индексом обнаруживается Barbara, которая в свою очередь указывает на индекс Beatrix: WT[6] = 3. Трек-значение для Beatrix равно нулю, то есть относительно неё в списке нет предыдущих слов начинающихся на B.

Создавая и прослеживая подобные цепочки слов, рекурсивно продвигаясь от старших разрядов к младшим, в итоге весьма быстро формируются новые последовательности, упорядоченные в алфавитном порядке. Отсортировав слова на «A», затем сортируется «B», затем «C» и далее по алфавиту.


Демо-код на C++ (автор - Линн Д. Ярбро)
/*            
 ** ABCsort на C
 ** Представленный в данной программе алгоритм сортировки является собственностью
 ** Аллена Бичика (Allen Beechick) и находится под защитой законодательства США, 
 ** Патент №5218700.
 ** Использование данного алгоритма без разрешения владельца запрещено законом.
 ** Автором этой программы является:
 ** Линн Д. Ярбро (Lynn D. Yarbrough)
 ** Палм Десерт (Palm Desert), Калифорния  
 **====================================================================== 
*/  
	#include <malloc.h> 
	#include <stdio.h> 
	#include <stdlib.h> 

	long *RT;  /* Таблица записей */
	long **LT; /* Таблица символов */

	void ABCsort (int keys) { /* Количество используемых ключевых полей */ 
	
		void process (int, int); 
		long register i, j, recno; 
		int register c; 
		int nodup = noduplicates; 
		long start, step, stop; 

		/* Выделяем хранилища под внутренние таблицы */ 
		LT = lmatrix(1, keys, alphamin, alphamax); 
		RT = lvector(1, N); 
		
		/* Инициализация таблицы символов: */ 
		for (j = alphamin; j <= alphamax; j++) { 
			for (i = 1; i <= keys; i++) 
				LT[i][j] = 0; 
		} 
		
		/* Обеспечиваем стабильность сортировки */ 
		if ((keys & 1) ^ nodup) {
			start = N; stop = 0; step = -1;
		} else {
			start = 1; 
			stop = N + 1; 
			step = 1;
		}
		
		/* Этап 1 */
		/* Группируем слова по первой букве */
		for (recno = start; recno != stop; recno += step) { 
			c = GetNextField(recno, 1); 
			RT[recno] = LT[1][c]; 
			LT[1][c] = recno; 
		}		
		
		/* Запускаем процесс уточнения положения записей в списке. */		
		process(1, keys); 	

		free_lmatrix(LT, 1, keys, alphamin, alphamax); 
		free_lvector(RT, 1, N); 
		
	} 
	
	/* ======================================================== */ 
	
	/* Функция обработки данных после 1-го этапа: */ 
	/* Перегруппировываем слова, переходя от одной буквы к следующей */
	void process (int level, int keys) { 
	
		long i, newlevel, nextrec, recno; 
		int nodup = noduplicates; 
		unsigned char c; 
		
		/* Цикл по алфавиту */
		for (i = alphamin; i <= alphamax; i++) {
		
			/* Ищем использование i-й буквы */ 
			recno = LT[level][i]; 
			LT[level][i] = 0; 
			
			/* Сканируем ветвь для этой буквы */ 
			while (recno != 0) {
				/* i-й символ используется только однажды, значит  
				отсортированная часть массива пополнилась новым элементом */ 
				if (RT[recno] == 0) {				
					PutCurrRecord(recno); 
					recno = 0; 
					continue; 
				} else {
					/* В случае многократного использования i-го символа: */ 
					if (level == keys) {
						/* Вывод всех данных на этом уровне: */ 
						while (recno != 0) {
							/* Добавляем текущую запись в таблицу индексов */ 
							PutCurrRecord(recno); 
							recno = RT[recno]; 
							if (nodup) recno = 0; 
						} 
					} else { 
						/* Продолжать уточнять порядок слов:*/ 
						/* опускаемся на уровень вниз */ 
						newlevel = level + 1; 
						while (recno != 0) { 
							nextrec = RT[recno]; 
							c = GetNextField(recno, newlevel); 
							RT[recno] = LT[newlevel][c]; 
							LT[newlevel][c] = recno; 
							recno = nextrec; 
						}  
						/* Продолжаем процесс уточнения */ 
						process(newlevel, keys); 
					} 
				} 
			} 
		} 
	} 


Youtube-версия анимации




Сложность по времени


В целом можно уверенно говорить о средней временной сложности O(k * n), где k — количество обрабатываемых разрядов.

Компания «ASIC DESIGN & MARKETING», занимающаяся разработкой интегральных микросхем, имплементировала алгоритм при создании ППВМ (Программируемых пользователем вентильных матриц). По утверждению инженеров компании, ABCsort работает от 2,5 до 10 раз быстрее чем QuickSort. Об этом можно почитать в этом PDF-отчёте.

Сложность по памяти


Для сортировки потребуется два вспомогательных массива: двухмерный для трекера символов, которым при оценке сложности можно пренебречь. А также массив из n элементов для трекера слов. То есть, общая оценка дополнительной памяти: O(n).



Цена


Если Вам приглянулся алгоритм, то не торопитесь запускать его в продакшен, не уплатив владельцу отступных. Способ запатентован (ссылка на pdf патента) и за его пиратское использование на вора обрушится карающий меч американского правосудия.

Цена за сортировку вполне божеская, 49 долларов. За эту сумму довольный клиент получает:

  • BeechickSort.dll. Тут содержится функция сортировки которую можно вызывать из любой программы.
  • BeechickSortDemo.exe, а также сорцы к ней – BeechickSortDemo.cpp.
  • Примеры исходных данных для сортировки: SchoolAddresses.txt (записи с несколькими полями, сортировать можно по-разному) и ShuffledText.txt (набор случайных слов из словаря).
  • SortDemo.htm – веб-интерфейс для задания параметров сортировки.


Если накинуть сверху 39 условных единиц, то DLL-ку отдадут с прокомментированными исходниками на C++.

Также предприимчивый религиовед-программист клянётся всеми святыми, что если ABC sort не окажется хотя бы вдвое быстрее чем Quick sort, то он безоговорочно вернёт деньги.

Тем, у кого остались вопросы по поводу патента, Аллен Бичик даёт исчерпывающие ответы:
Может, стоит продать алгоритм Microsoft?

Я пытался. Это было до того как я получил патент. Ребята из “Microsoft” сказали, что запатентовать не получится, поскольку это очередная разновидность поразрядной сортировки; к тому же, она их не впечатлила. Но в патентном ведомстве разглядели уникальность алгоритма.

Почему бы Вам не передать алгоритм в общественное достояние?

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


Характеристики алгоритма


Название ABC-сортировка (ABCsort, Allen Beechick Character sort);
Сортировка Бичика (Beechick sort)
Автор Аллен Бичик (Allen Beechick)
Год публикации 1993
Класс Сортировка распределением
Подкласс Поразрядная сортировка
Устойчивость Устойчивая
Сравнения Без сравнений
Временная сложность худшая средняя лучшая
O(k * n) O(k * n) O(n)
Сложность по памяти O(n)


Ссылки


Сайт сортировки (web-архив)
Реализация Лина Д. Ярбро на C++ (web-архив)
Патент на алгоритм (pdf)
Аппаратная реализация в интегральных миксросхемах (pdf)

Аллен Бичик


На Фейсбуке
На LinkedIn
Сайт книги «Разгадка Вознесения – соберём паззл вместе»


Голосование

Считаете ли Вы допустимым патентование компьютерных алгоритмов с последующим требованием роялти?
73%
(507)
Нет. Алгоритмы, как и любые законы Вселенной, принадлежат абсолютно всем.
27%
(192)
Да. Алгоритм – это изобретение, автор имеет полное моральное право на вознаграждение.

Проголосовало 699 человек. Воздержалось 127 человек.

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

Валерий Макаров @valemak
карма
60,2
рейтинг 0,1
Похожие публикации
Самое читаемое Разработка

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

  • +2
    Платный алгоритм сортировки? С учетом того, что сорцы доступны, я что-то сомневаюсь, что все, у кого есть этот алгоритм в программах платили за него деньги
  • +4
    Про сложность не уверен. Если у всех строк первые 10^7 символов совпадают, не придётся ли алгоритму проверить их все, прежде чем перейти собственно к сортировке? И не будет ли память для вспомогательных массивов зависеть ещё и от длины строк?
    • +1
      >>> Если у всех строк первые 10^7 символов совпадают, не придётся ли алгоритму проверить их все, прежде чем перейти собственно к сортировке?

      Линн Д. Ярбро и так и сяк тестировал сортировку, о чём он более-менее подробно описал здесь.

      Действительно, худшая временная сложность у сортировки O(n * k), где k — количество обрабатываемых разрядов. Как раз относится к предложенному Вами варианту.

      Немного подкорректировал таблицу характеристик алгоритма, добавил худшую и лучшую временную сложность.

      >>> И не будет ли память для вспомогательных массивов зависеть ещё и от длины строк?

      Трекер слов (основной пожиратель дополнительной памяти) — точно не будет. Сортировка устроена так что при любых раскладах в качестве word tracker достаточно только одномерного массива из n элементов.

      От длины строк прямо зависит трекер букв, но если сортировать список из миллиона элементов то его размерами можно пренебречь при оценке памяти.
  • +3
    Ну вот, лишили магистра богословия денег на постройку крайне важного храма.
  • +10
    Так это же сортировка при помощи trie, просто с оптимизированным представлением trie. Патент анулировать.
    • +4
      Я пытался пообщаться с Бичиком по поводу «уникальности» алгоритма, но он меня проигнорировал. :)
  • 0
    Казалось бы, это полностью эквивалентно поразрядной сортировке
    • +1
      Полная эквивалентность — нет. Улучшенная (оптимизированная) версия — да.

      В классической radix sort просматриваются все разряды. В ABC-сортировке перебор разрядов прекращается как только список упорядочен.
  • +1
    Но ведь сортировка со средним временем работы O(n) невозможна, не так ли? Из статьи совсем непонятно, откуда взялась эта оценка именно для среднего (а не лучшего) случая.
    • 0
      Я с Вами соглашусь, средняя временная сложность O(n) — это последствия моего куцего перевода с английского.
      Средняя временная сложность у этой сортировки — O(n * k), где k — количество обрабатываемых разрядов. Внёс изменения в статью, спасибо за замечание.
    • 0
      Ну почему же невозможна? Например можно 32 разрядные числа сортировать за линейное время (в худшем случае), можно и 64 разрядные, и 128 разрядные и т.д…
      • 0
        Числа и строки подходят для блочной сортировки, которая может происходить за линейное время, так как их можно не только сравнивать, но и распределять по «корзинам».
        • 0
          Это как-то опровергает то что я написал? Я тоже самое и имел ввиду.
          • –1
            Я хотел понять, думаем ли мы об одном и том же, а не оспорить.
      • 0
        Ограничивая диапазон значений — конечно можно. Но в общем массив чисел или строк сортировать за линейное время нельзя.
        • 0
          Я именно об этом и говорю. Для целых, например, ограничения на размер элемента достаточно чтобы отсортировать за линейное время. Также если строки ограничить по длине — то сортировку можно выполнять за линейное время.
          Никто и не говорит что в общем случае можно, т.к. в общем случае только чтение будет зависеть не только от размера массива, но и от размера элементов в этом массиве.
    • 0
      Эта сортировка не со средним, а с худшим временем O(n*k). В случае строк получится даже O(V), где V — общий объём входных данных.
  • 0
    Фамилия создателя сортировки многое говорит о нем. =)
    • +1
      beech (англ.) — бук, буковое дерево. Скорее всего отсюда и произошла фамилия.

      Я ж, надеюсь, вы не слово bitch имели в виду. :)
      • +1
        А может быть, bee-chick?
        • +1
          Пчелоцыплёнок? :)
          • +2
            Именно :)
            • +4
              Ещё точнее — Пчелоцып. :)
  • +6
    В РФ патенты на алгоритмы не имеют силы, так что автора можно смело игнорировать :)

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