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

Сортировка

Содержание

Сложные данныеДанные состоят из нескольких полей:struct element { field x; field y; }Пусть значение функции сравнения зависит только от поля xПоле x называют ключом, по которому производится сортировка.

Слайды и текст этой презентации

Слайд 1Сортировка
Пусть есть последовательность a0, a1... an и функция сравнения,

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

значений: меньше, больше или равно.

Задача сортировки
перестановка членов последовательности таким образом, чтобы выполнялось условие:
ai <= ai+1, для всех i от 0 до n.

Сортировка Пусть есть последовательность a0, a1... an и функция сравнения, которая на любых двух элементах последовательности принимает

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

field y; }

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

x

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

Сложные данныеДанные состоят из нескольких полей:struct element { field x; field y; }Пусть значение функции сравнения зависит

Слайд 3Пример

Пример

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

выполняемой некоторым алгоритмом, от размера входных данных -
f(n)
Объём работы
=

{

Время

,

Память

}

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

Объем памяти

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

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

СЛОЖНОСТИ АЛГОРИТМА

Θ(g(n)) - если ∃ с1>0, с2>0, n0>0 :

c1g(n)

≤ f(n) ≤ c2g(n), ∀ n>n0








Поиск точной функции, оценивающей временную сложность – трудоемкая задачаОЦЕНКИ ФУНКЦИИ СЛОЖНОСТИ АЛГОРИТМАΘ(g(n)) - если ∃ с1>0, с2>0,

Слайд 8O(g(n)) - если ∃ c>0, n0>0 :
0 ≤ f(n)

≤ cg(n),∀ n> n0











Например:
f(n) = n2 + 5n +

100
Подберем
O(n) = 1.1n2
O(g(n)) - если ∃ c>0, n0>0 : 0 ≤ f(n) ≤ cg(n),∀ n> n0Например: f(n) = n2

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

оценка f(n), то говорят, что класс функций f(n) растет не

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

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

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

Слайд 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)
Порядок функции 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)

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,… полиномиальная сложность
О(logN) – логарифмическая сложность
О(N*logN)
O(2n) – экспоненциальная

сложность
Типы сложности алгоритмаO(1) – константная сложностьО(n) – линейная сложностьО(nk), k = 2,3,4,… полиномиальная сложностьО(logN) – логарифмическая сложностьО(N*logN)

Слайд 13int 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(1)

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

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

O(1)

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

Слайд 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)

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

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

= 0;
q = x*x*x/3;
for(int i=1;i

II вариантint n = 10;float x = 2;double q,q1;double S = 0;q = x*x*x/3;for(int i=1;i

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


1
2
3
1
2
3
1
2
3

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

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

частично отсортированных данных.
Вставка
Выбор


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

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

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

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

Слайд 20Способы сортировки


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

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

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

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

Поразрядная сортировка (RadixSort)

Логарифмические и линейные алгоритмы Пирамидальная сортировка (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 цикла

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

элемент занимает «свое» место в массиве

На каждом шаге внутреннего цикла

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

Алгоритм содержит 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
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

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

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

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

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

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

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

элементом.

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

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

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

Слайд 284 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)

M =3(n-1)

C = (n-1)n/2

C = (n-1)n/2

C = (n-1)n/2

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

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

Слайд 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)
Оценка временной сложности алгоритма
неестественная
неустойчива

ЛучшийСреднийХудшийM = 0M =3n/2M =3(n-1)C = (n-1)n/2C = (n-1)n/2C = (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

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

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

в позицию 0.
1.2. Размер массива увеличивается на 1 , элементы

массива располагаются, начиная с 1-го элемента, на каждом шаге сортировки в 0 позицию выставляется вставляемый элемент
2. Поиск места с помощью бинарного деления
Оптимизация алгоритма1. Использование сторожевого элемента 1.1. Ищется минимальный элемент , выставляется в позицию 0. 1.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;
Алгоритм сортировки бинарными вставками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)
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)

Характеристики алгоритмаЛучшийСреднийХудший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)

Слайд 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

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

Устойчивая

ЛучшийСреднийХудшийM = 0M =(n-1)(n+3)/2M = (n-1)(n+3)C = n-1C = (n+1)n/4C = (n+1)n/2Со сторожевым элементом (II)Бинарными вставкамиЛучшийСреднийХудшийM =

Слайд 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



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

Слайд 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




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

Слайд 39Пирамидальная сортировка
Пирамида – это частично упорядоченное двоичное дерево, элементы

которого расположены в узлах дерева по следующему правилу – каждый

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




Пирамидальная сортировка Пирамида – это частично упорядоченное двоичное дерево, элементы которого расположены в узлах дерева по следующему

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

Зарубежные модели общего и профессионального образования (на примере Зарубежные модели общего и профессионального образования (на примере 297
Противоречия в развитии художественной культуры Противоречия в развитии художественной культуры 360
Стилевое многообразие искусства XVII-XVIII веков Стилевое многообразие искусства XVII-XVIII веков 453
ОГБПОУ Ангарский медицинский колледж ОГБПОУ Ангарский медицинский колледж 305
Виртуализация Linux Виртуализация Linux 250
Реторсии в МЧП Реторсии в МЧП 431
Окружающий мир Окружающий мир 182
Тема 27. Післявоєнна відбудова і розвиток України в 1945 – початку 1950-х рр Тема 27. Післявоєнна відбудова і розвиток України в 1945 – початку 1950-х рр 212
Запреты на ввоз и вывоз, а также запреты на поведение в Великобритании Запреты на ввоз и вывоз, а также запреты на поведение в Великобритании 213
Военная кафедра при СГТУ им. Гагарина Ю.А. Лекция 1 / 7 : Цифроаналоговые и Военная кафедра при СГТУ им. Гагарина Ю.А. Лекция 1 / 7 : Цифроаналоговые и 237
Галактики Галактики 213
Мой папа самый лучший! Мой папа самый лучший! 596
Я и мои дети Я и мои дети 198
Я город свой знаю, ведь я в нем живу (игра-викторина) Я город свой знаю, ведь я в нем живу (игра-викторина) 237
Понятие case технологии Понятие case технологии 663
О конкурсе научно-технологических проектов БОЛЬШИЕ ВЫЗОВЫ О конкурсе научно-технологических проектов БОЛЬШИЕ ВЫЗОВЫ 192
SMART- методика в создании проектов SMART- методика в создании проектов 337
Restaurant... I’d like to order, please Restaurant... I’d like to order, please 229
12 апреля - День космонавтики 12 апреля - День космонавтики 344
Адресаты любовной лирики Лермонтова Адресаты любовной лирики Лермонтова 411

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

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

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

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

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

Яндекс.Метрика