- •3. Анализ алгоритмов сортировки и поиска
- •1. Алгоритмы поиска
- •Int b_find(int* a, int n, int key) // key – искомое значение
- •2. Задачи сортировки. Сортировка методом парных перестановок
- •Void sort_pair(int* a, int n)
- •3. Метод пузырька
- •Void sort_bubble(int* a, int n)
- •4. Сортировка методом вставки
- •5. Метод слияния
- •Void merge(int* a, int p, int q, int r)
- •Void sort_merge(int* a, int n, int p, int r)
- •6. Метод вычерпывания
- •7. Результаты тестирования
Void merge(int* a, int p, int q, int r)
{ int i, j, k, L= r – p + 1;
int* x = new int[L];
i = p; j = q + 1;
for (k = 0; k < L; k++) { if (j > r) { x[k] = A[i]; i++; continue; }
if (i > q) { x[k] = A[j]; j++; continue; }
if (A[i] <= A[j]) { x[k] = A[i]; i++; }
else { x[k] = A[j]; j++; }
}
for (k = 0; k < L; k++) A[p+k] = x[k];
delete[] x;
}
Главная процедура sort_merge выполняет сортировку произвольного отрезка массива A с числом элементов n и с границами [p,r].
Void sort_merge(int* a, int n, int p, int r)
{ int q;
if (p < r) { q = (p + r) / 2;
sort_merge(A, n, p, q); // рекурсивные вызовы
sort_merge(A, n, q+1, r); // функции merge_sort
merge(A, p, q, r);
}
}
Для того, чтобы выполнить сортировку массива А полностью, вызов функции sort_merge необходимо записать следующим образом:
sort_merge(a, n, 0, n-1);
Использование двух последних параметров в таком вызове связано с "рекурсивностью" функции sort_merge.
Основные элементы алгоритма:
- слияние двух упорядоченных массивов в один упорядоченный массив;
- рекурсия;
- операция упорядочения пары элементов.
Обозначим:
merge(A, p, q, r) - процедура слияния (предварительно упорядоченных) отрезков массива A[p .. q] и A[q+1 .. r] в отрезок A[p .. r] , q – номер среднего элемента отрезка [p .. r]. Если отрезок имеет четную длину, то q есть номер крайнего справа элемента левой половины отрезка. Будем для простоты считать, что n = 2 p .
sort_m(A, n, p, q) - процедура упорядочения методом слияния отрезка A[p .. q] массива A с размером n. Схема этой процедуры в общем выглядит так:
sort_m(A, n, p, r) // t = F(n)
{ if (n <= 2)
{ q = (p + r) / 2; // t = c0
merge(A, p, q, r); // t = c1n
}
if (n > 2)
{ q = (p + r) / 2; // t = c0
sort_m(A, n, p, q); // t = F(n/2)
sort_m(A, n, q + 1, r); // t = F(n/2)
merge(A, p, q, r); // t = c1n
}
}
Из текста следует:
Если n<=2, то F(2) = c0 + 2c1 ,
Если n > 2, то F(n) = с0 + 2F(n/2) + c1n .
Решение будем искать методом развертывания. Найдем F(n) для n = 8 :
F(8) = c0 + 2F(4) + 8c1 ,
F(4) = c0 + 2F(2) + 4c1 ,
F(2) = c0 + 2c1 .
Отсюда:
F(8) = c0 + 8c1 + 2(c0 + 4c1 + 2(c0 + 2c1)) = 7c0 + 24c1 = (8-1)c0 + 8log2(8)c1
Обобщая на случай произвольного n, получаем:
F(n) = c0 (n-1) + c1 n log2(n) . Отсюда, с учетом закона поглощения, имеем:
F(n) = (n log n) .
6. Метод вычерпывания
Пусть имеем числовой массив a[0] .. a[n-1] , все элементы которого имеют случайные значения, которые равномерно распределены на отрезке [a,b]. Разделим отрезок [a,b] на n интервалов и создадим n (вначале пустых) списков, по одному для каждого интервала. Алгоритм вычерпывания включает в себя два этапа:
1) распределим элементы исходного массива по соответствующим спискам;
2) упорядочим каждый из списков;
3) перепишем последовательно элементы каждого из списков в исходный массив a[0] .. a[n-1].
Доказано, что алгоритм вычерпывания имеет в среднем линейный порядок. Его функция сложности принадлежит асимптотическому классу (n).
Метод вычерпывания может быть применен и для упорядочивания не числовых массивов. Однако это возможно, если элементы исходного массива можно разделить на n групп, где n - размер исходного массива, таким образом, чтобы:
а) для любого i любой элемент группы с номером i+1 был больше любого элемента группы с номером i ;
б) среднее количество элементов исходного массива, принадлежащих группе с произвольным номером равно 1 или мало отличается от 1.
Подробнее о методе вычерпывания см. в [1-Кормен].