Численные методы решения задач презентация

Содержание

Информатика. Тема 6. Численные методы решения задач. 6.1. Сортировка данных Сортировка – один из основных алгоритмов обработки информации, состоящий в переупорядочении по нужному признаку заданной последовательности величин. Дональд

Слайд 1ИНФОРМАТИКА

Тема 6.

Численные методы решения задач.

Слайд 2Информатика. Тема 6. Численные методы решения задач.
6.1. Сортировка данных

Сортировка – один

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

Дональд Кнут – американский ученый, преподаватель и идеолог программирования

Слайд 3Информатика. Тема 6. Численные методы решения задач.
Постановка задачи:
1) Имеется N элементов

R1, R2,…, RN, которые называются записями.
2) Каждая запись Rj, имеет ключ Kj.
3) На множестве ключей вводится отношение порядка < (меньше), что для трех разных ключей a, b, c выполняются следующие условия:
справедливо одно и только одно соотношение: a < b, a = b, a > b.
если a < b и b < c, то a < c.

Задача сортировки – найти такую перестановку записей p(1), p(2),…, p(N), после которой ключи расположились в неубывающем порядке KP(1) ≤ KP(2) ≤ KP(N).

Сортировка называется устойчивой, если она удовлетворяет дополнительному условию, что записи с одинаковыми ключами остаются в прежнем порядке, т.е. p(i) < p(j), если KP(i) = KP(j) и i < j.

Слайд 4Информатика. Тема 6. Численные методы решения задач.
Сортировку разделяют на два класса:

внутреннюю, когда все записи хранятся в быстрой оперативной памяти, и внешнюю, когда они там не помещаются.

Эффективность алгоритма сортировки можно оценить двумя показателями: количеством сравнений и количеством обменов.

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

Слайд 5Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

При сортировке

подсчетом используется вспомогательный массив
C(1), C(2),…, C(N), элементы которого изначально равны нулю.

Все ключи попарно сравниваются.

Если ключ Ki больше Kj, то элемент C(i) увеличивается на единицу.
В противном случае на единицу увеличивается элемент C(j).

После завершения сравнений величина C(j) + 1 определяет окончательное положение записи Rj.

Слайд 6Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 7Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 8Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 9Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 10Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 11Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 12Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 13Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 14Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 15Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 16Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 17Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 18Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 19Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 20Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 21Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 22Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 23Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 24Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 25Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 26Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 27Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 28Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 29Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 30Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 31Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 32Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 33Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 34Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 35Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 36Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 37Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 38Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 39Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 40Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом

Слайд 41Информатика. Тема 6. Численные методы решения задач.
6.1.2. Сортировка вставками

Пусть записи

R1, R2,…, Rj-1 размещены так, что K1 ≤ K2 ≤ Kj-1.
То есть считается, что предыдущие записи уже упорядочены.

Требуется разместить запись Rj.

Ключ Kj сравнивается по очереди с ключами Kj-1, Kj-2, Kj-3 … до тех пор, пока не будет определено, что запись Rj необходимо вставить между записями Ri и Ri+1.

Тогда записи Ri+1, Ri+2,…, Rj-1 сдвигаются.
Запись Rj занимает место (i+1).

Слайд 42Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

1, число обменов – 1.

Слайд 43Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

2, число обменов – 1.

Слайд 44Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

5, число обменов – 4.

Слайд 45Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

6, число обменов – 4.

Слайд 46Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

9, число обменов – 7.

Слайд 47Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

11, число обменов – 8.

Слайд 48Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

16, число обменов – 12.

Слайд 49Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

19, число обменов – 14.

Слайд 50Информатика. Тема 6. Численные методы решения задач.
Число сравнений – 25, число

обменов – 19.

Слайд 51Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
…
Число сравнений –

34, число обменов – 27.

Слайд 52Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

39, число обменов – 31.

Слайд 53Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

43, число обменов – 34.

Слайд 54Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

46, число обменов – 36.

Слайд 55Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

49, число обменов – 38.

Слайд 56Информатика. Тема 6. Численные методы решения задач.
Сортировка простыми вставками
Число сравнений –

53, число обменов – 41.

Слайд 57Информатика. Тема 6. Численные методы решения задач.
Сортировка бинарными вставками

Слайд 58Информатика. Тема 6. Численные методы решения задач.
Сортировка двухпутевыми вставками

Слайд 59Информатика. Тема 6. Численные методы решения задач.
6.1.3. Сортировка выбором

При сортировке

записей R1, R2,…, RN
1) Находится запись Rj, имеющая наибольший ключ Kj.

2) Происходит обмен записей Rj и RN.

3) Процедура поиска наибольшего ключа повторяется для записей R1, R2,…, RN-1. Подобная процедура повторяется (N-1) раз.

Слайд 60Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 15,

число обменов – 1.

Слайд 61Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 29,

число обменов – 2.

Слайд 62Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 42,

число обменов – 3.

Слайд 63Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 54,

число обменов – 4.

Слайд 64Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 65,

число обменов – 5.

Слайд 65Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 75,

число обменов – 6.

Слайд 66Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 84,

число обменов – 7.

Слайд 67Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 92,

число обменов – 8.

Слайд 68Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 99,

число обменов – 9.

Слайд 69Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 105,

число обменов – 10.

Слайд 70Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 110,

число обменов – 11.

Слайд 71Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 114,

число обменов – 12.

Слайд 72Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 117,

число обменов – 13.

Слайд 73Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 119,

число обменов – 13.

Слайд 74Информатика. Тема 6. Численные методы решения задач.
Сортировка выбором
Число сравнений – 120,

число обменов – 13.

Слайд 75Информатика. Тема 6. Численные методы решения задач.
6.1.4. Сортировка обменом

Простейший обменный

алгоритм называется «пузырек».

При сортировке записей R1, R2,…, RN алгоритмом «пузырек»
1) Сравниваются ключи двух соседних записей Rj и Rj-1.

2) Если ключ Kj меньше ключа Kj-1 записи Rj и Rj-1 обмениваются.

Слайд 76Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 1,

число обменов – 1.

Слайд 77Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 3,

число обменов – 2.

Слайд 78Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 5,

число обменов – 3.

Слайд 79Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 6,

число обменов – 4.

Слайд 80Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 7,

число обменов – 5.

Слайд 81Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 8,

число обменов – 6.

Слайд 82Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 9,

число обменов – 7.

Слайд 83Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 10,

число обменов – 8.

Слайд 84Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 11,

число обменов – 9.

Слайд 85Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 12,

число обменов – 10.

Слайд 86Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 13,

число обменов – 11.

Слайд 87Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 14,

число обменов – 12.

Слайд 88Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 15,

число обменов – 13.

Слайд 89Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 17,

число обменов – 14.

Слайд 90Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 19,

число обменов – 15.

Слайд 91Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 21,

число обменов – 16.

Слайд 92Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 22,

число обменов – 17.

Слайд 93Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 23,

число обменов – 18.

Слайд 94Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 24,

число обменов – 19.

Слайд 95Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 25,

число обменов – 20.

Слайд 96Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 26,

число обменов – 21.

Слайд 97Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 27,

число обменов – 22.

Слайд 98Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 28,

число обменов – 23.

Слайд 99Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 29,

число обменов – 24.

Слайд 100Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 30,

число обменов – 25.

Слайд 101Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 32,

число обменов – 26.

Слайд 102Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 34,

число обменов – 27.

Слайд 103Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 36,

число обменов – 28.

Слайд 104Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 37,

число обменов – 29.

Слайд 105Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 38,

число обменов – 30.

Слайд 106Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 39,

число обменов – 31.

Слайд 107Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 42,

число обменов – 32.

Слайд 108Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 46,

число обменов – 33.

Слайд 109Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 48,

число обменов – 34.

Слайд 110Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 49,

число обменов – 35.

Слайд 111Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 50,

число обменов – 36.

Слайд 112Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 54,

число обменов – 36.

Слайд 113Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 59,

число обменов – 37.

Слайд 114Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 60,

число обменов – 38.

Слайд 115Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 65,

число обменов – 38.

Слайд 116Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 70,

число обменов – 39.

Слайд 117Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 75,

число обменов – 39.

Слайд 118Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 79,

число обменов – 40.

Слайд 119Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 84,

число обменов – 40.

Слайд 120Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 87,

число обменов – 41.

Слайд 121Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 92,

число обменов – 41.

Слайд 122Информатика. Тема 6. Численные методы решения задач.
Сортировка «пузырьком»
Число сравнений – 99,

число обменов – 41.

Слайд 123Информатика. Тема 6. Численные методы решения задач.
6.1.5. Сортировка методом Шелла

При

сортировке «пузырьком» сравниваются ключи соседних записей (шаг сортировки равен единице).
Быстродействие можно повысить, применяя сортировку с убывающим шагом.

Дональд Шелл – американский ученый в области информатики

Слайд 124Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 8)

Число сравнений – 8, число обменов – 3.

Слайд 125Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 4)

Число сравнений – 11, число обменов – 3.

Слайд 126Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 4)

Число сравнений – 14, число обменов – 3.

Слайд 127Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 4)

Число сравнений – 18, число обменов – 4.

Слайд 128Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 4)

Число сравнений – 21, число обменов – 4.

Слайд 129Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 2)

Число сравнений – 30, число обменов – 7.

Слайд 130Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 2)

Число сравнений – 37, число обменов – 8.

Слайд 131Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 38, число обменов – 9.

Слайд 132Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 39, число обменов – 9.

Слайд 133Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 42, число обменов – 11.

Слайд 134Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 43, число обменов – 11.

Слайд 135Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 46, число обменов – 13.

Слайд 136Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 47, число обменов – 13.

Слайд 137Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 51, число обменов – 16.

Слайд 138Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 52, число обменов – 16.

Слайд 139Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 57, число обменов – 20.

Слайд 140Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 58, число обменов – 20.

Слайд 141Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 63, число обменов – 24.

Слайд 142Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 64, число обменов – 24.

Слайд 143Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 67, число обменов – 26.

Слайд 144Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 68, число обменов – 26.

Слайд 145Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки

равен 1)

Число сравнений – 72, число обменов – 29.

Слайд 146Информатика. Тема 6. Численные методы решения задач.
6.1.6. «Быстрая» сортировка

В 1962

году Ч.Э.Р. Хоар предложил обменную сортировку с разделением, которую назвал quicksort (быстрая сортировка).

Чарльз Энтони Ричард Хоар – английский ученый в области информатики

Слайд 147Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 6,

число обменов – 1.

Слайд 148Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 8,

число обменов – 2.

Слайд 149Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 9,

число обменов – 3.

Слайд 150Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 11,

число обменов – 4.

Слайд 151Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 13,

число обменов – 5.

Слайд 152Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 15,

число обменов – 6.

Слайд 153Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 18,

число обменов – 7.

Слайд 154Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 20,

число обменов – 8.

Слайд 155Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 21,

число обменов – 8.

Слайд 156Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 22,

число обменов – 9.

Слайд 157Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 23,

число обменов – 9.

Слайд 158Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 24,

число обменов – 9.

Слайд 159Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 25,

число обменов – 10.

Слайд 160Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 27,

число обменов – 11.

Слайд 161Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 28,

число обменов – 12.

Слайд 162Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 32,

число обменов – 12.

Слайд 163Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 33,

число обменов – 13.

Слайд 164Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 35,

число обменов – 14.

Слайд 165Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 36,

число обменов – 15.

Слайд 166Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 38,

число обменов – 15.

Слайд 167Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 39,

число обменов – 16.

Слайд 168Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 42,

число обменов – 16.

Слайд 169Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 45,

число обменов – 16.

Слайд 170Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 46,

число обменов – 17.

Слайд 171Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 47,

число обменов – 17.

Слайд 172Информатика. Тема 6. Численные методы решения задач.
Быстрая сортировка
Число сравнений – 48,

число обменов – 17.

Слайд 173Информатика. Тема 6. Численные методы решения задач.
6.1.7. Сравнение алгоритмов сортировки
Эффективность алгоритма

сортировки характеризуется несколькими параметрами:
Время сортировки
Память
Устойчивость
Естественность поведения

Время работы алгоритма сортировки зависит от количества сравнений ключей и количества перестановок записей.
Поскольку исходные данные распределены случайно, то следует говорить о минимальном, максимальном и среднем числе сравнений и перестановок.

Слайд 174Информатика. Тема 6. Численные методы решения задач.
Сравнение алгоритмов сортировки



Слайд 175Информатика. Тема 6. Численные методы решения задач.
Сравнение алгоритмов сортировки



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

Вступ до С. Перша проста програма 214
Мифы связанные с программированием 326
Организация службы документационного обеспечения управления на примере ООО СОЮЗ 347
Два подхода к измерению информации. (8 класс) 461
Работа со съемными носителями. (Тема 3) 274
Сортировка и подведения итогов в списке. Фильтрация списка 293

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

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

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

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

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

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

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