Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть

Презентация на тему Основы программирования. Эффективные алгоритмы сортировки

Содержание

2. Задача сортировки элементов массива
3. Рекуррентное слияние (снизу вверх)
4. Рекуррентное слияние (снизу вверх)
5. Рекуррентный алгоритм слиянияvoid merge_sort(double *A, int n){
6. Сортировка Шелла
7. Сортировка Шелла: h-цепочки
8. Сортировка вставкам с шагом h
9. Сортировка Шелла: идея и требования
10. Сортировка Шелла: выбор шага h
11. Сортировка Шелла: алгоритм
12. Пирамидальная сортировка
13. Свойства пирамиды (бинарной кучи)
14. Идея сортировки
15. Построение пирамиды
16. Трудоемкость построения пирамиды
17. Трудоемкость построения пирамиды
18. Функция просеивания в пирамидеПараметры и переменные
19. Алгоритм пирамидальной сортировкиvoid heap_sort(double *A, int n)
20. Быстрая сортировка (Хоар)
21. Быстрая сортировка
22. Быстрая сортировка: трудоемкость в среднем
23. Трудоемкость в среднем: доказательство
24. Трудоемкость в среднем: доказательство
25. Трудоемкость в среднем: доказательствоТаким образом:
26. Разделение массива: 1-й способ
27. Разделение массива: 2-й способ
28. Быстрая сортировка с 2 рекурсивными вызовамиvoid quick_sort_2(double
29. Быстрая сортировка с 1 рекурсивным вызовом
30. Быстрая сортировка с 1 рекурсивным вызовом
31. Быстрая сортировка с 1 рекурсивным вызовомvoid quick_sort(double
32. Свойства алгоритмов сортировки
33. Поиск k-го минимального элемента
34. Поиск k-го минимального элемента
35. Алгоритм поиска k-го минимального элементаdouble med(double *A,
36. Цифровая сортировка
37. Простейший алгоритм цифровой сортировки
38. Косвенная цифровая сортировкаПусть при тех же условиях
39. Алгоритм косвенной цифровой сортировки
40. Косвенная цифровая сортировка со спискамиЕсли использовать списки
41. Косвенная цифровая сортировка со списками
42. Цифровая сортировка целых чисел
43. Цифровая сортировка целых чисел
44. Скачать презентацию
45. Похожие презентации

Задача сортировки элементов массива

Главная
Информатика
Основы программирования. Эффективные алгоритмы сортировки

Основы программированияЭффективные алгоритмы сортировки

$Рекуррентный алгоритм слиянияvoid merge_sort(double *A, int n){ int s, b, c, e;$ Сортировка Шелла

Функция просеивания в пирамидеПараметры и переменные функции sift: i – начальный

$Алгоритм пирамидальной сортировкиvoid heap_sort(double *A, int n) { int i, m; //$ Быстрая сортировка (Хоар)

Быстрая сортировка: трудоемкость в среднем

Трудоемкость в среднем: доказательствоТаким образом:

$Быстрая сортировка с 2 рекурсивными вызовамиvoid quick_sort_2(double *A, int b, int e){$ Быстрая сортировка с 1 рекурсивным вызовом

$Быстрая сортировка с 1 рекурсивным вызовомvoid quick_sort(double *A, int b, int e){$ Свойства алгоритмов сортировки

Алгоритм поиска k-го минимального элементаdouble med(double *A, int n, int k){ int

Косвенная цифровая сортировкаПусть при тех же условиях массив A нужно упорядочить косвенно,

Косвенная цифровая сортировка со спискамиЕсли использовать списки целых (класс List из раздела

Косвенная цифровая сортировка со списками

Цифровая сортировка неотрицательных целых

Слайды презентации

Слайд 2 Задача сортировки элементов массива

Слайд 3 Рекуррентное слияние (снизу вверх)

Слайд 4 Рекуррентное слияние (снизу вверх)

Слайд 5 Рекуррентный алгоритм слияния
void merge_sort(double *A, int n)
{
int

$Рекуррентный алгоритм слиянияvoid merge_sort(double *A, int n){ int s, b, c,$

s, b, c, e;
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;
}

Слайд 6 Сортировка Шелла

Слайд 7 Сортировка Шелла: h-цепочки

Слайд 8 Сортировка вставкам с шагом h

Слайд 9 Сортировка Шелла: идея и требования

Слайд 10 Сортировка Шелла: выбор шага h

Слайд 11 Сортировка Шелла: алгоритм

Слайд 12 Пирамидальная сортировка

Слайд 13 Свойства пирамиды (бинарной кучи)

Слайд 14 Идея сортировки

Слайд 15 Построение пирамиды

Слайд 16 Трудоемкость построения пирамиды

Слайд 17 Трудоемкость построения пирамиды

Слайд 18 Функция просеивания в пирамиде
Параметры и переменные функции

Функция просеивания в пирамидеПараметры и переменные функции sift: i –

sift:
i – начальный номер просеиваемого элемента,
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)
{

$Алгоритм пирамидальной сортировкиvoid heap_sort(double *A, int n) { int i, m;$

int i, m;
// построение пирамиды
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);
}
}

Слайд 20 Быстрая сортировка (Хоар)

Слайд 21 Быстрая сортировка

Слайд 22 Быстрая сортировка: трудоемкость в среднем

Слайд 23 Трудоемкость в среднем: доказательство

Слайд 24 Трудоемкость в среднем: доказательство

Слайд 25 Трудоемкость в среднем: доказательство
Таким образом:

Слайд 26 Разделение массива: 1-й способ

Слайд 27 Разделение массива: 2-й способ

Слайд 28 Быстрая сортировка с 2 рекурсивными вызовами
void quick_sort_2(double *A,

Быстрая сортировка с 2 рекурсивными вызовамиvoid quick_sort_2(double *A, int b, int

int b, int e)
{ 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 рекурсивным вызовом

Слайд 30 Быстрая сортировка с 1 рекурсивным вызовом

Слайд 31 Быстрая сортировка с 1 рекурсивным вызовом
void quick_sort(double *A,

Быстрая сортировка с 1 рекурсивным вызовомvoid quick_sort(double *A, int b, int

int b, int e)
{ 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 }
}

Слайд 32 Свойства алгоритмов сортировки

Слайд 33 Поиск k-го минимального элемента

Слайд 34 Поиск k-го минимального элемента

Слайд 35 Алгоритм поиска k-го минимального элемента
double med(double *A, int

Алгоритм поиска k-го минимального элементаdouble med(double *A, int n, int k){

n, int k)
{ int b = 0, e =

n-1; double x;
while (b < e)
{
j = b; i = e; x = A[b];
while (j < i)
if (A[i] >= x) i--;
else
{ A[j++] = A[i]; A[i] = A[j]; A[j] = x; }
if (k < j) e = j-1;
else if (k > j) b = j+1;
else { b = j; break; }
}
return A[b];
}

Слайд 36 Цифровая сортировка

Слайд 37 Простейший алгоритм цифровой сортировки

Слайд 38 Косвенная цифровая сортировка
Пусть при тех же условиях массив

Косвенная цифровая сортировкаПусть при тех же условиях массив A нужно упорядочить

A нужно упорядочить косвенно, т.е. сформировать массив индексов в

порядке возрастания элементов A.
В этом случае нам понадобятся 3 целочисленных массива:
формируемый массив индексов Ind[0…n-1],
массив счетчиков count[0…e-b],
массив pos[0…e-b] текущих позиций в Ind индексов элементов массива A (индекс i очередного выбираемого элемента A[i] будет записан в Ind на позиции pos[A[i]-b]).

Слайд 39 Алгоритм косвенной цифровой сортировки

Слайд 40 Косвенная цифровая сортировка со списками
Если использовать списки целых

Косвенная цифровая сортировка со спискамиЕсли использовать списки целых (класс List из

(класс List из раздела «Линейные списки»), то можно записать

более элегантный алгоритм косвенной сортировки массива A.
В этом случае нам понадобятся:
формируемый список индексов LRes – очередь индексов в порядке возрастания значений A,
массив списков LMas[0…e-b] (индекс i очередного выбираемого элемента A[i] будет добавлен в конец списка LMas[A[i]-b]).
Выходной список (очередь) LRes формируется с помощью последовательного объединения списков LMas.