Метод прямого выбора SelectSort - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Метод прямого выбора SelectSort, слайд №1

Метод прямого выбора SelectSort, слайд №2

Метод прямого выбора SelectSort, слайд №3

Метод прямого выбора SelectSort, слайд №4

Метод прямого выбора SelectSort, слайд №5

Метод прямого выбора SelectSort, слайд №6

Метод прямого выбора SelectSort, слайд №7

Метод прямого выбора SelectSort, слайд №8

Метод прямого выбора SelectSort, слайд №9

Метод прямого выбора SelectSort, слайд №10

Метод прямого выбора SelectSort, слайд №11

Метод прямого выбора SelectSort, слайд №12

Метод прямого выбора SelectSort, слайд №13

Метод прямого выбора SelectSort, слайд №14

Метод прямого выбора SelectSort, слайд №15

Метод прямого выбора SelectSort, слайд №16

Метод прямого выбора SelectSort, слайд №17

Метод прямого выбора SelectSort, слайд №18

Метод прямого выбора SelectSort, слайд №19

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Метод прямого выбора SelectSort. Доклад-сообщение содержит 19 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

Описание слайда:

Список литературы 1. Н.Вирт. «Алгоритмы и структуры данных», 1989. 2. Д.Кнут. «Искусство программирования для ЭВМ», том 1 и 3, 1976-78. 3. Т.Кормен, Ч.Лейзерсон, Р.Ривест. «Алгоритмы: построение и анализ», 2001,2004,2009,2011. 4. Р.Седжвик. «Фундаментальные алгоритмы на С++», 2002. 5. Е.В.Курапова, Е.П.Мачикина. «Структуры и алгоритмы обработки данных», 2006. 6. Е.В.Курапова, Е.П.Мачикина. «Основные методы кодирования данных», 2010.

Слайд 2

Описание слайда:

Никлаус Вирт День рождения 15 февраля 1934 Швейцарский учёный, специалист в области информатики, известный теоретик в области разработки языков программирования, профессор компьютерных наук. Участвовал в разработке языков ALGOL68 и PL/360 Разработал языки Паскаль и Модула-2 8,

Слайд 3

Описание слайда:

Дональд Кнут День рождения 10 января 1938 Американский учёный, почётный профессор университетов в разных странах, иностранный член Российской академии наук, преподаватель и идеолог программирования, автор 19 монографий.

Слайд 4

Описание слайда:

Метод прямого выбора SelectSort Находим наименьший элемент массива и переставляем его на первое место. Среди оставшихся элементов (начиная со второго) находим наименьший элемент и переставляем его на второе место в массиве. Среди оставшихся элементов (начиная с третьего) находим наименьший элемент и переставляем его на третье место и т. д. сколько раз???

Слайд 5

Описание слайда:

Метод прямого выбора Алгоритм на псевдокоде DO ( i := 1, 2, ... n-1) k := i DO ( j := i+1, i+2,… ,n ) IF ( aj < ak ) k := j FI OD ai ak OD

Слайд 6

Описание слайда:

К У Р А П О В А К У Р А П О В А А У Р К П О В А А А Р К П О В У А А В К П О Р У А А В К П О Р У А А В К О П Р У А А В К О П Р У А А В К О П Р У

Слайд 7

Описание слайда:

Дадим оценку трудоёмкости метода прямого выбора, т.е. определим количество пересылок и сравнений. Дадим оценку трудоёмкости метода прямого выбора, т.е. определим количество пересылок и сравнений. 1) По количеству пересылок: на каждой итерации старшего цикла выполняется один обмен (3 пересылки). M = 3(n-1) 2) По количеству сравнений можем сказать: когда i=1 требуется (n-1) сравнение, когда i=2 требуется (n-2) сравнения, и т.д. Суммируя, получим: С = (n-1) + (n-2) + (n-3) + … + 1 С = 1 + 2 + 3 + … + (n-1) 2С = n + n + n + … + n 2С = n (n-1) C =

Слайд 8

Описание слайда:

При подсчете трудоемкости учитываются только те операции, в которых участвуют элементы массива. При подсчете трудоемкости учитываются только те операции, в которых участвуют элементы массива. Для удобства реализации алгоритмов на Си массив можно описывать следующим образом: int A [ 1+n ]; Тогда при заполнении и выводе массива элемент А[0] не используется. Для метода прямого выбора SelectSort: Значения М и С не зависят от исходной упорядоченности массива. Сортировка не устойчива. Пример: 3’ 3” 2 -> 2 3” 3’

Слайд 9

Описание слайда:

Видео SelectSort

Слайд 10

Описание слайда:

Классы сложности алгоритмов Часто бывает трудно определить точное время работы алгоритма, тогда пользуются асимптотической или приближенной оценкой времени работы. Асимптотическое доминирование функций. Определение. Функция f(x) асимптотически доминирует над функцией g(x) или g(x) = O ( f(x) ), если |g(x)| ≤ const |f(x)| при x→∞. Примеры: 1) g(x) = 10х f(x) = х 2) g(x) = 1 f(x) = x 3) g(x) = 2х f(x) = х2

Слайд 11

Описание слайда:

Свойства асимптотического доминирования функций Для функций f , f1 , f2 и константы k справедливы свойства: f = O(f) O (k*f) = O (f) O (f1+f2) = O (f1) +O (f2) Пример: T = 10n + 20 T = O(10n+20) = O(10n) + O(20) = O(n) +O(1) = O(n), при n→ ∞. Приведем ряд доминирования основных функций O(1) < O(log n) < O(n) < O(n log n) < O(na) < O(an) < < O(n!) < O(nn) , при n→∞, a >1.

Слайд 12

Описание слайда:

Трудоемкость SelectSort M = 3(n-1) С = Т = С + М = О(Т) = О(С+М) = О( + 3(n-1)) = = O() - O() + O(3n) - O(3) = = O(n2) - O(n) + O(n) - O(1) = O(n2) , n→∞ T = O(n2) , n→∞

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Пузырьковая сортировка BubbleSort Двигаясь от конца массива к его началу, будем сравнивать между собой соседние элементы. Если правый элемент будет меньше, чем левый, то поменяем их местами. При первом проходе наименьший элемент переместится на первое место. При втором проходе наименьший элемент из оставшихся “всплывёт” на второе место, и т.д. Через (n-1) итерацию массив будет отсортирован.

Слайд 15

Описание слайда:

Пузырьковая сортировка Алгоритм на псевдокоде Обозначим i – номер итерации, j – индекс правого элемента в текущей паре. DO (i := 1, 2, ... n-1) DO (j := n, n-1, ... i+1) IF (aj < aj-1) aj↔aj-1 FI OD OD

Слайд 16

Описание слайда:

К У Р А П О В А К У Р А П О В А А В А О А П А А А Р А У А К А К У Р А П О В В О В П А В А Р А У А К

Слайд 17

Описание слайда:

А А В К О П У Р А А В К О П У Р Р У П Р А А В К О П Р У Р У А А В К О П Р У А А В К О П Р У

Слайд 18

Описание слайда:

Если сравнить BubbleSort с алгоритмом SelectSort, то по количеству сравнений эти методы идентичны. Если сравнить BubbleSort с алгоритмом SelectSort, то по количеству сравнений эти методы идентичны. С = Количество пересылок М зависит от исходной упорядоченности массива. Рассмотрим случаи: 1) Массив упорядочен -> пересылок не будет (Mmin = 0) 2) Массив обратно упорядочен -> максимальное количество пересылок (Mmах = 3С) 3) Массив случайный Мср = = Метод зависит от исходной упорядоченности по количеству пересылок. Пузырьковая сортировка устойчива.