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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 6 промежуточных версий 4 участников)
Строка 1: Строка 1:
В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот.
+
В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта Least Significant Digit (LSD) и Most Significant Digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке наоборот.
  
 
== Алгоритм LSD==
 
== Алгоритм LSD==
Теперь рассмотрим подробно, что же представляет собой этот алгоритм.
 
 
 
Перед сортировкой необходимо определить 2 величины:
 
Перед сортировкой необходимо определить 2 величины:
  
<tex>1. width</tex> - максимальное количество разрядов в сортируемых величинах.
+
# <tex>width</tex> {{---}} максимальное количество разрядов в сортируемых величинах.
 +
# <tex>range</tex> {{---}} количество возможных значений одного разряда ключа (сортируемого элемента), то есть мощность используемого алфавита.
  
<tex>2. range</tex> - количество возможных значений одного разряда ключа(сортируемого элемента)т.е. мощность используемого алфавита.
+
Создаются <tex>range</tex> вспомогательных списков-корзин, т.е. на каждое возможное значение разряда элемента по корзине.
 
 
Сам алгоритм работает следующим образом. Создаются <tex>range</tex> вспомогательных списков - корзин, т.е. на каждое возможное значение разряда элемента по корзине.
 
  
 
'''Первый проход:'''
 
'''Первый проход:'''
  
''Первый этап'' - распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
+
''Первый этап'' {{---}} распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
  
 
Например, пусть имеем исходную последовательность из <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 окажутся пусты, а остальные распределят элементы след. образом:
Строка 28: Строка 25:
 
<tex>list9: 9, 59</tex>
 
<tex>list9: 9, 59</tex>
  
''Второй этап'' - сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности:
+
''Второй этап'' {{---}} сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности:
  
 
<tex>11, 21 (list1), 24(list4), 76(list6), 98, 8(list8), 9, 59(list9)</tex>
 
<tex>11, 21 (list1), 24(list4), 76(list6), 98, 8(list8), 9, 59(list9)</tex>
Строка 37: Строка 34:
 
'''Второй проход:'''
 
'''Второй проход:'''
  
''Первый этап'' - корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:
+
''Первый этап'' {{---}} корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:
  
 
<tex>list0: 8, 9</tex>
 
<tex>list0: 8, 9</tex>
Строка 51: Строка 48:
 
<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, 24(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

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

В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта 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, 24(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