Цифровая сортировка — различия между версиями
(→Псевдокод) |
Warrior (обсуждение | вклад) (→Псевдокод) |
||
Строка 24: | Строка 24: | ||
В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве стабильной сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив <tex> A </tex> <tex> m </tex>-разрядных чисел размера <tex> n </tex>. Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива <tex> A </tex> размещаются в нужном порядке во вспомогательном массиве <tex> B </tex>. Для подсчета количества объектов, <tex> i </tex>-ый разряд которых одинаковый, а затем и для определения положения объектов в массиве <tex> B </tex> используется вспомогательный массив <tex> C </tex>. Функция <tex> digit(x, i) </tex> возвращает <tex> i </tex>-ый разряд числа <tex> x </tex>. Также считаем, что значения разрядов меньше <tex> k </tex>. | В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве стабильной сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив <tex> A </tex> <tex> m </tex>-разрядных чисел размера <tex> n </tex>. Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива <tex> A </tex> размещаются в нужном порядке во вспомогательном массиве <tex> B </tex>. Для подсчета количества объектов, <tex> i </tex>-ый разряд которых одинаковый, а затем и для определения положения объектов в массиве <tex> B </tex> используется вспомогательный массив <tex> C </tex>. Функция <tex> digit(x, i) </tex> возвращает <tex> i </tex>-ый разряд числа <tex> x </tex>. Также считаем, что значения разрядов меньше <tex> k </tex>. | ||
radixSort(A) | radixSort(A) | ||
− | '''for''' i = 1 '''to''' m | + | '''for''' i = 1 '''to''' m |
+ | d = digit(A[j], i); | ||
'''for''' j = 0 '''to''' k - 1 | '''for''' j = 0 '''to''' k - 1 | ||
C[j] = 0; | C[j] = 0; | ||
'''for''' j = 0 '''to''' n - 1 | '''for''' j = 0 '''to''' n - 1 | ||
− | C[ | + | C[d] = C[d] + 1; |
'''for''' j = 1 '''to''' k - 1 | '''for''' j = 1 '''to''' k - 1 | ||
C[j] = C[j] + C[j - 1]; | C[j] = C[j] + C[j - 1]; | ||
'''for''' j = n - 1 '''to''' 0 | '''for''' j = n - 1 '''to''' 0 | ||
− | B[C[ | + | B[C[d]] = A[j]; |
− | C[ | + | C[d] = C[d] - 1; |
A = B; | A = B; | ||
Версия 23:56, 10 июня 2012
Цифровая сортировка — один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.
Алгоритм
При цифровой сортировке данные разбиваются на "разряды", после чего они сортируются какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему. Заметим, что лексикографический порядок сортировки разрядов должен совпадать с требуемым от самой цифровой сортировки. Например, если объекты сортируются по невозрастанию, то при сортировки по
-ому разряду объект с меньшим -ым разрядом должен идти раньше, чем объект, у которого данный разряд больше. В этом нетрудно убедиться, если на вход алгоритму подать объекты, состоящие из одного разряда.Примерами объектов, которые удобно разбивать на разряды и сортировать по ним, являются числа и строки.
- Для чисел уже существует понятие разряда, поэтому разбивать будем именно по ним. Конечно, в разных системах счисления разряды одного и того же числа отличаются, поэтому перед тем как разбивать число, представим его в удобной для нас системе счисления.
- Так как строки представляют из себя массивы символов, то в качестве разряда можно брать отдельные символы, сравнение которых обычно происходит по соответствующим им кодам из таблицы кодировок. Для такого разбиения самый младший разряд — последний символ строки.
Для вышеперечисленных объектов наиболее часто в качестве устойчивой сортировки применяют сортировку подсчетом.
Корректность алгоритма
Докажем, что данный алгоритм работает верно, используя метод математической индукции по номеру разряда. Пусть
— количество разрядов в сортируемых объектах.База:
. Очевидно, что алгоритм работает верно, потому что в таком случае мы просто сортируем младшие разряды какой-то заранее выбранной стабильной сортировкой.Переход: Пусть для
алгоритм правильно отсортировал элементы по младшим разрядам. Покажем, что в таком случае, при сортировке по -ому разряду, объекты также будут отсортированы в правильном порядке.Вспомогательная сортировка разобьет все объекты на группы, в которых
-ый разряд объектов одинаковый. Рассмотрим такие группы. Для сортировки по отдельным разрядам мы используем стабильную сортировку, следовательно порядок объектов с одинаковым -ым разрядом не изменился. Но по предположению индукции по предыдущим разрядам объекты были отсортированы правильно, и поэтому в каждой такой группе объекты будут отсортированы верно. Также верно, что сами группы находятся в правильном относительно друг друга порядке, а, следовательно, и все элементы отсортированы правильно по -ым младшим разрядам.Псевдокод
В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве стабильной сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив
-разрядных чисел размера . Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива размещаются в нужном порядке во вспомогательном массиве . Для подсчета количества объектов, -ый разряд которых одинаковый, а затем и для определения положения объектов в массиве используется вспомогательный массив . Функция возвращает -ый разряд числа . Также считаем, что значения разрядов меньше .radixSort(A) for i = 1 to m d = digit(A[j], i); for j = 0 to k - 1 C[j] = 0; for j = 0 to n - 1 C[d] = C[d] + 1; for j = 1 to k - 1 C[j] = C[j] + C[j - 1]; for j = n - 1 to 0 B[C[d]] = A[j]; C[d] = C[d] - 1; A = B;
Сложность
Пусть
— количество разрядов, — количество объектов, которые нужно отсортировать, — время работы устойчивой сортировки. Цифровая сортировка выполняет итераций, на каждой из которой выполняется устойчивая сортировка и не более других операций. Следовательно время работы цифровой сортировки — .Рассмотрим отдельно случай сортировки чисел. Пусть в качестве аргумента сортировке передается массив, в котором содержатся
-значных чисел, и каждая цифра может принимать значения от до . Тогда цифровая сортировка позволяет отсортировать данный массив за время , если устойчивая сортировка имеет время работы . Если небольшое, то оптимально выбирать в качестве устойчивой сортировки сортировку подсчетом.Если количество разрядов — константа, а
, то сложность цифровой сортировки составляет , то есть она линейно зависит от количества сортируемых чисел.Литература
- Дональд Кнут Искусство программирования, том 3. Сортировка и поиск
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ
Ссылки
- Визуализатор 1 — Java-аплет.
- Визуализатор 2 — Java-аплет.