Сортировка

Сентябрь 3, 2022

Главная
Алгебра
Сортировка

Содержание

2. Сложные данные Данные состоят из нескольких полей: struct element { field x; field y; } Пусть
3. Пример
6. Характеристики сортировки Вычислительная сложность алгоритма - функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от размера
7. Поиск точной функции, оценивающей временную сложность – трудоемкая задача ОЦЕНКИ ФУНКЦИИ СЛОЖНОСТИ АЛГОРИТМА Θ(g(n)) - если
8. O(g(n)) - если ∃ c>0, n0>0 : 0 ≤ f(n) ≤ cg(n),∀ n> n0 Например: f(n)
9. О-функция – верхняя асимптотическая оценка трудоемкости алгоритма Если получена верхняя асимптотическая оценка f(n), то говорят, что
10. Порядок функции f(n) - O(N2) О – функции выражают относительную скорость алгоритма в зависимости от некоторой
11. O(1,5*N) = O((17*N)*N) = O(N) O(17*N)*O(N) O(N2) = O(N)*O(N) = O(N*N) = = O(N5+N2) = O(N5)
12. Типы сложности алгоритма O(1) – константная сложность О(n) – линейная сложность О(nk), k = 2,3,4,… полиномиальная
13. int y,n; float x; y = scanf(“%d”,&n); if (n==0) { printf(“Введены неверные данные…\n ”); printf(“Для продолжения
14. Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность. Оцените сложность алгоритма поиска минимального элемента квадратной
15. О(1) О(1) О(1) О(1) О(1) О(n)* О(i)+O(2i+1)+O(1)+O(i) О(2i+1) Среднее O(2n+1) ≈ O(n) О(n)
16. II вариант int n = 10; float x = 2; double q,q1; double S = 0;
17. Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов. 1 2 3 1 2 3
18. Естественность поведения - эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Вставка Выбор
19. Сфера применения Внутренние Внешние работают с данными в оперативной памяти с произвольным доступом упорядочивают информацию, расположенную
20. Способы сортировки Квадратичные и субквадратичные алгоритмы: Сортировка выбором (SelectSort) Сортировка вставками (InsertSort) Сортировка обменом (BubbleSort) Сортировка
21. Логарифмические и линейные алгоритмы Пирамидальная сортировка (HeapSort) Сортировка Хоара (QuickSort) Поразрядная сортировка (RadixSort)
22. Сортировка обменом Сортировка сравнивает пары рядом стоящих элементов и меняет их местами, если значение первого элемента
23. Алгоритм содержит 2 цикла На каждом шаге внутреннего цикла самый «большой» элемент занимает «свое» место в
24. Оптимизация алгоритма Фиксировать уже поставленные на свои места элементы Проверять, был ли выполнен хотя бы один
25. Характеристики алгоритма Лучший Средний Худший M = 0 M =3(n2 - n)/4 M =3(n2 - n)/2
26. от O(n) до О(n2) Оценка временной сложности алгоритма Естественность естественная Устойчивость устойчива
27. Сортировка выбором При первом просмотре элементов массива ищется индекс минимального элемента k, элемент с индексом k
28. 4 7 8 5 2 i=0 k = 4 → 2 7 8 5 4 2
29. Лучший Средний Худший M = 0 M =3n/2 M =3(n-1) C = (n-1)n/2 C = (n-1)n/2
30. Сортировка вставками Полагается i = 1, считается что массив от 0 до i -1 упорядочен. В
31. Оптимизация алгоритма 1. Использование сторожевого элемента 1.1. Ищется минимальный элемент , выставляется в позицию 0. 1.2.
32. Алгоритм сортировки бинарными вставками 1. для i от 2 до n если a[i-1]>a[i] то x:= a[i];
33. Характеристики алгоритма Лучший Средний Худший M = 2(n-1) M = 1/4 (n2+9n-10) M = 1/2 (n2+3n-4)
34. Лучший Средний Худший M = 0 M =(n-1)(n+3)/2 M = (n-1)(n+3) C = n-1 C =
35. Сортировка Шелла Сортирует элементы массива, отстоящие друг от друга на заданный интервал . После того, как
36. Сортировка Шелла Например, для массива из 7 элементов: 23 12 43 54 83 11 2 ?
37. Сортировка комбинированная Комбинация пузырька и сортировки Шелла. На каждом шаге сравниваются значения отстоящие друг от друга
38. Сортировка комбинированная 23 12 43 54 83 11 Hi0=7 H1= (7*8)/11=5 23 12 43 54 83
40. Скачать презентацию

Слайд 2

Сложные данные
Данные состоят из нескольких полей:
struct element { field x; field

y; }
Пусть значение функции сравнения зависит только от поля x

Поле x называют ключом, по которому
производится сортировка.

Слайд 3

Пример

Слайд 4

Слайд 5

Слайд 6

Характеристики сортировки
Вычислительная сложность алгоритма - функция, определяющая зависимость объёма работы, выполняемой

некоторым алгоритмом, от размера входных данных -
f(n)

Объём работы

= {

Время

Память

}

Количество элементарных шагов

Объем памяти

Слайд 7

Поиск точной функции, оценивающей временную сложность – трудоемкая задача
ОЦЕНКИ ФУНКЦИИ СЛОЖНОСТИ

АЛГОРИТМА
Θ(g(n)) - если ∃ с1>0, с2>0, n0>0 :
c1g(n) ≤ f(n) ≤ c2g(n), ∀ n>n0

Слайд 8

O(g(n)) - если ∃ c>0, n0>0 :
0 ≤ f(n) ≤

cg(n),∀ n> n0

Например:
f(n) = n2 + 5n + 100
Подберем
O(n) = 1.1n2

Слайд 9

О-функция – верхняя асимптотическая оценка трудоемкости алгоритма
Если получена верхняя асимптотическая оценка

f(n), то говорят, что класс функций f(n) растет не быстрее, чем функция g(n) с точностью до постоянного множителя

Ω-функция – нижняя асимптотическая оценка трудоемкости алгоритма
Ω(g(n)) - если ∃ c>0, n0>0 :
0 ≤ сg(n) ≤ f(n),∀ n> n0

Слайд 10

Порядок функции f(n) - O(N2)
О – функции выражают относительную скорость алгоритма

в зависимости от некоторой переменной (или переменных).

Правила преобразования
1. O(k*f)=O(f)
2. O(f*g)=O(f)*O(g) или O(f/g)=O(f)/O(g)
3. O(f+g) равна доминанте O(f) и O(g)

Слайд 11

O(1,5N) =
O((17N)N) =
O(N)
O(17N)O(N)
O(N2)
=
O(N)O(N)
=
O(N*N)
=
=
O(N5+N2) =
O(N5)

Слайд 12

Типы сложности алгоритма
O(1) – константная сложность
О(n) – линейная сложность
О(nk), k =

2,3,4,… полиномиальная сложность
О(logN) – логарифмическая сложность
О(N*logN)
O(2n) – экспоненциальная сложность

Слайд 13

int y,n;
float x;
y = scanf(“%d”,&n);
if (n==0)
{ printf(“Введены неверные

данные…\n ”);
printf(“Для продолжения нажмите любую
клавишу…”);
getch();
exit(0);}
else {
x = 25.5*sin(2*n)/n;
printf (“Значение x = %8.2f”, x);}
}

O(1)+O(1)

O(1)

O(Выч. услов)

Доминанта O(true) и О(false)

O(1)

Слайд 14

Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность.
Оцените сложность

алгоритма поиска минимального элемента квадратной матрицы размерности n.

…
int n,min = x[0][0];
for(int i=0;i for(int j = 0;j if (x[i][j] < min) min = x[i][j];
…

O(1) +

O(N) *

O(N)*

O(выч. условия) +
О(выч. выражения)

О(N2)

Слайд 15

О(1)
О(1)
О(1)
О(1)
О(1)
О(n)*
О(i)+O(2i+1)+O(1)+O(i)
О(2i+1)
Среднее O(2n+1) ≈ O(n)
О(n)

Слайд 16

II вариант
int n = 10;
float x = 2;
double q,q1;
double S =

0;
q = x*x*x/3;
for(int i=1;i<=n;i++)
{
if(i%2) S-=q; else S+=q;
q = (q*x*x*(2*i+1))/((i+1)*(2*i+3));
}

О(n)

Слайд 17

Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов.
1
2
3
1
2
3
1
2
3

Слайд 18

Естественность поведения - эффективность метода при обработке уже отсортированных, или частично

отсортированных данных.

Вставка

Выбор

Слайд 19

Сфера применения
Внутренние
Внешние
работают с данными в оперативной памяти с произвольным доступом
упорядочивают

информацию, расположенную на внешних носителях.

Слайд 20

Способы сортировки
Квадратичные и субквадратичные алгоритмы:
Сортировка выбором (SelectSort)
Сортировка вставками

(InsertSort)
Сортировка обменом (BubbleSort)
Сортировка Шелла (ShellSort)
Комбинированная сортировка (CombSort)

Слайд 21

Логарифмические и линейные алгоритмы
Пирамидальная сортировка (HeapSort)
Сортировка Хоара (QuickSort)
Поразрядная

сортировка (RadixSort)

Слайд 22

Сортировка обменом
Сортировка сравнивает пары рядом стоящих элементов и меняет их

местами, если значение первого элемента из пары больше значения второго элемента.

4 7 8 5 2
4 7 5 2 8
4 5 2 7 8
4 2 5 7 8
2 4 5 7 8

Слайд 23

Алгоритм содержит 2 цикла
На каждом шаге внутреннего цикла самый «большой» элемент

занимает «свое» место в массиве
На каждом шаге внутреннего цикла самый маленький элемент передвигается ровно на одну позицию к «своему» месту

Слайд 24

Оптимизация алгоритма
Фиксировать уже поставленные на свои места элементы
Проверять, был ли выполнен

хотя бы один обмен во внутреннем цикле
Просматривать массив в двух направлениях

Слайд 25

Характеристики алгоритма
Лучший
Средний
Худший
M = 0
M =3(n2 - n)/4
M =3(n2 - n)/2
C =

(n-1)n/2

C = (n-1)n/2

Классическая реализация

Лучший

Средний

Худший

M = 0

M =3(n2 - n)/4

M =3(n2 - n)/2

C = n-1

C = (n-1)n/4

C = (n-1)n/2

С проверкой обменов

Слайд 26

от O(n) до О(n2)
Оценка временной сложности алгоритма
Естественность
естественная
Устойчивость
устойчива

Слайд 27

Сортировка выбором
При первом просмотре элементов массива ищется индекс минимального элемента

k, элемент с индексом k меняется местом с первым элементом.

При втором просмотре ищется индекс минимального элемента k среди оставшихся, элемент с индексом k меняется местом со вторым элементом.

На i-том просмотре ищется индекс минимального элемента k среди элементов с номерами от i до n и меняются местами элементы с номерами i и k.

Слайд 28

4 7 8 5 2 i=0 k = 4 → 2

7 8 5 4
2 7 8 5 4 i=2 k = 5 → 2 4 8 5 7
2 4 8 5 7 i=3 k = 4 → 2 4 5 8 7
2 4 5 8 7 i=4 k = 5 → 2 4 5 7 8

Характеристики алгоритма

Лучший

Средний

Худший

M = 3(n-1)

M =3(n-1)

C = (n-1)n/2

Классическая реализация

Слайд 29

Лучший
Средний
Худший
M = 0
M =3n/2
M =3(n-1)
C = (n-1)n/2
C = (n-1)n/2
C = (n-1)n/2
С

проверкой индексов

О(n2)

Оценка временной сложности алгоритма

неестественная

неустойчива

Слайд 30

Сортировка вставками

Полагается i = 1, считается что массив от

0 до i -1 упорядочен. В этом упорядоченном массиве ищется место для x[i]. В дальнейшем, значение i увеличивается на единицу и алгоритм повторяется.

4 7 8 5 2 i=1 → 4 7 8 5 2
4 7 8 5 2 i=2 → 4 7 8 5 2
4 7 8 5 2 i=3 → 4 5 7 8 2
4 5 7 8 2 i=4 → 2 4 5 7 8

Слайд 31

Оптимизация алгоритма
1. Использование сторожевого элемента
1.1. Ищется минимальный элемент , выставляется в

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

Слайд 32

Алгоритм сортировки бинарными вставками
1. для i от 2 до n
если

a[i-1]>a[i] то
x:= a[i];
left:= 1;
right:= i-1;
пока left<=right
sred:= (left+right) / 2;
если a[sred] иначе right:= sred-1;
для j:= i-1 до left шаг -1
a[j+1]:= a[j];
a[left]:= x;

Слайд 33

Характеристики алгоритма
Лучший
Средний
Худший
M = 2(n-1)
M = 1/4 (n2+9n-10)
M = 1/2 (n2+3n-4)

C = 2(n-1)

C = 1/4 (n2+n-2)

C = 1/2 (n2 +n-2)

Классическая реализация

Лучший

Средний

Худший

M = 2(n-1)

M = 1/4 (n2+9n-10)

M = 1/2 (n2+3n-4)

C = n-1

C = 1/8 (n2 + n - 2)

C = 1/4 (n2 + n -2)

Со сторожевым элементом (I)

Слайд 34

Лучший
Средний
Худший
M = 0
M =(n-1)(n+3)/2
M = (n-1)(n+3)
C = n-1
C = (n+1)n/4
C =

(n+1)n/2

Со сторожевым элементом (II)

Бинарными вставками

Лучший

Средний

Худший

M = 0

M =(n-1)(n+3)/2

M = (n-1)(n+3)

C = n-1

C = N/2*log2 N

C = N*log2 N

Естественная

Устойчивая

Слайд 35

Сортировка Шелла
Сортирует элементы массива, отстоящие друг от друга на заданный

интервал .
После того, как все элементы массива, отстоящие друг от друга на будут отсортированы, интервал изменяется по правилу Hi+1=(Hi - 1)/2 для массивов, содержащих более 500 элементов и Hi+1=(Hi-1)/3 для массивов, содержащих менее 500 элементов. За H0 принимается число элементов массива. Метод заканчивает работу, когда становится меньше 1. Модификация сортировки вставками

Слайд 36

Сортировка Шелла
Например, для массива из 7 элементов:
23 12 43

54 83 11 2 ? 23 12 43 54 83 11 2
23 12 43 54 83 11 2 ? 23 12 43 54 83 11 2
23 12 43 54 83 11 2 ? 23 12 43 54 83 11 2
23 12 43 54 83 11 2 ? 23 12 43 11 83 54 2
23 12 43 54 83 11 2 ? 23 12 43 11 2 54 83
Так как обмены при первом проходе были, то шаг остается прежним:
23 12 43 11 2 54 83 ? 23 12 43 11 2 54 83
23 12 43 11 2 54 83 ? 23 11 43 12 2 54 83
23 11 43 12 2 54 83 ? 23 11 2 12 43 54 83
23 11 2 12 43 54 83 ? 23 11 2 12 43 54 83
23 11 2 12 43 54 83 ? 23 11 2 12 43 54 83

Слайд 37

Сортировка комбинированная
Комбинация пузырька и сортировки Шелла. На каждом шаге сравниваются значения

отстоящие друг от друга на заданное значение шага Hi+1=8Hi /11 , но такое сравнение происходит всего один раз. Как только значение смещения становится равным 1, выполняется сортировка до конца методом пузырька. За принимается число элементов массива.

Слайд 38

Сортировка комбинированная
23 12 43 54 83 11 Hi0=7 H1= (7*8)/11=5
23 12

43 54 83 11 2 ? 11 12 43 54 83 23 2
11 12 43 54 83 23 2 ? 11 2 43 54 83 23 12
H2= (5*8)/11=3
11 2 43 54 83 23 12 ? 11 2 43 54 83 23 12
11 2 43 54 83 23 12 ? 11 2 43 54 83 23 12
11 2 43 54 83 23 12 ? 11 2 23 54 83 43 12
11 2 23 54 83 43 12 ? 11 2 23 12 83 43 54
H3= (3*8)/11=2
11 2 23 12 83 43 54 ? 11 2 23 12 83 43 54
11 2 23 12 83 43 54 ? 11 2 23 12 83 43 54
11 2 23 12 83 43 54 ? 11 2 23 12 83 43 54
11 2 23 12 83 43 54 ? 11 2 23 12 83 43 54
11 2 23 12 83 43 54 ? 11 2 23 12 54 43 83

Сортировка

Содержание

Сложные данныеДанные состоят из нескольких полей:struct element { field x; field

Пример

Характеристики сортировкиВычислительная сложность алгоритма - функция, определяющая зависимость объёма работы, выполняемой

Поиск точной функции, оценивающей временную сложность – трудоемкая задачаОЦЕНКИ ФУНКЦИИ СЛОЖНОСТИ

O(g(n)) - если ∃ c>0, n0>0 : 0 ≤ f(n) ≤

О-функция – верхняя асимптотическая оценка трудоемкости алгоритмаЕсли получена верхняя асимптотическая оценка

Порядок функции f(n) - O(N2)О – функции выражают относительную скорость алгоритма

O(1,5*N) =O((17*N)*N) = O(N)O(17*N)*O(N)O(N2)=O(N)*O(N)=O(N*N)==O(N5+N2) =O(N5)

Типы сложности алгоритмаO(1) – константная сложностьО(n) – линейная сложностьО(nk), k =

int y,n; float x;y = scanf(“%d”,&n);if (n==0) { printf(“Введены неверные

Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность. Оцените сложность

О(1)О(1)О(1)О(1)О(1)О(n)*О(i)+O(2i+1)+O(1)+O(i)О(2i+1)Среднее O(2n+1) ≈ O(n)О(n)

II вариантint n = 10;float x = 2;double q,q1;double S =

Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов. 123123123

Естественность поведения - эффективность метода при обработке уже отсортированных, или частично

Сфера применения ВнутренниеВнешниеработают с данными в оперативной памяти с произвольным доступомупорядочивают

Способы сортировки Квадратичные и субквадратичные алгоритмы: Сортировка выбором (SelectSort) Сортировка вставками

Логарифмические и линейные алгоритмы Пирамидальная сортировка (HeapSort) Сортировка Хоара (QuickSort) Поразрядная

Сортировка обменом Сортировка сравнивает пары рядом стоящих элементов и меняет их

Алгоритм содержит 2 циклаНа каждом шаге внутреннего цикла самый «большой» элемент

Оптимизация алгоритмаФиксировать уже поставленные на свои места элементыПроверять, был ли выполнен

Характеристики алгоритмаЛучшийСреднийХудшийM = 0M =3(n2 - n)/4M =3(n2 - n)/2C =

от O(n) до О(n2)Оценка временной сложности алгоритмаЕстественностьестественнаяУстойчивостьустойчива

Сортировка выбором При первом просмотре элементов массива ищется индекс минимального элемента

4 7 8 5 2 i=0 k = 4 → 2

ЛучшийСреднийХудшийM = 0M =3n/2M =3(n-1)C = (n-1)n/2C = (n-1)n/2C = (n-1)n/2С

Сортировка вставками Полагается i = 1, считается что массив от

Оптимизация алгоритма1. Использование сторожевого элемента 1.1. Ищется минимальный элемент , выставляется в

Алгоритм сортировки бинарными вставками1. для i от 2 до n если

Характеристики алгоритмаЛучшийСреднийХудшийM = 2(n-1)M = 1/4 (n2+9n-10) M = 1/2 (n2+3n-4)

ЛучшийСреднийХудшийM = 0M =(n-1)(n+3)/2M = (n-1)(n+3)C = n-1C = (n+1)n/4C =

Сортировка Шелла Сортирует элементы массива, отстоящие друг от друга на заданный

Сортировка Шелла Например, для массива из 7 элементов: 23 12 43

Сортировка комбинированнаяКомбинация пузырька и сортировки Шелла. На каждом шаге сравниваются значения

Сортировка комбинированная23 12 43 54 83 11 Hi0=7 H1= (7*8)/11=523 12

Похожие презентации

Сложные данные
Данные состоят из нескольких полей:
struct element { field x; field

Характеристики сортировки
Вычислительная сложность алгоритма - функция, определяющая зависимость объёма работы, выполняемой

Поиск точной функции, оценивающей временную сложность – трудоемкая задача
ОЦЕНКИ ФУНКЦИИ СЛОЖНОСТИ

O(g(n)) - если ∃ c>0, n0>0 :
0 ≤ f(n) ≤

О-функция – верхняя асимптотическая оценка трудоемкости алгоритма
Если получена верхняя асимптотическая оценка

Порядок функции f(n) - O(N2)
О – функции выражают относительную скорость алгоритма

O(1,5N) =
O((17N)N) =
O(N)
O(17N)O(N)
O(N2)
=
O(N)O(N)
=
O(N*N)
=
=
O(N5+N2) =
O(N5)

Типы сложности алгоритма
O(1) – константная сложность
О(n) – линейная сложность
О(nk), k =

int y,n;
float x;
y = scanf(“%d”,&n);
if (n==0)
{ printf(“Введены неверные

Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность.
Оцените сложность

О(1)
О(1)
О(1)
О(1)
О(1)
О(n)*
О(i)+O(2i+1)+O(1)+O(i)
О(2i+1)
Среднее O(2n+1) ≈ O(n)
О(n)

II вариант
int n = 10;
float x = 2;
double q,q1;
double S =

Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов.
1
2
3
1
2
3
1
2
3

Сфера применения
Внутренние
Внешние
работают с данными в оперативной памяти с произвольным доступом
упорядочивают

Способы сортировки
Квадратичные и субквадратичные алгоритмы:
Сортировка выбором (SelectSort)
Сортировка вставками

Логарифмические и линейные алгоритмы
Пирамидальная сортировка (HeapSort)
Сортировка Хоара (QuickSort)
Поразрядная

Сортировка обменом
Сортировка сравнивает пары рядом стоящих элементов и меняет их

Алгоритм содержит 2 цикла
На каждом шаге внутреннего цикла самый «большой» элемент

Оптимизация алгоритма
Фиксировать уже поставленные на свои места элементы
Проверять, был ли выполнен

Характеристики алгоритма
Лучший
Средний
Худший
M = 0
M =3(n2 - n)/4
M =3(n2 - n)/2
C =

от O(n) до О(n2)
Оценка временной сложности алгоритма
Естественность
естественная
Устойчивость
устойчива

Сортировка выбором
При первом просмотре элементов массива ищется индекс минимального элемента

Лучший
Средний
Худший
M = 0
M =3n/2
M =3(n-1)
C = (n-1)n/2
C = (n-1)n/2
C = (n-1)n/2
С

Сортировка вставками

Полагается i = 1, считается что массив от

Оптимизация алгоритма
1. Использование сторожевого элемента
1.1. Ищется минимальный элемент , выставляется в

Алгоритм сортировки бинарными вставками
1. для i от 2 до n
если

Характеристики алгоритма
Лучший
Средний
Худший
M = 2(n-1)
M = 1/4 (n2+9n-10)
M = 1/2 (n2+3n-4)

Лучший
Средний
Худший
M = 0
M =(n-1)(n+3)/2
M = (n-1)(n+3)
C = n-1
C = (n+1)n/4
C =

Сортировка Шелла
Сортирует элементы массива, отстоящие друг от друга на заданный

Сортировка Шелла
Например, для массива из 7 элементов:
23 12 43

Сортировка комбинированная
Комбинация пузырька и сортировки Шелла. На каждом шаге сравниваются значения

Сортировка комбинированная
23 12 43 54 83 11 Hi0=7 H1= (7*8)/11=5
23 12