🗊Презентация Сортировки. Программирование. Семинар 4

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Сортировки. Программирование. Семинар 4, слайд №1Сортировки. Программирование. Семинар 4, слайд №2Сортировки. Программирование. Семинар 4, слайд №3Сортировки. Программирование. Семинар 4, слайд №4Сортировки. Программирование. Семинар 4, слайд №5Сортировки. Программирование. Семинар 4, слайд №6Сортировки. Программирование. Семинар 4, слайд №7Сортировки. Программирование. Семинар 4, слайд №8Сортировки. Программирование. Семинар 4, слайд №9Сортировки. Программирование. Семинар 4, слайд №10Сортировки. Программирование. Семинар 4, слайд №11Сортировки. Программирование. Семинар 4, слайд №12Сортировки. Программирование. Семинар 4, слайд №13Сортировки. Программирование. Семинар 4, слайд №14Сортировки. Программирование. Семинар 4, слайд №15Сортировки. Программирование. Семинар 4, слайд №16Сортировки. Программирование. Семинар 4, слайд №17Сортировки. Программирование. Семинар 4, слайд №18Сортировки. Программирование. Семинар 4, слайд №19Сортировки. Программирование. Семинар 4, слайд №20Сортировки. Программирование. Семинар 4, слайд №21Сортировки. Программирование. Семинар 4, слайд №22Сортировки. Программирование. Семинар 4, слайд №23Сортировки. Программирование. Семинар 4, слайд №24Сортировки. Программирование. Семинар 4, слайд №25Сортировки. Программирование. Семинар 4, слайд №26Сортировки. Программирование. Семинар 4, слайд №27Сортировки. Программирование. Семинар 4, слайд №28
Скачать

Содержание ▲

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

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

Слайд 1


ПРОГРАММИРОВАНИЕ Семинар 4. Сортировки
Описание слайда:
ПРОГРАММИРОВАНИЕ Семинар 4. Сортировки

Слайд 2


Сортировка Процесс перестановки объектов заданной совокупности в определённом порядке (возрастающем или убывающем).
Описание слайда:
Сортировка Процесс перестановки объектов заданной совокупности в определённом порядке (возрастающем или убывающем).

Слайд 3


Цель сортировки Облегчение последующего поиска элементов в отсортированном множестве (например, возможность применения бинарного поиска).
Описание слайда:
Цель сортировки Облегчение последующего поиска элементов в отсортированном множестве (например, возможность применения бинарного поиска).

Слайд 4


Виды сортировки внутренняя (массивы); внешняя (файлы).
Описание слайда:
Виды сортировки внутренняя (массивы); внешняя (файлы).

Слайд 5


Задача сортировки Упорядочить N объектов a1, a2, …, aN, т. е. переставить их в такой последовательности ap1, ap2, …, apN, чтобы их ключи расположились в неубывающем порядке kp1≤ kp2≤ … ≤ kpN.
Описание слайда:
Задача сортировки Упорядочить N объектов a1, a2, …, aN, т. е. переставить их в такой последовательности ap1, ap2, …, apN, чтобы их ключи расположились в неубывающем порядке kp1≤ kp2≤ … ≤ kpN.

Слайд 6


Свойство устойчивости Сортировка называется устойчивой, если записи с одинаковыми ключами остаются в прежнем порядке: kpi = kpj & i < j ⇒ pi < pj. При устойчивой сортировке относительный порядок элементов не меняется.
Описание слайда:
Свойство устойчивости Сортировка называется устойчивой, если записи с одинаковыми ключами остаются в прежнем порядке: kpi = kpj & i < j ⇒ pi < pj. При устойчивой сортировке относительный порядок элементов не меняется.

Слайд 7


Сортировка массивов Требование: экономное использование памяти, т. е. не используются дополнительные массивы, а перестановка элементов производится внутри сортируемого массива. Меры эффективности: количество сравнения ключей C(N); количество перестановок M(N).
Описание слайда:
Сортировка массивов Требование: экономное использование памяти, т. е. не используются дополнительные массивы, а перестановка элементов производится внутри сортируемого массива. Меры эффективности: количество сравнения ключей C(N); количество перестановок M(N).

Слайд 8


Методы сортировки массивов включение; выбор; обмен; подсчёт; разделение; слияние.
Описание слайда:
Методы сортировки массивов включение; выбор; обмен; подсчёт; разделение; слияние.

Слайд 9


Сортировка простыми вставками Пусть ai, ai + 1, …, aN — неотсортированная последовательность (входная), a1, a2, …, ai - 1 — отсортированная (готовая). На каждом i-м шаге i-ый элемент входной последовательности вставляется в подходящее место готовой.
Описание слайда:
Сортировка простыми вставками Пусть ai, ai + 1, …, aN — неотсортированная последовательность (входная), a1, a2, …, ai - 1 — отсортированная (готовая). На каждом i-м шаге i-ый элемент входной последовательности вставляется в подходящее место готовой.

Слайд 10


Алгоритм Условно разделить массив A на входную и готовую части. К входной части сначала относится только A[0]. Цикл по i от 1 до N - 1 с шагом 1 x = A[i]; j = i - 1; Пока j ≥ 0 и A[j] > x выполнять A[j + 1] = A[j]; j = j - 1; Конец Пока A[j + 1] = x; Конец цикла
Описание слайда:
Алгоритм Условно разделить массив A на входную и готовую части. К входной части сначала относится только A[0]. Цикл по i от 1 до N - 1 с шагом 1 x = A[i]; j = i - 1; Пока j ≥ 0 и A[j] > x выполнять A[j + 1] = A[j]; j = j - 1; Конец Пока A[j + 1] = x; Конец цикла

Слайд 11


Пример 38 90 5 10 17 3 9 1 38 90 5 10 17 3 9 1 5 38 90 10 17 3 9 1 5 10 38 90 17 3 9 1 5 10 17 38 90 3 9 1 3 5 10 17 38 90 9 1 3 5 9 10 17 38 90 1 1 3 5 9 10 17 38 90
Описание слайда:
Пример 38 90 5 10 17 3 9 1 38 90 5 10 17 3 9 1 5 38 90 10 17 3 9 1 5 10 38 90 17 3 9 1 5 10 17 38 90 3 9 1 3 5 10 17 38 90 9 1 3 5 9 10 17 38 90 1 1 3 5 9 10 17 38 90

Слайд 12


Анализ алгоритма max(C(i)) = i - 1 Если перестановки равновероятны, то в среднем C(i) = i / 2. max(M(i)) = C(i) + 2 Cmax = 1 + 2 + … + N - 1 = N (N - 1) / 2 Cmin = N - 1 Mmin = 2 (N - 1) Mmax = N (N - 1) / 2 + 2 (N - 1) ≈ N (N + 3) / 2
Описание слайда:
Анализ алгоритма max(C(i)) = i - 1 Если перестановки равновероятны, то в среднем C(i) = i / 2. max(M(i)) = C(i) + 2 Cmax = 1 + 2 + … + N - 1 = N (N - 1) / 2 Cmin = N - 1 Mmin = 2 (N - 1) Mmax = N (N - 1) / 2 + 2 (N - 1) ≈ N (N + 3) / 2

Слайд 13


Анализ алгоритма Наилучшие оценки — уже упорядоченный массив, наихудшие — обратный порядок. Сортировка устойчива.
Описание слайда:
Анализ алгоритма Наилучшие оценки — уже упорядоченный массив, наихудшие — обратный порядок. Сортировка устойчива.

Слайд 14


Сортировка бинарными включениями При поиске подходящего места вставки в методе простой вставки использовать метод бинарного поиска C(i) ≈ log2N C(N) ≈ N log2N M(N) не изменится
Описание слайда:
Сортировка бинарными включениями При поиске подходящего места вставки в методе простой вставки использовать метод бинарного поиска C(i) ≈ log2N C(N) ≈ N log2N M(N) не изменится

Слайд 15


Сортировка простым выбором Идея многократного выбора. На каждом i-м шаге выбирается наименьший элемент входной последовательности и меняется местами с аi. Далее перемещаем его в готовую последовательность. Процесс продолжаем до тех пор, пока во входной последовательности не останется один элемент.
Описание слайда:
Сортировка простым выбором Идея многократного выбора. На каждом i-м шаге выбирается наименьший элемент входной последовательности и меняется местами с аi. Далее перемещаем его в готовую последовательность. Процесс продолжаем до тех пор, пока во входной последовательности не останется один элемент.

Слайд 16


Алгоритм Условно разделить массив A на входную и готовую части. Сначала весь массив — входная часть. Цикл по i от 0 до N - 2 с шагом 1 r = i; Цикл по j от i + 1 до N - 1 с шагом 1 если A[j] < A[r], то r = j и выйти из цикла; Конец цикла если i ≠ r, то обменять A[i] с A[r]. Конец цикла
Описание слайда:
Алгоритм Условно разделить массив A на входную и готовую части. Сначала весь массив — входная часть. Цикл по i от 0 до N - 2 с шагом 1 r = i; Цикл по j от i + 1 до N - 1 с шагом 1 если A[j] < A[r], то r = j и выйти из цикла; Конец цикла если i ≠ r, то обменять A[i] с A[r]. Конец цикла

Слайд 17


Пример 38 90 5 10 17 3 9 1 1 38 90 5 10 17 3 9 1 3 38 90 5 10 17 9 1 3 5 38 90 10 17 9 1 3 5 9 38 90 10 17 1 3 5 9 10 38 90 17 1 3 5 9 10 17 38 90 1 3 5 9 10 17 38 90
Описание слайда:
Пример 38 90 5 10 17 3 9 1 1 38 90 5 10 17 3 9 1 3 38 90 5 10 17 9 1 3 5 38 90 10 17 9 1 3 5 9 38 90 10 17 1 3 5 9 10 38 90 17 1 3 5 9 10 17 38 90 1 3 5 9 10 17 38 90

Слайд 18


Анализ алгоритма C(i) не зависит от начального порядка элементов. C(N) = N - 1 + N -2 + … + 1 = N (N - 1) / 2 Mmax = N - 1
Описание слайда:
Анализ алгоритма C(i) не зависит от начального порядка элементов. C(N) = N - 1 + N -2 + … + 1 = N (N - 1) / 2 Mmax = N - 1

Слайд 19


Сортировка простым обменом (метод пузырька) Идея — сравнение и обмен соседних элементов, начиная с конца массива. На каждом i-м шаге сравниваем i-ый и (i - 1)-ый элементы, меняя их местами, если они не упорядочены. Повторяем процесс, начиная с конца до 2-го элемента и т. д.
Описание слайда:
Сортировка простым обменом (метод пузырька) Идея — сравнение и обмен соседних элементов, начиная с конца массива. На каждом i-м шаге сравниваем i-ый и (i - 1)-ый элементы, меняя их местами, если они не упорядочены. Повторяем процесс, начиная с конца до 2-го элемента и т. д.

Слайд 20


Алгоритм Цикл по i от 1 до N - 1 с шагом 1 Цикл по j от N - 1 до i с шагом 1 если A[j] < A[j - 1], то обменять A[j] с A[j - 1]. Конец цикла Конец цикла
Описание слайда:
Алгоритм Цикл по i от 1 до N - 1 с шагом 1 Цикл по j от N - 1 до i с шагом 1 если A[j] < A[j - 1], то обменять A[j] с A[j - 1]. Конец цикла Конец цикла

Слайд 21


Пример 38 90 5 10 17 3 9 1 38 90 5 10 17 3 1 9 38 90 5 10 17 1 3 9 38 90 5 10 1 17 3 9 38 90 5 1 10 17 3 9 38 90 1 5 10 17 3 9 38 1 90 5 10 17 3 9 1 38 90 5 10 17 3 9 1 38 90 5 10 17 3 9 1 38 90 5 10 3 17 9 1 38 90 5 3 10 17 9 1 38 90 3 5 10 17 9 1 38 3 90 5 10 17 9 1 3 38 90 5 10 17 9 1 3 38 90 5 10 9 17 1 3 38 90 5 9 10 17 1 3 38 90 5 9 10 17 1 3 38 5 90 9 10 17 1 3 5 38 90 9 10 17 1 3 5 38 90 9 10 17 1 3 5 38 90 9 10 17 1 3 5 38 9 90 10 17 1 3 5 9 38 90 10 17 1 3 5 9 38 90 10 17 1 3 5 9 38 10 90 17 1 3 5 9 10 38 90 17 1 3 5 9 10 38 17 90 1 3 5 9 10 17 38 90 1 3 5 9 10 17 38 90
Описание слайда:
Пример 38 90 5 10 17 3 9 1 38 90 5 10 17 3 1 9 38 90 5 10 17 1 3 9 38 90 5 10 1 17 3 9 38 90 5 1 10 17 3 9 38 90 1 5 10 17 3 9 38 1 90 5 10 17 3 9 1 38 90 5 10 17 3 9 1 38 90 5 10 17 3 9 1 38 90 5 10 3 17 9 1 38 90 5 3 10 17 9 1 38 90 3 5 10 17 9 1 38 3 90 5 10 17 9 1 3 38 90 5 10 17 9 1 3 38 90 5 10 9 17 1 3 38 90 5 9 10 17 1 3 38 90 5 9 10 17 1 3 38 5 90 9 10 17 1 3 5 38 90 9 10 17 1 3 5 38 90 9 10 17 1 3 5 38 90 9 10 17 1 3 5 38 9 90 10 17 1 3 5 9 38 90 10 17 1 3 5 9 38 90 10 17 1 3 5 9 38 10 90 17 1 3 5 9 10 38 90 17 1 3 5 9 10 38 17 90 1 3 5 9 10 17 38 90 1 3 5 9 10 17 38 90

Слайд 22


Анализ алгоритма C(i) = N - i C(N) = N - 1 + N - 2 + … + 1 = N (N - 1) / 2 Mmin = 0 Mmax = C(N) — обратно упорядоченный массив.
Описание слайда:
Анализ алгоритма C(i) = N - i C(N) = N - 1 + N - 2 + … + 1 = N (N - 1) / 2 Mmin = 0 Mmax = C(N) — обратно упорядоченный массив.

Слайд 23


Сортировка с разделением (быстрая сортировка)
Описание слайда:
Сортировка с разделением (быстрая сортировка)

Слайд 24


Сортировка с разделением (быстрая сортировка) Идея — обмен несоседних элементов и сведение к сортировки меньших частей. На каждом i-м шаге существует индекс m, такой что: ∀i, j 0 ≤ i ≤ m & m < j < N - 1 ai ≤ aj. Назовём m медианой. Далее сортируем отдельно левую и правую части любым методом обмена.
Описание слайда:
Сортировка с разделением (быстрая сортировка) Идея — обмен несоседних элементов и сведение к сортировки меньших частей. На каждом i-м шаге существует индекс m, такой что: ∀i, j 0 ≤ i ≤ m & m < j < N - 1 ai ≤ aj. Назовём m медианой. Далее сортируем отдельно левую и правую части любым методом обмена.

Слайд 25


Алгоритм Процедура СортировкаРазделением(l, r) Привести последовательность al, …, ar к условию выше и определить медиану m; Части длины 0 или 1 не сортируем; Если l < m, то СортировкаРазделением(l, m); Если m + 1 < r, то СортировкаРазделением(m + 1, r); Конец процедуры
Описание слайда:
Алгоритм Процедура СортировкаРазделением(l, r) Привести последовательность al, …, ar к условию выше и определить медиану m; Части длины 0 или 1 не сортируем; Если l < m, то СортировкаРазделением(l, m); Если m + 1 < r, то СортировкаРазделением(m + 1, r); Конец процедуры

Слайд 26


Алгоритм Процесс разделения: Пока i < j i = l; j = r; Пока ai < x i = i + 1; Пока x < aj j = j - 1; Если i < j, то обменять ai с aj; i = i + 1; j = j - 1; Конец пока
Описание слайда:
Алгоритм Процесс разделения: Пока i < j i = l; j = r; Пока ai < x i = i + 1; Пока x < aj j = j - 1; Если i < j, то обменять ai с aj; i = i + 1; j = j - 1; Конец пока

Слайд 27


Пример 38 90 5 10 17 3 9 1 1 90 5 10 17 3 9 38 1 9 5 10 17 3 90 38 1 9 5 3 10 17 90 38 1 9 5 3 10 17 90 38
Описание слайда:
Пример 38 90 5 10 17 3 9 1 1 90 5 10 17 3 9 38 1 9 5 10 17 3 90 38 1 9 5 3 10 17 90 38 1 9 5 3 10 17 90 38

Слайд 28


Сортировка подсчётом Заводится дополнительный массив B: B[j] содержит количество вхождений числа j в A.
Описание слайда:
Сортировка подсчётом Заводится дополнительный массив B: B[j] содержит количество вхождений числа j в A.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию