Слайд 2Задача сортировки элементов массива
![Задача сортировки элементов массива](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-1.jpg)
Слайд 3Рекуррентное слияние (снизу вверх)
![Рекуррентное слияние (снизу вверх)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-2.jpg)
Слайд 4Рекуррентное слияние (снизу вверх)
![Рекуррентное слияние (снизу вверх)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-3.jpg)
Слайд 5Рекуррентный алгоритм слияния
void merge_sort(double *A, int n)
{
int s, b, c, e;
![Рекуррентный алгоритм слияния void merge_sort(double *A, int n) { int s, b,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-4.jpg)
double *D = new double[n];
for (s = 1; s < n; s *= 2) {
for (b = 0; b < n; b += s*2) {
c = min(b+s-1, n-1);
e = min(c+s, n-1);
merge_series(A, b, c, e, D);
}
for (b = 0; b < n; b++) A[b] = D[b];
}
delete [] D;
}
Слайд 8Сортировка вставкам с шагом h
![Сортировка вставкам с шагом h](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-7.jpg)
Слайд 9Сортировка Шелла: идея и требования
![Сортировка Шелла: идея и требования](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-8.jpg)
Слайд 13Свойства пирамиды (бинарной кучи)
![Свойства пирамиды (бинарной кучи)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-12.jpg)
Слайд 16Трудоемкость построения пирамиды
![Трудоемкость построения пирамиды](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-15.jpg)
Слайд 17Трудоемкость построения пирамиды
![Трудоемкость построения пирамиды](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-16.jpg)
Слайд 18 Функция просеивания в пирамиде
Параметры и переменные функции sift:
i – начальный
![Функция просеивания в пирамиде Параметры и переменные функции sift: i – начальный](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-17.jpg)
номер просеиваемого элемента,
m – номер конечного элемента в текущей пирамиде,
j – текущий номер просеиваемого элемента,
k – номер левого или большего сына j.
void sift(double *A, int i, int m)
{
int j = i, k = i*2+1; // левый сын
while (k <= m)
{
if (k if (A[j] < A[k])
{ swap(A[j], A[k]); j = k; k = k*2+1; }
else break;
}
}
Слайд 19Алгоритм пирамидальной сортировки
void heap_sort(double *A, int n)
{
int i, m;
//
![Алгоритм пирамидальной сортировки void heap_sort(double *A, int n) { int i, m;](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-18.jpg)
построение пирамиды
for (i = n/2; i >= 0; i--)
sift(A, i, n-1);
// сортировка массива
for (m = n-1; m >= 1; m--)
{
swap(A[0], A[m]);
sift(A, 0, m-1);
}
}
Слайд 22Быстрая сортировка: трудоемкость в среднем
![Быстрая сортировка: трудоемкость в среднем](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-21.jpg)
Слайд 23Трудоемкость в среднем: доказательство
![Трудоемкость в среднем: доказательство](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-22.jpg)
Слайд 24Трудоемкость в среднем: доказательство
![Трудоемкость в среднем: доказательство](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-23.jpg)
Слайд 25Трудоемкость в среднем: доказательство
Таким образом:
![Трудоемкость в среднем: доказательство Таким образом:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-24.jpg)
Слайд 28Быстрая сортировка с 2 рекурсивными вызовами
void quick_sort_2(double *A, int b, int e)
{
![Быстрая сортировка с 2 рекурсивными вызовами void quick_sort_2(double *A, int b, int](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-27.jpg)
double x; int i, j;
x = A[(b+e)/2]; i = b; j = e;
while (i < j)
{
while (A[i] < x) i++;
while (A[j] > x) j--;
if (i <= j) {
{ swap(A[i], A[j]); i++; j--; }
}
if (b < j) quick_sort_2(A, b, j);
if (i < e) quick_sort_2(A, i, e);
}
Слайд 29Быстрая сортировка с 1 рекурсивным вызовом
![Быстрая сортировка с 1 рекурсивным вызовом](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-28.jpg)
Слайд 30Быстрая сортировка с 1 рекурсивным вызовом
![Быстрая сортировка с 1 рекурсивным вызовом](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-29.jpg)
Слайд 31Быстрая сортировка с 1 рекурсивным вызовом
void quick_sort(double *A, int b, int e)
{
![Быстрая сортировка с 1 рекурсивным вызовом void quick_sort(double *A, int b, int](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-30.jpg)
double x; int i, j, c = b, d = e;
while (c < d) {
x = A[(c+d)/2]; i = c; j = d;
while (i < j) {
while (A[i] < x) i++;
while (A[j] > x) j--;
if (i <= j)
{ swap(A[i], A[j]); i++; j--; }
}
if (j-c < d-i)
{ if (c < j) quick_sort(A,c,j); c = i; }
else { if (i }
}
Слайд 33Поиск k-го минимального элемента
![Поиск k-го минимального элемента](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-32.jpg)
Слайд 34Поиск k-го минимального элемента
![Поиск k-го минимального элемента](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/970850/slide-33.jpg)