Сортировка файлов методом прямого слияния

Сравнение методов сортировки массивов

Функция быстрой сортировки

void quicksort(int numbers[], int array_size)

{

q_sort(numbers, 0, array_size - 1);

}

void q_sort(int numbers[], int left, int right)

{

int pivot, l_hold, r_hold;

1 hold = left;

r_hold = right;

pivot = numbers[left];

while (left < right)

{

while ((numbers[right] >= pivot) && (left < right))

right--; if (left!= right)

{

numbers[left] = numbers[right]; left++;

}

while ((numbers[left] <= pivot) && (left < right))

left++; if (left!= right)

{

numbers[right] = numbers[left]; right--; } }

numbers[left] = pivot; pivot = left; left = l_hold; right = r_hold; if (left < pivot)

q_sort(numbers, left, pivot-1); if (right > pivot)

q_sort(numbers, pivot+1, right); }

Анализ алгоритма [3]. Ожидаемое число обменов равно (п - \1п)1в. Если предположить, что в качестве разрешающего элемента всегда выбирается медиана, то каждое разделение разбивает массив на две равные части, и число проходов, необходимых для сортировки, равно log п. Тогда общее число сравнений составит и-log «, а общее число обменов — (w/6)-log п. Вероятность попадания на медиану составляет \1п. Однако, если граница выбирается случайным образом, эффективность алгоритма в среднем хуже оптимального варианта лишь в 2-In 2 раз. Основной недостаток алгоритма — недостаточно высокая производительность при небольших п.

Сравним эффективность методов сортировки массивов. Для всех прямых методов сортировки можно дать точные аналитические формулы [3]. Они представлены в табл. 3.5.

Для усовершенствованных методов сортировки нет простых и точных формул. Существенно, однако, что в случае сортировки Шелла вычислительные затраты составляют с-п ', а для пирамидальной и быстрой сортировок — с и log п, где с — соответствующий коэффициент.

Опытным путем были получены следующие результаты [3]:

1. Пузырьковая сортировка наихудший метод из всех сравниваемых.

2. Быстрая сортировка лучше в 2—3 раза, чем пирамидальная. Она сортирует массив, расположенный в обратном порядке, практически с той же скоростью, что и уже упорядоченный.

Таблица 3.5 Сравнение прямых методов сортировки

Вид сортировки	Показатели	Min	Среднее	Мах
Прямое включение	С = М =	п-\ 2(и - 1)	(п^2 - п -2)1 А (п^2-9п-Щ1А	(п^2 - п)12 - 1 (п^2 -Ъп- 4)/2
Прямой выбор	с = м=	(п^2 - п)12 3(и - 1)	(п^2 - п)12 «■(In n + 0,57)	(п^2 - п)12 п^2 /4+ 3(«-1)
Прямой обмен	с = м=	(п^2 - п)12 0	(п^2 - п)12 0,75-(п^2-п)	(п^2 - п)12 (п^2-п)\,5

Алгоритмы сортировки, рассмотренные ранее, неприменимы, если сортируемые данные расположены в файле с последовательным доступом (на диске), который характеризуется тем, что в каждый момент имеется непосредственный доступ к одному и только одному компоненту [1, 3, 9, 10, 13].

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

Метод заключается в следующем [3]:

1. Последовательность а разбивается на две половины: b ис.

2. Последовательности b ис сливаются при помощи объединения отдельных элементов в упорядоченные пары.

3. Полученной последовательности присваивается имя а, и повторяются шаги 1 и 2; на этот раз упорядоченные пары сливаются в упорядоченные четверки.

4. Предыдущие шаги повторяются: четверки сливаются в восьмерки и так далее, пока не будет упорядочена вся последовательность.

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