Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
28 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
244.59 kB
Просмотров:
44
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![ПРОГРАММИРОВАНИЕ Семинар .](/documents_6/fdb05dedd9be1de6852781013052b5b7/img0.jpg)
Содержание слайда: ПРОГРАММИРОВАНИЕ
Семинар 4.
Сортировки
№2 слайд![Сортировка Процесс](/documents_6/fdb05dedd9be1de6852781013052b5b7/img1.jpg)
Содержание слайда: Сортировка
Процесс перестановки объектов заданной совокупности в определённом порядке (возрастающем или убывающем).
№3 слайд![Цель сортировки Облегчение](/documents_6/fdb05dedd9be1de6852781013052b5b7/img2.jpg)
Содержание слайда: Цель сортировки
Облегчение последующего поиска элементов в отсортированном множестве (например, возможность применения бинарного поиска).
№4 слайд![Виды сортировки внутренняя](/documents_6/fdb05dedd9be1de6852781013052b5b7/img3.jpg)
Содержание слайда: Виды сортировки
внутренняя (массивы);
внешняя (файлы).
№5 слайд![Задача сортировки Упорядочить](/documents_6/fdb05dedd9be1de6852781013052b5b7/img4.jpg)
Содержание слайда: Задача сортировки
Упорядочить N объектов a1, a2, …, aN,
т. е. переставить их в такой последовательности ap1, ap2, …, apN, чтобы их ключи расположились в неубывающем порядке kp1≤ kp2≤ … ≤ kpN.
№6 слайд![Свойство устойчивости](/documents_6/fdb05dedd9be1de6852781013052b5b7/img5.jpg)
Содержание слайда: Свойство устойчивости
Сортировка называется устойчивой, если записи с одинаковыми ключами остаются в прежнем порядке:
kpi = kpj & i < j ⇒ pi < pj.
При устойчивой сортировке относительный порядок элементов не меняется.
№7 слайд![Сортировка массивов](/documents_6/fdb05dedd9be1de6852781013052b5b7/img6.jpg)
Содержание слайда: Сортировка массивов
Требование: экономное использование памяти, т. е. не используются дополнительные массивы, а перестановка элементов производится внутри сортируемого массива.
Меры эффективности:
количество сравнения ключей C(N);
количество перестановок M(N).
№8 слайд![Методы сортировки массивов](/documents_6/fdb05dedd9be1de6852781013052b5b7/img7.jpg)
Содержание слайда: Методы сортировки массивов
включение;
выбор;
обмен;
подсчёт;
разделение;
слияние.
№9 слайд![Сортировка простыми вставками](/documents_6/fdb05dedd9be1de6852781013052b5b7/img8.jpg)
Содержание слайда: Сортировка простыми вставками
Пусть ai, ai + 1, …, aN — неотсортированная последовательность (входная),
a1, a2, …, ai - 1 — отсортированная (готовая).
На каждом i-м шаге i-ый элемент входной последовательности вставляется в подходящее место готовой.
№10 слайд![Алгоритм Условно разделить](/documents_6/fdb05dedd9be1de6852781013052b5b7/img9.jpg)
Содержание слайда: Алгоритм
Условно разделить массив 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 слайд![Пример](/documents_6/fdb05dedd9be1de6852781013052b5b7/img10.jpg)
Содержание слайда: Пример
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 -](/documents_6/fdb05dedd9be1de6852781013052b5b7/img11.jpg)
Содержание слайда: Анализ алгоритма
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 слайд![Анализ алгоритма Наилучшие](/documents_6/fdb05dedd9be1de6852781013052b5b7/img12.jpg)
Содержание слайда: Анализ алгоритма
Наилучшие оценки — уже упорядоченный массив,
наихудшие — обратный порядок.
Сортировка устойчива.
№14 слайд![Сортировка бинарными](/documents_6/fdb05dedd9be1de6852781013052b5b7/img13.jpg)
Содержание слайда: Сортировка бинарными включениями
При поиске подходящего места вставки в методе простой вставки использовать метод бинарного поиска
C(i) ≈ log2N
C(N) ≈ N log2N
M(N) не изменится
№15 слайд![Сортировка простым выбором](/documents_6/fdb05dedd9be1de6852781013052b5b7/img14.jpg)
Содержание слайда: Сортировка простым выбором
Идея многократного выбора.
На каждом i-м шаге выбирается наименьший элемент входной последовательности и меняется местами с аi. Далее перемещаем его в готовую последовательность.
Процесс продолжаем до тех пор, пока во входной последовательности не останется один элемент.
№16 слайд![Алгоритм Условно разделить](/documents_6/fdb05dedd9be1de6852781013052b5b7/img15.jpg)
Содержание слайда: Алгоритм
Условно разделить массив 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 слайд![Пример](/documents_6/fdb05dedd9be1de6852781013052b5b7/img16.jpg)
Содержание слайда: Пример
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 не](/documents_6/fdb05dedd9be1de6852781013052b5b7/img17.jpg)
Содержание слайда: Анализ алгоритма
C(i) не зависит от начального порядка элементов.
C(N) = N - 1 + N -2 + … + 1 = N (N - 1) / 2
Mmax = N - 1
№19 слайд![Сортировка простым обменом](/documents_6/fdb05dedd9be1de6852781013052b5b7/img18.jpg)
Содержание слайда: Сортировка простым обменом (метод пузырька)
Идея — сравнение и обмен соседних элементов, начиная с конца массива.
На каждом i-м шаге сравниваем i-ый и (i - 1)-ый элементы, меняя их местами, если они не упорядочены.
Повторяем процесс, начиная с конца до 2-го элемента и т. д.
№20 слайд![Алгоритм Цикл по i от до N -](/documents_6/fdb05dedd9be1de6852781013052b5b7/img19.jpg)
Содержание слайда: Алгоритм
Цикл по i от 1 до N - 1 с шагом 1
Цикл по j от N - 1 до i с шагом 1
если A[j] < A[j - 1], то обменять A[j] с A[j - 1].
Конец цикла
Конец цикла
№21 слайд![Пример](/documents_6/fdb05dedd9be1de6852781013052b5b7/img20.jpg)
Содержание слайда: Пример
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](/documents_6/fdb05dedd9be1de6852781013052b5b7/img21.jpg)
Содержание слайда: Анализ алгоритма
C(i) = N - i
C(N) = N - 1 + N - 2 + … + 1 = N (N - 1) / 2
Mmin = 0
Mmax = C(N) — обратно упорядоченный массив.
№23 слайд![Сортировка с разделением](/documents_6/fdb05dedd9be1de6852781013052b5b7/img22.jpg)
Содержание слайда: Сортировка с разделением (быстрая сортировка)
№24 слайд![Сортировка с разделением](/documents_6/fdb05dedd9be1de6852781013052b5b7/img23.jpg)
Содержание слайда: Сортировка с разделением (быстрая сортировка)
Идея — обмен несоседних элементов и сведение к сортировки меньших частей.
На каждом i-м шаге существует индекс m, такой что:
∀i, j 0 ≤ i ≤ m & m < j < N - 1 ai ≤ aj.
Назовём m медианой. Далее сортируем отдельно левую и правую части любым методом обмена.
№25 слайд![Алгоритм Процедура](/documents_6/fdb05dedd9be1de6852781013052b5b7/img24.jpg)
Содержание слайда: Алгоритм
Процедура СортировкаРазделением(l, r)
Привести последовательность al, …, ar к условию выше и определить медиану m;
Части длины 0 или 1 не сортируем;
Если l < m, то СортировкаРазделением(l, m);
Если m + 1 < r, то СортировкаРазделением(m + 1, r);
Конец процедуры
№26 слайд![Алгоритм Процесс разделения](/documents_6/fdb05dedd9be1de6852781013052b5b7/img25.jpg)
Содержание слайда: Алгоритм
Процесс разделения:
Пока 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 слайд![Пример](/documents_6/fdb05dedd9be1de6852781013052b5b7/img26.jpg)
Содержание слайда: Пример
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 слайд![Сортировка подсчётом](/documents_6/fdb05dedd9be1de6852781013052b5b7/img27.jpg)
Содержание слайда: Сортировка подсчётом
Заводится дополнительный массив B: B[j] содержит количество вхождений числа j в A.