CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Рисование прямоугольника. (31302 hits)
#Хранение иерархических деревьев. (53328 hits)
#Код. (179772 hits)
#"The Java Programming Language" Ken Arnold, James Gosling, David Holmes листинги, код, примеры из книги, исходники. (61068 hits)
#Валидация, динамическая проверка заполнения html форм. (209204 hits)
#Поиск дубликатов внутри файла. (31348 hits)
#Вычисление среднего, среднего отклонения, среднеквадратического отклонения и дисперсии заданной выборки. (46439 hits)
#Доступ ко всем полям и методам. (58030 hits)
#Вычисление минимального / максимального значения. (74393 hits)
#Шифрование произвольных данных. (328768 hits)
#Овал, вписанный в прямоугольник. (37862 hits)
#Переворот символов строки (или элементов одномерного массива). (112214 hits)
#Полезные утилиты, небольшие api и библиотеки и проч.. (69733 hits)
#Сортировка Шелла, обший принцип. (145044 hits)
#Перестановка фрагментов строки(или одномерного массива). (60682 hits)
#Программное создание ссылок. (99855 hits)
#Сравнение алгоритмов сортировки массива. (182123 hits)
#Работа с камерой. (35831 hits)
#Сортировка выбором, общий подход. (72847 hits)
#Древовидные структуры. (57430 hits)


Главная >> Каталог задач >> Сортировка >> Поразрядная Сортировка >>

Поразрядная сортировка, общий принцип

Aвтор:
Дата:
Просмотров: 130615
реализации(C++: 1шт...) +добавить

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

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

На каждой своей итерации алгоритм включает 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) Поразрядная сортировка, оптимизированная версия на списках на C++, code #12[автор:-]