CodeLAB
на главную карта сайта обратная связь
каталог | задачи | паттерны | исходники | стат | форумы | ссылки
 гость
искать в
Главная >> Каталог задач >> Сортировка >> поразрядная >> Поразрядная сортировка, общий принцип

<< назад
распечатать обсудить >>


Поразрядная сортировка, общий принцип
реализации: C++, количество: 1

Aвтор: this
Дата: 10.05.2002
Просмотров: 51530
Рейтинг: 3/7,4.87(3369)
+
реализации(исходники) +добавить

Алгоритм поразрядной сортировки использует совершенно инной подход сортировки элементов, позволяя в некоторых случаях достигать большей производительности и экономичности, чем другие алгоритмы. Особенность в том, что элементы непосредственно между собой, с друг другом т.е. - не сравниваются.

В двух словах: поразрядная сортировка подразумевает следующее: сначала элементы сортируются по своему младшему(последнему) разряду, затем следующему(предпоследнему) и т.д. до старшего разряда, первого.

На каждой своей итерации алгоритм включает 2 этапа: распределение и сборка. Скорость работы алгоритмы определяется тем что количество проходов по всем элементам исходного списка(массива и проч.) равна максимальному количеству разрядов в элементе, т.е. разрядов сортируемого ключа. Если мы сортируем числа, то количество разрядов - будет равно количеству десятичных разрядов этого числа, например: 27 - количество разрядов 2, 487 - количество разрядов 3, число 9 - 1 разряд и т.д. В случае же сортировки текстовых строк - количество разрядов будет очевидно определяться количеством букв в строке.

Теперь рассмотрим подробно, что же представляет собой этот алгоритм.

Перед сортировкой необходимо определить 2 величины:

  1. width - максимальное количество разрядов в сортируемых величинах, по-другому - количество разрядов в самом длинном ключе(как мы помним "ключ" = сортируемый элемент).
  2. range - количество возможных значений одного разряда ключа(сортируемого элемента). Т.е. для десятичных чисел очевидно имеем - 10, для 16-тиричных - 16, для строки это будет соответственно количество букв в алфавите: т.о. для строки из русских символов - 33, из английских - 36.

Сам алгоритм работает следующим образом. Создаются range вспомогательных списков - "карманов", т.е. на каждое возможное значение разряда элемента - по карману, т.е. по списку. Далее - первый этап распределение по карманам и на первом проходе элементы исходной последовательности помещаются в эти карманы (списки) по их младшему разряду, т.е. по самому правому числу. Какой этот самый младший разряд у элемента, в такой карман этот элемент и помещается.

Например, пусть имеем исходную последовательность из {11, 24, 9, 59, 21, 98, 76, 8}, для которой определяем width = 2, range = 10, поэтому будет 10 "карманов": список0, список1..., список9. Тогда на первом проходе карманы №2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:
список0: 9, 8
список1: 11, 21
список4: 24
список6: 76
список8: 98
список9: 59

Далее второй этап - сборка: просто последовательно соединяем один за другим все карманы и располагаем элементы уже в этой последовательности:
9, 8 (<< это был список0), 11, 21 (список1), 24(список4), 76(список 6), 98(список 8), 59(список9)

Это был один проход алгоритма, соответствующий крайнему правому разряду ключа.
На следующем проходе, элементы из уже обновленной последовательности распределяются по карманам в соответствии с их вторым(т.е. предпоследним) разрядом и т.д по самого старшего, максимального, width-го разряда ключа.

Составим алгоритм первой, самой простой реализации поразрядной сортировки: в качестве карманов используем массивы, исходная последовательность - тоже массив.

 псевдокод: реализация на массивах  ссылка
  1. // инициализация дополнительных списков - "карманов"
  2. pockets = array[range]
  3. for i = 0 to range - 1
  4. pockets[i] = newArray
  5.  
  6. // Основной цикл
  7. for step = 0 to width - 1
  8. // распределение
  9. for i = 0 to (sortedArr.length - 1)
  10. // Получаем значение step-го разряда текущего элемента(ключа)
  11. // ("/" - целочисленное деление)
  12. currDigit = (sortedArr[i] % range^(step + 1)) / range^step
  13. pockets[currDigit].add(sortedArr[i]);
  14.  
  15. // сборка
  16. k = 0 // индекс элементов новой последовательности
  17. for i = 0 to range - 1
  18. for ii = 0 to (pockets[i].length - 1)
  19. sortedArr[k++] = pockets[i][ii]
  20. // Очищение карманов
  21. if step < width - 1
  22. for i = 0 to range - 1
  23. pockets[i] = newArray
  24.  
  25.  

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

Данный алгоритм примерно выглядит следующим образом:

 псевдокод: поразрядная сортировка на односвязном списке  ссылка
  1. // Возвращает ссылку на отсортированный односвязный список
  2. // Передается: та же ссылка list, но на неотсортированный список и width
  3. function radixList(list, width, range)
  4.  
  5. // Дополнительные переменные типа списка(listtype)
  6. // out - результирующий список, который пока идиентичен
  7. // исходному
  8. out = list;
  9.  
  10. // Массивы ссылок на головы и хвосты списков карманов
  11. head = newArrayOfList[range]
  12. tail = newArrayOfList[range]
  13.  
  14. // Вспомогательная переменная
  15. rangepow = 1;
  16.  
  17. for step = 0 to (width - 1)
  18. // Обнуляем все карманы
  19. for i = 0 to range - 1
  20. head[i] = NULL
  21. tail[i] = NULL
  22.  
  23. // РАСПРЕДЕЛЕНИЕ >>
  24. // Проходимся по всему исходному списку
  25. // пока не будет достигнут конец
  26. //(ссылка на текущий элемент - в никуда)
  27. while list != NULL
  28. // Получаем значение step-го разряда текущего элемента(ключа)
  29. // ("/" - целочисленное деление)
  30. currDigit = (list->val / rangepow) % range;
  31.  
  32. // получаем ссылку на хвост текущего кармана
  33. temp = tail[currDigit];
  34.  
  35. // Если карман пуст, то текущий элемент
  36. // будет его головой, иначе добавляем текущий элемент
  37. // в конец кармана
  38. if head[currDigit]=NULL head[currDigit] = list;
  39. else temp->next = list;
  40.  
  41. // Обновляем хвост текущего кармана
  42. // чтобы теперь он указывал на новый добавленный
  43. // элемент
  44. temp = tail[currDigit] = list;
  45. temp->next = NULL;
  46.  
  47. // Переходим к следующему элементу списка
  48. list = list->next;
  49. end while
  50.  
  51.  
  52. // Находим в переменную i первый непустой карман,
  53. // чтобы с него начать сборку.
  54. for i = 0 to (range - 1)
  55. if ( head[i] != NULL ) break;
  56.  
  57. // СБОРКА >>
  58. list = head[i];
  59. temp = tail[i];
  60. for currDigit = i+1 to range
  61. if head[currDigit] != NULL
  62. temp->next = head[currDigit];
  63. temp = tail[currDigit];
  64.  
  65. // !!! важный момент: чтобы на след. итерации в currDigit
  66. // при "распределении" получить следующий разряд - возводим
  67. // в степерь вспомогательную переменную:
  68. rangepow *= range;
  69. end for
  70.  
  71. // Возвращаем ссылку на первый элемент отсортированного списка
  72. return out;
  73.  

Скорость, производительность данных алгоритмов пропорциональна ~ O(width*(n + range)), где n - количество сортируемых элементов. Объем потребляемой памяти в случае с массивами пропорционален ~ (range + n), в случае оптимизированной версии для списков ~(n).

НО! На этом оптимизиция поразрядной сортировки не заканчивается. Дело все в том, что в отличие от списков, массивы по своему определению обладают одним очень важным качеством... у них имеется индекс!!! Который тоже может хранить информацию, позволяющую сократить время выполнение алгоритма почти в 2 раза!

О том какую именно информацию, и что потом с ней делать - читайте в задаче поразрядная сортировка подсчетом.



Реализации: C++(1)   +добавить реализацию

1) Поразрядная сортировка, оптимизированная версия на списках, code #12[автор:-]


<< назад наверх
распечатать обсудить >>

 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2017 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.013099 секунд
Количество запросов к БД: 14, gzip: 13.8kb/56.6kb(76%)