Алгоритм цифровой сортировки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 6: Строка 6:
 
Перед сортировкой необходимо определить 2 величины:
 
Перед сортировкой необходимо определить 2 величины:
  
<tex>1. width</tex> - максимальное количество разрядов в сортируемых величинах.
+
# <tex>width</tex> {{---}} максимальное количество разрядов в сортируемых величинах.
 
+
# <tex>range</tex> {{---}} количество возможных значений одного разряда ключа (сортируемого элемента), то есть мощность используемого алфавита.
<tex>2. range</tex> - количество возможных значений одного разряда ключа(сортируемого элемента)т.е. мощность используемого алфавита.
 
  
 
Сам алгоритм работает следующим образом. Создаются <tex>range</tex> вспомогательных списков - корзин, т.е. на каждое возможное значение разряда элемента по корзине.
 
Сам алгоритм работает следующим образом. Создаются <tex>range</tex> вспомогательных списков - корзин, т.е. на каждое возможное значение разряда элемента по корзине.
Строка 14: Строка 13:
 
'''Первый проход:'''
 
'''Первый проход:'''
  
''Первый этап'' - распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
+
''Первый этап'' {{---}} распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
  
 
Например, пусть имеем исходную последовательность из <tex>{11, 24, 9, 59, 21, 98, 76, 8}</tex>, для которой определяем <tex>width</tex> = 2, <tex>range</tex> = 10, поэтому будет 10 корзин: <tex>list0, list1..., list9</tex>. Тогда на первом проходе корзины №0, 2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:
 
Например, пусть имеем исходную последовательность из <tex>{11, 24, 9, 59, 21, 98, 76, 8}</tex>, для которой определяем <tex>width</tex> = 2, <tex>range</tex> = 10, поэтому будет 10 корзин: <tex>list0, list1..., list9</tex>. Тогда на первом проходе корзины №0, 2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:
Строка 37: Строка 36:
 
'''Второй проход:'''
 
'''Второй проход:'''
  
''Первый этап'' - корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:
+
''Первый этап'' {{---}} корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:
  
 
<tex>list0: 8, 9</tex>
 
<tex>list0: 8, 9</tex>
Строка 51: Строка 50:
 
<tex>list9: 98</tex>
 
<tex>list9: 98</tex>
  
''Второй этап'' - собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 9(list0), 11(list1), 21(list2), 59(list5), 76(list7), 98(list 9)</tex>
+
''Второй этап'' {{---}} собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 9(list0), 11(list1), 21(list2), 59(list5), 76(list7), 98(list 9)</tex>
  
  
 
== Время работы ==
 
== Время работы ==
Алгоритм цифровой сортировки работает за линейное время - <tex>O(k(n + |A|))</tex>, где <tex>|A|</tex> - мощность алфавита(<tex>range</tex>), <tex>k</tex> - максимальная длина строки(<tex>width</tex>), <tex>n</tex> - количество сортируемых строк.
+
Алгоритм цифровой сортировки работает за линейное время - <tex>O(k(n + |A|))</tex>, где <tex>|A|</tex> {{---}} мощность алфавита(<tex>range</tex>), <tex>k</tex> {{---}} максимальная длина строки(<tex>width</tex>), <tex>n</tex> {{---}} количество сортируемых строк.
  
 
== Применение ==
 
== Применение ==
Алгоритм цифровой сортировки позволяет строить суффиксный массив за <tex>O(n^2)</tex>, где <tex>n</tex> - длина строки.
+
Алгоритм цифровой сортировки позволяет строить суффиксный массив за <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} длина строки.
  
 
== Источник ==
 
== Источник ==
 
Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 5-8459-0082-4
 
Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 5-8459-0082-4

Версия 18:37, 28 июня 2011

В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта Least Significant Digit (LSD) и Most Significant Digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке наоборот.

Алгоритм LSD

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

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

  1. [math]width[/math] — максимальное количество разрядов в сортируемых величинах.
  2. [math]range[/math] — количество возможных значений одного разряда ключа (сортируемого элемента), то есть мощность используемого алфавита.

Сам алгоритм работает следующим образом. Создаются [math]range[/math] вспомогательных списков - корзин, т.е. на каждое возможное значение разряда элемента по корзине.

Первый проход:

Первый этап — распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.

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

[math]list1: 11, 21[/math]

[math]list4: 24[/math]

[math]list6: 76[/math]

[math]list8: 98, 8[/math]

[math]list9: 9, 59[/math]

Второй этап - сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности:

[math]11, 21 (list1), 24(list4), 76(list6), 98, 8(list8), 9, 59(list9)[/math]

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

Второй проход:

Первый этап — корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:

[math]list0: 8, 9[/math]

[math]list1: 11[/math]

[math]list2: 21, 24[/math]

[math]list5: 59[/math]

[math]list7: 76[/math]

[math]list9: 98[/math]

Второй этап — собираем и получаем отсортированную по возрастанию последовательность: [math]8, 9(list0), 11(list1), 21(list2), 59(list5), 76(list7), 98(list 9)[/math]


Время работы

Алгоритм цифровой сортировки работает за линейное время - [math]O(k(n + |A|))[/math], где [math]|A|[/math] — мощность алфавита([math]range[/math]), [math]k[/math] — максимальная длина строки([math]width[/math]), [math]n[/math] — количество сортируемых строк.

Применение

Алгоритм цифровой сортировки позволяет строить суффиксный массив за [math]O(n^2)[/math], где [math]n[/math] — длина строки.

Источник

Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 5-8459-0082-4