Поразрядная сортировка (RadixSort)

Сортировка

Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда следует алгоритм:

• Берем максимальный элемент в корне и меняем его местами с последним неотсортированным элементом. После этого он находится на правильной позиции, и в дальнейшем алгоритме уже не участвует.
• Берем элемент, находящийся в вершине и для него выполняем алгоритм по построению пирамиды.
• Выполняем шаги 1 и 2, пока не останется неотсортированных элементов.

3.9 Сортировка слиянием

1. Общее быстродействие O= Theta(n*log(n)).

2. Использует дополнительную память, объем которой равен Theta(n).

3. Устойчивая.

4. Естественность зависит от реализации.

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

Выборка и слияние — это вспомогательные операции в том смысле, что выборка разбивает файл на два независимых массива, в то время как слияние объединяет два независимых массива в один.

Сортировка слиянием (mergesort) является дополнением быстрой сортировки в том, что она состоит из двух рекурсивных вызовов с последующей процедурой слияния.

В процессе сортировки происходит деление массива до единственного элемента. Такой массив можно считать опорным. Значит, составление алгоритма сортировки заключается в написании одной единственной функции слияния.

Например, разбиваем исходный неупорядоченный массив на два массива: a[lb]... a[split] и a[split+1]... a[ub].

В результате сортировки мы получим: a[lb]... a[ub].

3 7 8 2 | 4 6 1 5

3 7 | 8 2 | 4 6 | 1 5

3 | 7 | 8 | 2 | 4 | 6 | 1 | 5

3 7 | 2 8 | 4 6 | 1 5

2 3 7 8 | 1 4 5 6

1 2 3 4 5 6 7 8

В сортировке происходит деление до единственного элемента, такой массив можно считать упорядоченным, значит, написанный алгоритм сортировки заключается в написании одной единственно функции слияния.

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

• Общее быстродействие O(n + m)

• Использует дополнительную память

• Устойчивая

• Не естественная

Поразрядная сортировка существенно отличается от описанных ранее.

Во-первых, он совсем не использует сравнений сортируемых элементов.

Во-вторых ключ, по которому идет сортировка разбивается на части (разряды). Например, при сортировке слов, слова можно разделить на буквы, при сортировке чисел, их можно поделить на цифры.

Для сортировки необходимо задать два дополнительных параметра:

k – количество разрядов в самом длинном ключе

m – разрядность данных (количество возможных значений для каждого разряда ключа).

Например, при сортировке русских слов m=33 (количество букв русского алфавита), k – количество букв в самом длинном слове.

При сортировке десятичных чисел m=10 (10 цифр от 0 до 9), k – максимальное количество цифр в числах участвующих в сортировке, для диапазона от 0 до 5000 k=4.

Основная идея заключается в выделении m счетчиков, которые ведут подсчет сколько чисел из исходного массива имеют в соответствующем разряде одинаковое значение.

Сортировка двухпроходная.

На первом этапе подсчитываются количество чисел имеющих, одинаковые значения в разряде.

На втором этапе на основании информации полученной на первом этапе строится новый массив, отсортированный по разряду.

Аналогичные действия производятся над следующим разрядом. Всего потребуется k таких проходов.

Поразрядная сортировка (Десятичные числа) m=10 k=3

Дата добавления: 2014-01-11