Цифровая сортировка

Материал из Викиконспекты
Версия от 21:28, 7 мая 2012; Qwerty787788 (обсуждение | вклад) (добавлены категории)
Перейти к: навигация, поиск
Пример цифровой сортировки

Цифровая сортировка — алгоритм сортировки за линейное время.

Алгоритм

При цифровой сортировке данные разбиваются на "разряды", после этого данные сортируются какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему. Для чисел наиболее часто в качестве устойчивой сортировки применяют сортировку подсчетом.

Сложность

Пусть [math]k[/math] - количество разрядов, n - количество входных данных, [math]T(n)[/math] - сложность устойчивой сортировки, тогда сложность цифровой сортировки - [math]О(k*T(n))[/math]. При использовании сортировки подсчетом получаем линейную зависимость.

Псевдокод

 Radix_sort
 for i = 1 to m
    do устойчивая сортировка массива по i-ому разряду

Литература

  • Дональд Кнут Искусство программирования, том 3. Сортировка и поиск
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ

Ссылки