Цифровая сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 49 промежуточных версий 11 участников)
Строка 1: Строка 1:
'''Цифровая сортировка''' — алгоритм сортировки за линейное время.
+
 
==Алгоритм==
+
'''Цифровая сортировка''' (англ. ''radix sort'') {{---}} один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.
При цифровой сортировке данные разбиваются на "разряды", после этого данные сортируются какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему.
+
== Алгоритм ==
Для чисел наиболее часто в качестве устойчивой сортировки применяют [[сортировка подсчетом|сортировку подсчетом]].  
+
[[Файл:Цифровая_сортировка.png|thumb|right|450px|Пример цифровой сортировки трехзначных чисел, начиная с младших разрядов]]
 +
[[Файл:Msd-sort.png|thumb|right|450px|Пример цифровой сортировки трехзначных чисел, начиная со старших разрядов]]
 +
Имеем множество последовательностей одинаковой длины, состоящих из элементов, на которых задано [[Отношение порядка|отношение линейного порядка]]. Требуется отсортировать эти последовательности в лексикографическом порядке.
 +
 
 +
По аналогии с разрядами чисел будем называть элементы, из которых состоят сортируемые объекты, разрядами. Сам алгоритм состоит в последовательной сортировке объектов какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему, после чего последовательности будут расположены в требуемом порядке.
 +
 
 +
Примерами объектов, которые удобно разбивать на разряды и сортировать по ним, являются числа и строки.
 +
 
 +
*Для чисел уже существует понятие разряда, поэтому будем представлять числа как последовательности разрядов. Конечно, в разных системах счисления разряды одного и того же числа отличаются, поэтому перед сортировкой представим числа в удобной для нас системе счисления.
 +
 
 +
*Строки представляют из себя последовательности символов, поэтому в качестве разрядов в данном случае выступают отдельные символы, сравнение которых обычно происходит по соответствующим им кодам из [[Представление символов, таблицы кодировок#Таблицы кодировок|таблицы кодировок]]. Для такого разбиения самый младший разряд {{---}} последний символ строки.
 +
 
 +
Для вышеперечисленных объектов наиболее часто в качестве устойчивой сортировки применяют [[сортировка подсчетом|сортировку подсчетом]].
 +
 
 +
Такой подход к алгоритму называют '''LSD-сортировкой''' (Least Significant Digit radix sort). Существует модификация алгоритма цифровой сортировки, анализирующая значения разрядов, начиная слева, с наиболее значащих разрядов. Данный алгоритм известен, как '''MSD-сортировка''' (Most Significant Digit radix sort).
 +
=== Корректность алгоритма LSD-сортировки ===
 +
Докажем, что данный алгоритм работает верно, используя метод математической индукции по номеру разряда. Пусть <tex> n </tex> {{---}} количество разрядов в сортируемых объектах.
 +
 
 +
<b> База</b>: <tex> n = 1 </tex>. Очевидно, что алгоритм работает верно, потому что в таком случае мы просто сортируем младшие разряды какой-то заранее выбранной устойчивой сортировкой.
 +
 
 +
<b> Переход</b>: Пусть для <tex> n = k </tex> алгоритм правильно отсортировал последовательности по <tex> k </tex> младшим разрядам. Покажем, что в таком случае, при сортировке по <tex> (k + 1) </tex>-му разряду, последовательности также будут отсортированы в правильном порядке.
 +
 
 +
Вспомогательная сортировка разобьет все объекты на группы, в которых <tex> (k + 1) </tex>-й разряд объектов одинаковый. Рассмотрим такие группы. Для сортировки по отдельным разрядам мы используем устойчивую сортировку, следовательно порядок объектов с одинаковым <tex> (k + 1) </tex>-м разрядом не изменился. Но по предположению индукции по предыдущим <tex> k </tex> разрядам последовательности были отсортированы правильно, и поэтому в каждой такой группе они будут отсортированы верно. Также верно, что сами группы находятся в правильном относительно друг друга порядке, а, следовательно, и все объекты отсортированы правильно по <tex> (k + 1) </tex>-м младшим разрядам.
 +
 
 +
== Псевдокод ==
 +
=== LSD-сортировка ===
 +
В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве устойчивой сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив <tex> A </tex> размера <tex> n </tex> <tex> m </tex>-разрядных чисел . Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива <tex> A </tex> размещаются в нужном порядке во вспомогательном массиве <tex> B </tex>. Для подсчета количества объектов, <tex> i </tex>-й разряд которых одинаковый, а затем и для определения положения объектов в массиве <tex> B </tex> используется вспомогательный массив <tex> C </tex>. Функция <tex> \mathrm{digit(x, i)} </tex> возвращает <tex> i </tex>-й разряд числа <tex> x </tex>. Также считаем, что значения разрядов меньше <tex> k </tex>.
 +
  '''function''' radixSort(int[] A):
 +
      '''for''' i = 1 '''to''' m             
 +
          '''for''' j = 0 '''to''' k - 1                             
 +
              C[j] = 0                                 
 +
          '''for''' j = 0 '''to''' n - 1
 +
              d = digit(A[j], i)
 +
              C[d]++
 +
          count = 0
 +
          '''for''' j = 0 '''to''' k - 1
 +
              tmp = C[j]
 +
              C[j] = count
 +
              count += tmp
 +
          '''for''' j = 0 '''to''' n - 1
 +
              d = digit(A[j], i)                           
 +
              B[C[d]] = A[j]           
 +
              C[d]++
 +
          A = B
 +
 
 +
=== MSD-сортировка ===
 +
Будем считать, что у всех элементов одинаковое число разрядов. Если это не так, то положим на более старших разрядах элементы с самым маленьким значением — для чисел это <tex>0</tex>. Сначала исходный массив делится на <tex>k</tex> частей, где <tex>k</tex> — основание, выбранное для представления сортируемых объектов. Эти части принято называть "корзинами" или "карманами". В первую корзину попадают элементы, у которых старший разряд с номером <tex>d = 0</tex> имеет значение <tex>0</tex>. Во вторую корзину попадают элементы, у которых старший разряд с номером <tex>d = 0</tex> имеет значение <tex>1</tex> и так далее. Затем элементы, попавшие в разные корзины, подвергаются рекурсивному разделению по следующему разряду с номером <tex>d = 1</tex>. Рекурсивный процесс разделения продолжается, пока не будут перебраны все разряды сортируемых объектов и пока размер корзины больше единицы. То есть останавливаемся когда <tex>d > m</tex> или <tex>l \geqslant r</tex>, где m — максимальное число разрядов в сортируемых объектах, <tex>l</tex>, <tex>r</tex> — левая и правая границы отрезка массива <tex>A</tex>.
 +
 
 +
В основу распределения элементов по корзинам положен метод распределяющего подсчета элементов с одинаковыми значениями в сортируемом разряде. Для этого выполняется просмотр массива и подсчет количества элементов с различными значениями в сортируемом разряде. Эти счетчики фиксируются во вспомогательном массиве счетчиков <tex>cnt</tex>. Затем счетчики используются для вычисления размеров корзин и определения границ разделения массива. В соответствии с этими границами сортируемые объекты переносятся во вспомогательный массив <tex>c</tex>, в котором размещены корзины.
 +
После того как корзины сформированы, содержимое вспомогательного массива <tex>c</tex> переносится обратно в исходный массив <tex>A</tex> и выполняется рекурсивное разделение новых частей по следующему разряду в пределах границ корзин, полученных на предыдущем шаге.
 +
 
 +
Изначально запускаем функцию так <math>\mathrm{radixSort(A, 0, A.length - 1, 1)}</math>
 +
 
 +
  '''function''' radixSort(int[] A, int l, int r, int d):
 +
      '''if''' d > m '''or''' l >= r
 +
          '''return'''
 +
      '''for''' j = 0 '''to''' k + 1
 +
          cnt[j] = 0
 +
      '''for''' i = l '''to''' r                             
 +
          j = digit(A[i], d)
 +
          cnt[j + 1]++
 +
      '''for''' j = 2 '''to''' k
 +
          cnt[j] += cnt[j - 1]
 +
      '''for''' i = l '''to''' r
 +
          j = digit(A[i], d)
 +
          c[l + cnt[j]] = A[i]
 +
          cnt[j]--
 +
      '''for''' i = l '''to''' r
 +
          A[i] = c[i]
 +
      radixSort(A, l, l + cnt[0] - 1, d + 1)
 +
      '''for''' i = 1 '''to''' k
 +
          radixSort(A, l + cnt[i - 1], l + cnt[i] - 1, d + 1)
 +
 
 
==Сложность==
 
==Сложность==
Пусть <tex>m</tex> - количество разрядов, n - количество входных данных, T(n) - сложность устойчивой сортировки, тогда сложность цифровой сортировки - <tex>О(m*T(n))</tex>.
+
===Сложность LSD-сортировки===
При использовании сортировки подсчетом получаем линейную зависимость.
+
Пусть <tex> m </tex> {{---}} количество разрядов, <tex> n </tex> {{---}} количество объектов, которые нужно отсортировать, <tex> T(n) </tex> {{---}} время работы устойчивой сортировки. Цифровая сортировка выполняет <tex> k </tex> итераций, на каждой из которой выполняется устойчивая сортировка и не более <tex> O(1) </tex> других операций. Следовательно время работы цифровой сортировки {{---}} <tex> O(k T(n)) </tex>.
==Псевдокод==
+
 
 +
Рассмотрим отдельно случай сортировки чисел. Пусть в качестве аргумента сортировке передается массив, в котором содержатся <tex> n </tex> <tex> m </tex>-значных чисел, и каждая цифра может принимать значения от <tex> 0 </tex> до <tex> k - 1 </tex>. Тогда цифровая сортировка позволяет отсортировать данный массив за время <tex> O(m (n + k)) </tex>, если устойчивая сортировка имеет время работы <tex> O(n + k) </tex>. Если <tex> k </tex> небольшое, то оптимально выбирать в качестве устойчивой сортировки сортировку подсчетом.
 +
 
 +
Если количество разрядов {{---}} константа, а <tex> k = O(n) </tex>, то сложность цифровой сортировки составляет <tex> O(n) </tex>, то есть она линейно зависит от количества сортируемых чисел.
 +
===Сложность MSD-сортировки===
 +
Пусть значения разрядов меньше <tex>b</tex>, а количество разрядов {{---}} <tex>k</tex>. При сортировке массива из одинаковых элементов MSD-сортировкой на каждом шаге все элементы будут находится в неубывающей по размеру корзине, а так как цикл идет по всем элементам массива, то получим, что время работы MSD-сортировки оценивается величиной <tex>O(nk)</tex>, причем это время нельзя улучшить. Хорошим случаем для данной сортировки будет массив, при котором на каждом шаге каждая корзина будет делиться на <tex>b</tex> частей. Как только размер корзины станет равен <tex>1</tex>, сортировка перестанет рекурсивно запускаться в этой корзине. Таким образом, асимптотика будет <math>\Omega(n\log_b{n})</math>. Это хорошо тем, что не зависит от числа разрядов.
 +
 
 +
Существует также модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана, и вызывается более быстрая сортировка, основанная на сравнениях (например, сортировка вставками).
  
  Radix_sort
+
== См. также ==
  for i = 1 to m
+
* [[Сортировка подсчетом]]
    do устойчивая сортировка массива по i-ому разряду
+
* [[Сортировка вставками]]
  
== Литература ==
+
== Источники информации ==
 +
* [[wikipedia:ru:Поразрядная сортировка|Википедия {{---}} Цифровая сортировка]]
 +
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/linear-2005 Визуализатор 1] — Java-аплет.
 +
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/linear-2001 Визуализатор 2] — Java-аплет.
 
* Дональд Кнут Искусство программирования, том 3. Сортировка и поиск
 
* Дональд Кнут Искусство программирования, том 3. Сортировка и поиск
 
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ
 
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ
  
== Ссылки ==
+
[[Категория: Дискретная математика и алгоритмы]]
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/linear-2005 Визуализатор1] — Java-аплет.
+
[[Категория: Сортировки]]
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/linear-2001 Визуализатор2] — Java-аплет.
+
[[Категория: Другие сортировки]]

Текущая версия на 19:05, 4 сентября 2022

Цифровая сортировка (англ. radix sort) — один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.

Алгоритм

Пример цифровой сортировки трехзначных чисел, начиная с младших разрядов
Пример цифровой сортировки трехзначных чисел, начиная со старших разрядов

Имеем множество последовательностей одинаковой длины, состоящих из элементов, на которых задано отношение линейного порядка. Требуется отсортировать эти последовательности в лексикографическом порядке.

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

Примерами объектов, которые удобно разбивать на разряды и сортировать по ним, являются числа и строки.

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

Для вышеперечисленных объектов наиболее часто в качестве устойчивой сортировки применяют сортировку подсчетом.

Такой подход к алгоритму называют LSD-сортировкой (Least Significant Digit radix sort). Существует модификация алгоритма цифровой сортировки, анализирующая значения разрядов, начиная слева, с наиболее значащих разрядов. Данный алгоритм известен, как MSD-сортировка (Most Significant Digit radix sort).

Корректность алгоритма LSD-сортировки

Докажем, что данный алгоритм работает верно, используя метод математической индукции по номеру разряда. Пусть [math] n [/math] — количество разрядов в сортируемых объектах.

База: [math] n = 1 [/math]. Очевидно, что алгоритм работает верно, потому что в таком случае мы просто сортируем младшие разряды какой-то заранее выбранной устойчивой сортировкой.

Переход: Пусть для [math] n = k [/math] алгоритм правильно отсортировал последовательности по [math] k [/math] младшим разрядам. Покажем, что в таком случае, при сортировке по [math] (k + 1) [/math]-му разряду, последовательности также будут отсортированы в правильном порядке.

Вспомогательная сортировка разобьет все объекты на группы, в которых [math] (k + 1) [/math]-й разряд объектов одинаковый. Рассмотрим такие группы. Для сортировки по отдельным разрядам мы используем устойчивую сортировку, следовательно порядок объектов с одинаковым [math] (k + 1) [/math]-м разрядом не изменился. Но по предположению индукции по предыдущим [math] k [/math] разрядам последовательности были отсортированы правильно, и поэтому в каждой такой группе они будут отсортированы верно. Также верно, что сами группы находятся в правильном относительно друг друга порядке, а, следовательно, и все объекты отсортированы правильно по [math] (k + 1) [/math]-м младшим разрядам.

Псевдокод

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

В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве устойчивой сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив [math] A [/math] размера [math] n [/math] [math] m [/math]-разрядных чисел . Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива [math] A [/math] размещаются в нужном порядке во вспомогательном массиве [math] B [/math]. Для подсчета количества объектов, [math] i [/math]-й разряд которых одинаковый, а затем и для определения положения объектов в массиве [math] B [/math] используется вспомогательный массив [math] C [/math]. Функция [math] \mathrm{digit(x, i)} [/math] возвращает [math] i [/math]-й разряд числа [math] x [/math]. Также считаем, что значения разрядов меньше [math] k [/math].

 function radixSort(int[] A):
     for i = 1 to m               
         for j = 0 to k - 1                              
             C[j] = 0                                  
         for j = 0 to n - 1
             d = digit(A[j], i)
             C[d]++
         count = 0
         for j = 0 to k - 1
             tmp = C[j]
             C[j] = count
             count += tmp
         for j = 0 to n - 1
             d = digit(A[j], i)                             
             B[C[d]] = A[j]            
             C[d]++
         A = B

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

Будем считать, что у всех элементов одинаковое число разрядов. Если это не так, то положим на более старших разрядах элементы с самым маленьким значением — для чисел это [math]0[/math]. Сначала исходный массив делится на [math]k[/math] частей, где [math]k[/math] — основание, выбранное для представления сортируемых объектов. Эти части принято называть "корзинами" или "карманами". В первую корзину попадают элементы, у которых старший разряд с номером [math]d = 0[/math] имеет значение [math]0[/math]. Во вторую корзину попадают элементы, у которых старший разряд с номером [math]d = 0[/math] имеет значение [math]1[/math] и так далее. Затем элементы, попавшие в разные корзины, подвергаются рекурсивному разделению по следующему разряду с номером [math]d = 1[/math]. Рекурсивный процесс разделения продолжается, пока не будут перебраны все разряды сортируемых объектов и пока размер корзины больше единицы. То есть останавливаемся когда [math]d \gt m[/math] или [math]l \geqslant r[/math], где m — максимальное число разрядов в сортируемых объектах, [math]l[/math], [math]r[/math] — левая и правая границы отрезка массива [math]A[/math].

В основу распределения элементов по корзинам положен метод распределяющего подсчета элементов с одинаковыми значениями в сортируемом разряде. Для этого выполняется просмотр массива и подсчет количества элементов с различными значениями в сортируемом разряде. Эти счетчики фиксируются во вспомогательном массиве счетчиков [math]cnt[/math]. Затем счетчики используются для вычисления размеров корзин и определения границ разделения массива. В соответствии с этими границами сортируемые объекты переносятся во вспомогательный массив [math]c[/math], в котором размещены корзины. После того как корзины сформированы, содержимое вспомогательного массива [math]c[/math] переносится обратно в исходный массив [math]A[/math] и выполняется рекурсивное разделение новых частей по следующему разряду в пределах границ корзин, полученных на предыдущем шаге.

Изначально запускаем функцию так [math]\mathrm{radixSort(A, 0, A.length - 1, 1)}[/math]

 function radixSort(int[] A, int l, int r, int d):
     if d > m or l >= r 
         return
     for j = 0 to k + 1 
         cnt[j] = 0
     for i = l to r                              
         j = digit(A[i], d)
         cnt[j + 1]++
     for j = 2 to k
         cnt[j] += cnt[j - 1]
     for i = l to r
         j = digit(A[i], d)
         c[l + cnt[j]] = A[i]
         cnt[j]--
     for i = l to r
         A[i] = c[i]
     radixSort(A, l, l + cnt[0] - 1, d + 1)
     for i = 1 to k
         radixSort(A, l + cnt[i - 1], l + cnt[i] - 1, d + 1)

Сложность

Сложность LSD-сортировки

Пусть [math] m [/math] — количество разрядов, [math] n [/math] — количество объектов, которые нужно отсортировать, [math] T(n) [/math] — время работы устойчивой сортировки. Цифровая сортировка выполняет [math] k [/math] итераций, на каждой из которой выполняется устойчивая сортировка и не более [math] O(1) [/math] других операций. Следовательно время работы цифровой сортировки — [math] O(k T(n)) [/math].

Рассмотрим отдельно случай сортировки чисел. Пусть в качестве аргумента сортировке передается массив, в котором содержатся [math] n [/math] [math] m [/math]-значных чисел, и каждая цифра может принимать значения от [math] 0 [/math] до [math] k - 1 [/math]. Тогда цифровая сортировка позволяет отсортировать данный массив за время [math] O(m (n + k)) [/math], если устойчивая сортировка имеет время работы [math] O(n + k) [/math]. Если [math] k [/math] небольшое, то оптимально выбирать в качестве устойчивой сортировки сортировку подсчетом.

Если количество разрядов — константа, а [math] k = O(n) [/math], то сложность цифровой сортировки составляет [math] O(n) [/math], то есть она линейно зависит от количества сортируемых чисел.

Сложность MSD-сортировки

Пусть значения разрядов меньше [math]b[/math], а количество разрядов — [math]k[/math]. При сортировке массива из одинаковых элементов MSD-сортировкой на каждом шаге все элементы будут находится в неубывающей по размеру корзине, а так как цикл идет по всем элементам массива, то получим, что время работы MSD-сортировки оценивается величиной [math]O(nk)[/math], причем это время нельзя улучшить. Хорошим случаем для данной сортировки будет массив, при котором на каждом шаге каждая корзина будет делиться на [math]b[/math] частей. Как только размер корзины станет равен [math]1[/math], сортировка перестанет рекурсивно запускаться в этой корзине. Таким образом, асимптотика будет [math]\Omega(n\log_b{n})[/math]. Это хорошо тем, что не зависит от числа разрядов.

Существует также модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана, и вызывается более быстрая сортировка, основанная на сравнениях (например, сортировка вставками).

См. также

Источники информации