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

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

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

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

Бичик

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

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

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

• В среднем в 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» и далее по алфавиту.

/*            
 ** 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); 
					} 
				} 
			} 
		} 
	} 

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

В целом можно уверенно говорить о временной сложности O(n).

Компания «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++.

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

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

Ссылки

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

Аллен Бичик

На Фейсбуке
На LinkedIn
Сайт книги «Разгадка Вознесения – соберём паззл вместе»
«Who's who in Bible Prophecy. A list of popular teachers and scholars»

Голосование

Автор: valemak

Источник