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

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

Информатика. Тема 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.

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

Информатика. Тема 6. Численные методы решения задач.
6.1.1. Сортировка подсчетом
При сортировке подсчетом используется вспомогательный массив
C(1), C(2),…, C(N), элементы которого изначально равны нулю.
Все ключи попарно сравниваются.
Если ключ Ki больше Kj, то элемент C(i) увеличивается на единицу.
В противном случае на единицу увеличивается элемент C(j).
После завершения сравнений величина C(j) + 1 определяет окончательное положение записи Rj.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Информатика. Тема 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Информатика. Тема 6. Численные методы решения задач.
6.1.3. Сортировка выбором
При сортировке записей R1, R2,…, RN
1) Находится запись Rj, имеющая наибольший ключ Kj.
2) Происходит обмен записей Rj и RN.
3) Процедура поиска наибольшего ключа повторяется для записей R1, R2,…, RN-1. Подобная процедура повторяется (N-1) раз.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Информатика. Тема 6. Численные методы решения задач.
6.1.4. Сортировка обменом
Простейший обменный алгоритм называется «пузырек».
При сортировке записей R1, R2,…, RN алгоритмом «пузырек»
1) Сравниваются ключи двух соседних записей Rj и Rj-1.
2) Если ключ Kj меньше ключа Kj-1 записи Rj и Rj-1 обмениваются.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Информатика. Тема 6. Численные методы решения задач.
6.1.5. Сортировка методом Шелла
При сортировке «пузырьком» сравниваются ключи соседних записей (шаг сортировки равен единице).
Быстродействие можно повысить, применяя сортировку с убывающим шагом.
Дональд Шелл – американский ученый в области информатики

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

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 4)
Число сравнений – 11, число обменов – 3.

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 4)
Число сравнений – 14, число обменов – 3.

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

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

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 2)
Число сравнений – 30, число обменов – 7.

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 2)
Число сравнений – 37, число обменов – 8.

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 1)
Число сравнений – 38, число обменов – 9.

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 1)
Число сравнений – 39, число обменов – 9.

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

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 1)
Число сравнений – 43, число обменов – 11.

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 1)
Число сравнений – 46, число обменов – 13.

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 1)
Число сравнений – 47, число обменов – 13.

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 1)
Число сравнений – 51, число обменов – 16.

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 1)
Число сравнений – 52, число обменов – 16.

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 1)
Число сравнений – 57, число обменов – 20.

Информатика. Тема 6. Численные методы решения задач.
Сортировка методом Шелла (шаг сортировки равен 1)
Число сравнений – 58, число обменов – 20.

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

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

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

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

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

Информатика. Тема 6. Численные методы решения задач.
6.1.6. «Быстрая» сортировка
В 1962 году Ч.Э.Р. Хоар предложил обменную сортировку с разделением, которую назвал quicksort (быстрая сортировка).
Чарльз Энтони Ричард Хоар – английский ученый в области информатики

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Информатика. Тема 6. Численные методы решения задач.
6.1.7. Сравнение алгоритмов сортировки
Эффективность алгоритма сортировки характеризуется несколькими параметрами:
Время сортировки
Память
Устойчивость
Естественность поведения
Время работы алгоритма сортировки зависит от количества сравнений ключей и количества перестановок записей.
Поскольку исходные данные распределены случайно, то следует говорить о минимальном, максимальном и среднем числе сравнений и перестановок.

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