Поразрядная сортировка

Поразрядная сортировка

Поразрядная сортировка (Цифровая сортировка) — алгоритм сортировки за линейное время.

Алгоритм

Алгоритм сортировки, числа сортируются по разрядам. Существует два варианта least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот.

При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

При MSD сортировке получается алфавитный порядок, который подходит для сортировки строк. Например "b, c, d, e, f, g, h, i, j, ba" отсортируется как "b, ba, c, d, e, f, g, h, i, j".

Если MSD применить к числам разной длины, то получим последовательность 1, 10, 2, 3, 4, 5, 6, 7, 8, 9.

При MSD сортировке последовательность сортируется по старшему значимому двоичному разряду так, чтобы все ключи начинающиеся с 0 оказались перед всеми ключами начинающимися с 1. Для этого необходимо найти крайний слева ключ Ki, начиющийся с 1, и крайний справа ключ Kj, начиющийся с 0. После чего Ki и Kj меняются местами, и процесс повторяется, пока не получится i > j.

Пусть F0 — множество элементов начинающихся с 0, F1 — множество всех остальных элементов. Будем к F0 применять поразрядную сортировку (начав теперь со второго бита слева, а не со старшего) до тех пор, пока множество F0 полностью не рассортируется. Затем проделаем тоже самое с F1.

Реализация поразрядной сортировки на С++

01	/*Поразрядная сортировка

02	Radix sort, MSD. Для char-строк. Ноль - конец строки. На основе рекурсии. Глубина рекурсии = длина строки + 1. В каждой рекурсии требуется память для размещения двух массивов указателей: StringItem* front[256], т.е. 2Кб;*/

03	//элемент списка

04	struct StringItem

05

{

06	const char* str; //указатель на строку

07	StringItem* next;

08

};

09	//pList - начало списка указателей на строки

10	//iDigit - разряд, по которому сортирует

11	//возвращает указатель на первый элемент отсортированной последовательности

12	StringItem*  radix_sort_msd_for_string(StringItem* pList, unsigned int iDigit )

13

{

14	// количество вариантов значения одного разряда (char)

15	const int iRange = 256;

16

17	//массив bucket-ов (под-списков)

18	StringItem* front[iRange];

19	memset(front, 0, sizeof(front) );

20

21	StringItem** ppNextItem[iRange];

22	for (int i = 0; i next;

23

24	temp->next=NULL; //отключаем от списка

25

26	unsigned char c = (unsigned char)temp->str[iDigit];

27	*ppNextItem[c]=temp;

28	ppNextItem[c]=&temp->next;

29

}

30	//строим выходной список

31	StringItem* pResult = NULL;

32	StringItem** ppNext = &pResult;

33	//нулевой bucket возвращаем весь - он уже отсортирован

34	*ppNext = front[0];

35	while (*ppNext)

36	ppNext=&((*ppNext)->next);

37	for (int i = 1; i next == NULL)// с одним элементом - сразу добавляем

38	*ppNext = front[i];

39	else    // остальные - на сортировку по следующему разряду

40	*ppNext = radix_sort_msd_for_string(front[i], iDigit + 1);

41	while (*ppNext)

42	ppNext=&((*ppNext)->next);

43

}

44

45	return pResult;

46

}

47

48	/******************/

Вывод по поразрядной сортировке

Вместо сравнения N-й битовой позиции в слове сравнивается N-й байт строки.

Нулевой проход использует только нулевые символы в каждой строке и является корзинной сортировкой по нулевому символу. Эффективная реализация возможна при использовании массива ссылок на строки вместо самих строк, дополнительного массива «границ корзин», инициализируемого частотами встреч символов при первом проходе, они же число элементов в каждой «корзине». При следующем проходе заполняется массив ссылок.

N-й (для N > 0) проход выполняется последовательно над каждой корзиной, полученной на (N - 1)-м проходе, с делением её на «подкорзины». В этом проходе сравниваются N-ные символы каждой строки.

Операция завершается при N, равном максимальной длине строки, или же в ситуации, когда все «подкорзины» получили длину 1.