Pull to refresh

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

Reading time 6 min
Views 47K

Данная разновидность поразрядной 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-отчёте (на 10-й странице).

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


Для сортировки потребуется два вспомогательных массива: двухмерный для трекера символов, которым при оценке сложности можно пренебречь. А также массив из 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
Сайт книги «Разгадка Вознесения – соберём паззл вместе»

Голосование

Only registered users can participate in poll. Log in, please.
Считаете ли Вы допустимым патентование компьютерных алгоритмов с последующим требованием роялти?
72.53% Нет. Алгоритмы, как и любые законы Вселенной, принадлежат абсолютно всем. 507
27.47% Да. Алгоритм – это изобретение, автор имеет полное моральное право на вознаграждение. 192
699 users voted. 127 users abstained.
Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
+29
Comments 24
Comments Comments 24

Articles