ЛЕКЦИЯ 5 ПОРАЗРЯДНАЯ СОРТИРОВКА. СОРТИРОВКА СЛИЯНИЕМ
Цель лекции: изучение методов поразрядной сортировки, методов сортировки массива слияние.,
Основны расматриваемы вопросы: поразрядная сортировка,сортировка слиянием.
Поразрядная сортировка
Рассмотрим данный метод для списочных структур данных 
. Обратите внимание, что в данном методе, в отличие от всех ранее рассмотреннх, не используются сравнения.
Предположим, что элементы линейного списка L есть k-разрядные десятичные числа, разрядность максимального числа известна заранее. Обозначим d(j,n) - j-ю справа цифра числа n, которую можно выразить как
d(j,n) = [ n / 10j-1 ] mod 10
Пусть L0, L1,..., L9 - вспомогательные списки (карманы), вначале пустые. Поразрядная сортировка состоит из двух процессов, называемых распределение и сборка и выполняемых для j=1,2,...,k.
Фаза распределения разносит элементы L по карманам: элементы li списка L последовательно добавляются в списки Lm, где m = d(j, li). Таким образом получаем десять списков, в каждом из которых j-тые разряды чисел одинаковы и равны m.
Фаза сборки состоит в объединении списков L0, L1,..., L9 в общий список
L = L0 => L1 => L2 => ... => L9
Рассмотрим пример работы алгоритма на входном списке
0 => 8 => 12 => 56 => 7 => 26 => 44 => 97 => 2 => 37 => 4 => 3 => 3 => 45 => 10.
Максимальное число содержит две цифры, значит, разрядность данных k=2.
Первый проход, j=1.
Распределение по первой справа цифре:
L0: 0 => 10 // все числа с первой справа цифрой 0
L1: пусто
L2: 12 => 2
L3: 3 => 3
L4: 44 => 4
L5: 45
L6: 56 => 26
L7: 7 => 97 => 37
L8: 8
L9: пусто // все числа с первой справа цифрой 9
|
|
|
Cборка:
соединяем списки Li один за другим
L: 0 => 10 => 12 => 2 => 3 => 3 => 44 => 4 => 45 => 56 => 26 => 7 => 97 => 37 => 8
Второй проход, j=2.
Распределение по второй справа цифре:
L0: 0 => 2 => 3 => 3 => 4 => 7 => 8
L1: 10 => 12
L2: 26
L3: 37
L4: 44 => 45
L5: 56
L6: пусто
L7: пусто
L8: пусто
L9: 97
Cборка:
соединяем списки Li один за другим
L: 0 => 2 => 3 => 3 => 4 => 7 => 8 => 10 => 12 => 26 => 37 => 44 => 45 => 56 => 97
Число используемых карманов - количество возможных значений элемента списка.
Число проходов зависит от разрядности чисел.
Сложность метода О(n)
Сортировка слиянием
Сортировки слиянием применимы как для внутренней сортировки, так и в тех случаях, когда требуется отсортировать последовательный файл, не помещающийся целиком в основной памяти. Использование методов, основанных на механизмах слияния и используемых для внешних сортировок, рассмотрим позднее. На данной лекции рассмотрим основные идеи использования сортировки слиянием для массивов.
Один из популярных алгоритмов внутренней сортировки со слияниями основан на следующих идеях. Сначала поясним, что такое слияние. Пусть имеются два отсортированных в порядке возрастания массива p[1], p[2], ..., p[n] и q[1], q[2], ..., q[n] и имеется пустой массив r[1], r[2], ..., r[2n], который мы хотим заполнить значениями массивов p и q в порядке возрастания. Для слияния выполняются следующие действия: сравниваются p[1] и q[1], и меньшее из значений записывается в r[1]. Предположим, что это значение p[1]. Тогда p[2] сравнивается с q[1] и меньшее из значений заносится в r[2]. Предположим, что это значение q[1]. Тогда на следующем шаге сравниваются значения p[2] и q[2] и т.д., пока мы не достигнем границ одного из массивов. Тогда остаток другого массива просто дописывается в "хвост" массива r.
|
|
|
Для сортировки со слиянием массива a[1], a[2], ..., a[n] заводится парный массив b[1], b[2], ..., b[n]. На первом шаге производится слияние a[1] и a[n] с размещением результата в b[1], b[2], слияние a[2] и a[n-1] с размещением результата в b[3], b[4], ..., слияние a[n/2] и a[n/2+1] с помещением результата в b[n-1], b[n]. На втором шаге производится слияние пар b[1], b[2] и b[n-1], b[n] с помещением результата в a[1], a[2], a[3], a[4], слияние пар b[3], b[4] и b[n-3], b[n-2] с помещением результата в a[5], a[6], a[7], a[8], ..., слияние пар b[n/2-1], b[n/2] и b[n/2+1], b[n/2+2] с помещением результата в a[n-3], a[n-2], a[n-1], a[n]. И т.д. На последнем шаге, например (в зависимости от значения n), производится слияние последовательностей элементов массива длиной n/2 a[1], a[2], ..., a[n/2] и a[n/2+1], a[n/2+2], ..., a[n] с помещением результата в b[1], b[2], ..., b[n].
|
|
|
Для случая массива, используемого в наших примерах, последовательность шагов показана в таблице 2.9.
| Начальное состояние массива | 8 23 5 65 44 33 1 6 |
| Шаг 1 | 6 8 1 23 5 33 44 65 |
| Шаг 2 | 6 8 44 65 1 5 23 33 |
| Шаг 3 | 1 5 6 8 23 33 44 65 |
При применении сортировки со слиянием число сравнений ключей и число пересылок оценивается как O(nlog n). Но следует учитывать, что для выполнения алгоритма для сортировки массива размера n требуется 2n элементов памяти.
Более подробно группу методов сортировки слиянием рассмотрим при изучении методов внешней сортировки.
Дата добавления: 2018-05-02; просмотров: 629; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!