Уточненный рекурсивный алгоритм процедуры быстрой сортировки

⇐ ПредыдущаяСтр 6 из 6

Исходные данные: Массив А; Левая_граница (0); Правая_граница (n-1)

1. Индекс в начале, i = Левая_граница.

2. Индекс в конце, j =Правая_граница.

3. Опорный = A[(Левая_граница + Правая_граница) / 2].

4. Повторять

4.1. Движение слева направо:

Пока A[i] < Опорный

i = i + 1

4.2. Движение справа налево:

Пока A[j] > Опорный

j = j - 1.

4.3. Поменять местами A[i] и A[j].

4.4. i = i + 1.

4.5. j = j - 1.

Пока Левая_граница < Правая_граница.

5. Если Левая_граница < j, то отсортировать А от Левая_граница до j,

6. Если i > Правая_граница, то отсортировать А от i до Правая_граница.

7. Вывести массив А.

Сложность алгоритма зависит от выбора опорного элемента. Наилучшим считается значение так называемой медианы. Это – элемент, который меньше или равен половине элементов массива и больше или равен другой половине. Нахождение такого элемента требует выполнения дополнительных операций.

Число сравнений и пересылок при реализации быстрой сортировки в худшем случае пропорционально n², т.е. его временная сложность равна О(n²), а в среднем и лучшем - О(n log n). Вообще рассмотренный метод является одним из наиболее эффективных, о чем говорит его название. Причем, наилучшие характеристики он обеспечивает для массивов, имеющих случайные значения.

1.4. Алгоритмы внешней сортировки

Эти методы предназначены для сортировки файлов, находящихся на внешних устройствах (например, на жестком диске). Для большинства файлов характерно, что в каждый момент времени доступен только один элемент. Часть элементов (в виде блоков, серий и т.д.) может храниться в памяти, но ее размеры должны быть небольшими. Это накладывает дополнительные ограничения на методы сортировки. Они, как правило, используют упорядочение внутри отдельных блоков, а также сортировку между ними. Эффективность методов определяется объемом требуемой памяти. Несмотря на такие ограничения, они могут использоваться и для массивов данных, а также таких структур, как связанные списки.

В работе всех алгоритмов, выделяют две основные процедуры (фазы):

a) Разбиение на серии (блоки);

b) Слияние серий.

В разных методах за один просмотр (проход) массива эти фазы выполняются один или несколько раз.

Наиболее распространенными являются следующие алгоритмы:

1) Простая сортировка слиянием;

2) Алгоритм естественных слияний;

3) Метод Боуза- Нельсона.

1.4.1. Простая сортировка слиянием

Этот метод является одним из самых простых и быстрых. Особенностью его является то, что он работает с элементами файла (массива) последовательно, благодаря чему может использоваться для данных на жёстком диске.

Алгоритм использует методику «разделяй и властвуй», которая может быть представлена в виде трех стадий:

1) разделение — данные разбиваются на две, три или более составляющих (последовательностей, массивов), обработка которых осуществляется простыми методами;

2) рекурсия — применяется для обработки полученных составляющих;

3) слияние — результаты действий над составляющими «сливаются» в единое целое.

Массив А разбивается на две половины: B и С. Эти половины сливаются в упорядоченные пары, объединяя первые элементы из B и С в первую пару, вторые – во вторую и т.д. Полученному массиву присваивается имя А, после чего операция повторяется. При этом пары сливаются в упорядоченные четверки. Предыдущие шаги повторяются: четверки сливаются в восьмерки и т.д., пока не будет упорядочен весь массив, т.к. длины частей каждый раз удваиваются. Если размер массива нечетный, или на некотором шаге получатся неполные части, то выполняют отдельно слияние начал, концов и центральной частей.

Очевидно, что основой алгоритма является подзадача слияния двух отсортированных массивов в один, тоже отсортированный. Пусть исходные массивы А и В имеют размерность n_a и n_b. Результат слияния – массив С размерностью n_a + n_b. Он формируется так. Из первых элементов массивов А и В в С записывается сначала меньший, а потом – больший, как показано на рисунке. Считая, что индексы элементов начинаются с 0 (как это принято в системах С++ и java), алгоритм можно описать так.

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

Алгоритм слияния двух отсортированных массивов

1. Номер А (i_a) =0.

2. Номер B (i_b) =0.

3. Пока (i_a < n_a) и (i_b < n_b)

3.1. Если А [i_a] ≤ B [i_b], то

a) C[i_a + i_b] = А [i_a];

b) i_a = i_a + 1.

Иначе

a) C[i_a + i_b] = B [i_b];

b) i_b = i_b + 1.

4. Если i_a < n_a, то

Переписать оставшийся массив А в С.

5. Если i_b < n_b, то

Переписать оставшийся массив А в С.

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

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

1. Разбить элементы массива на пары и осуществить слияние элементов каждой пары, получив отсортированные цепочки длины 2 (кроме может быть, одного элемента, для которого не нашлось пары);

2. Разбить отсортированные цепочки на пары, и осуществить слияние цепочек каждой пары;

3. Если число отсортированных цепочек больше единицы, перейти к шагу 2.

Рассмотрим работу алгоритма на примере массива из 8 чисел, использованного в предыдущих примерах.

Исходный массив 44 55 12 42 94 18 06 67

Шаг 1 – разбиение на 2 подмассива 44 55 12 42 и

94 18 06 67

Шаг 2 – слияние в пары 44 94’ 18 55’ 06 12’ 42 67

Шаг 3 – разбиение на 4 подмассива 44 94’ 18 55’

06 12’ 42 67’

Шаг 4 – слияние пар 06 12 44 94’ 18 42 55 67’

Шаг 5 – разбиение на 8 подмассивов 06 12 44 94

18 42 55 67

Шаг 6 – слияние 06 12 18 42 44 55 67 94

Этот алгоритм можно реализовать рекурсивным способом или с помощью обычного цикла. Рекурсивный алгоритм будет таким.

⇐ Предыдущая 1 2 3 4 56