Сортировка посредством выбора

Август 7, 2022

Главная
Информатика
Сортировка посредством выбора

Содержание

2. Сортировка вставками
3. Сортировка вставками А = 50, 20, 40, 75, 35 O(n2)
4. Сортировка слиянием (продолжение)
5. Сортировка слиянием (продолжение) A[p..q] A[q+1..r] A[p..r] n1= q-p+1 A[p..q] n2=r-q A[q+1..r] Массив B – n1 Массив
6. Сортировка слиянием (продолжение) Процедура Merge(A, p, q, r) Вход: А: массив p, q, r: индексы в
7. Слияние сортированных последовательностей
9. Быстрая сортировка Быстрая сортировка работает «на месте», без привлечения дополнительной памяти. Асимптотическое время работы быстрой сортировки
10. Быстрая сортировка Парадигма « разделяй и властвуй». Этап разделения: «опорная» книга – индекс 15
11. Быстрая сортировка Разделение. Сначала выберем одну книгу из слотов от p до r. Назовем эту книгу
12. Быстрая сортировка Процедура быстрой сортировки подразумевает вызов процедуры Partition (A, p, r), которая разбивает подмассив A[p..r]
13. Быстрая сортировка Первоначальный вызов Quicksort(A, 1, r) аналогичен вызову процедуры Merge-Sort. Пример работы процедуры Quicksort с
14. Быстрая сортировка Вызов процедуры Partition Процедура разбиения книг на полке в слотах с p по r.
15. Быстрая сортировка Вызов процедуры Partition ( A, 9,15)
16. Быстрая сортировка Вызов процедуры Partition ( A, 9,15), продолжение.
17. Быстрая сортировка Вызов процедуры Partition ( A, 9,15), описание Если автор книги находится в алфавитном порядке
18. Быстрая сортировка Вызов процедуры Partition ( A, 9,15), результат.
19. Быстрая сортировка Чтобы преобразовать разбиение книг на полке в разбиение подмассива A[p..r], мы сначала выбираем крайний
20. Быстрая сортировка Процедура Partition(A, p, r) Вход: тот же, что и для процедуры Merge-Sort. Результат: перестановка
21. Быстрая сортировка Процедура Partition(A, p, r): перестановка элементов A[p..r], такая, что каждый элемент в A[p..q-1] не
23. Скачать презентацию

Слайд 2

Сортировка вставками

Слайд 3

Сортировка вставками
А = 50, 20, 40, 75, 35
O(n2)

Слайд 4

Сортировка слиянием (продолжение)

Слайд 5

Сортировка слиянием (продолжение)
A[p..q] A[q+1..r] A[p..r]
n1= q-p+1 A[p..q]
n2=r-q A[q+1..r]
Массив B

– n1
Массив С –n2
A[p..q] B
A[q+1..r] C

Слайд 6

Сортировка слиянием (продолжение)
Процедура Merge(A, p, q, r)
Вход:
А: массив
p, q, r: индексы

в массиве А. Подмассивы А[p..q] и A[q+1..r] считаются уже отсортированными.
Результат: подмассив А[p.. r], содержащий все элементы, находившиеся в подмассивах А[p..q] и A[q+1..r], но теперь подмассив А[p.. r] отсортирован.
Установить n1 равным q-p+1, n2 – равным r-q.
B[1.. n1+1] и C[1.. n2+1] представляют собой новые массивы.
Скопировать А[p..q] в B[1.. n1] , а A[q+1..r] - в C[1.. n2].
Установить B[n1+1] и C[n2+1] равными «бесконечности».
Установить i и j равными 1.
Для k = p до r
Если B[i] <= C[j], установить A[k] равным B[i] и увеличить i на 1.
В противном случае (B[i]> C [j]) установить A[k] равным C[j] и увеличить j на 1.

Слайд 7

Слияние сортированных последовательностей

Слайд 8

Слайд 9

Быстрая сортировка
Быстрая сортировка работает «на месте», без привлечения дополнительной памяти.
Асимптотическое время

работы быстрой сортировки для среднего случая отличается от времени работы для наихудшего случая.
Парадигма « разделяй и властвуй».
Изначально мы хотим отсортировать все n книг
в слотах с первого до n-го
и при этом рассматриваем обобщенную задачу сортировки книг
в слотах с p до r.

Слайд 10

Быстрая сортировка
Парадигма « разделяй и властвуй».
Этап разделения: «опорная» книга –

индекс 15

Слайд 11

Быстрая сортировка
Разделение. Сначала выберем одну книгу из слотов от p до

r. Назовем эту книгу опорной. Представим книги на полке так, чтобы все книги с авторами, идущими в алфавитном порядке до автора опорной книги, находились слева от опорной, а книги с авторами, идущими по алфавиту после автора опорной книги, - справа от последней. После разбиения книги как слева от опорной книги, так и справа, не располагаются в каком-то конкретном порядке.
Властвование. Осуществляется путем рекурсивной сортировки книг слева и справа от опорного элемента. То есть если при разделении опорный элемент вносится в слот q, то рекурсивно сортируются книги в слотах с p по q-1 и с q+1 по r .
Объединение. На этом этапе мы ничего не делаем! После рекурсивной сортировки мы получаем полностью отсортированный массив. Авторы всех книг слева от опорной ( в слотах с p по q-1) идут по алфавиту до автора опорной книги, и книги отсортированы, а авторы всех книг справа от опорной книги (с q+1 по r) идут по алфавиту после автора опорной книги, и все эти книги также отсортированы.

Слайд 12

Быстрая сортировка
Процедура быстрой сортировки подразумевает вызов процедуры
Partition (A, p, r),

которая разбивает подмассив A[p..r] и возвращает индекс q позиции, в которую помещается опорный элемент.
Процедура Quicksort(A, p, r)
Вход и результат : те же, что и у процедуры Merge-Sort.
Если p >= r, просто выйти из процедуры, не выполняя никаких действий.
В противном случае выполнить следующее.
Вызвать Partition (A, p, r) и установить значение q равным результату вызова.
Рекурсивно вызвать Quicksort(A, p, q-1).
Рекурсивно вызвать Quicksort(A, q+1, r).

Слайд 13

Быстрая сортировка
Первоначальный вызов Quicksort(A, 1, r) аналогичен вызову процедуры Merge-Sort.
Пример

работы процедуры Quicksort с развернутой рекурсией.
Для каждого подмассива, в котором p<= r, указаны индексы p, q, r.
Самое нижнее значение в каждой позиции массива показывает, какой элемент будет находиться в этой позиции по завершении сортировки.
При чтении массива слева направо смотрим на самые нижние значения в каждой позиции, массив отсортирован.

Слайд 14

Быстрая сортировка Вызов процедуры Partition
Процедура разбиения книг на полке в слотах с

p по r. В качестве опорной выбираем крайнюю справа книгу - из слота r. В любой момент каждая книга может находиться в одной из четырех групп, и эти группы располагаются в слотах от p до r слева направо.
Группа L (левая) : книги с авторами, о которых известно, что они располагаются в алфавитном порядке до автора опорной книги или написаны автором опорной книги.
Далее идет группа R( правая): книги с авторами, о которых известно, что они располагаются в алфавитном порядке после автора опорной книги.
Затем идет группа U (неизвестная) : книги, которые еще не рассмотрели и не знаем, как их авторы располагаются по отношению к автору опорной книги в алфавитном порядке.
Последней идет группа P (опорная): в нее входит единственная опорная книга.
Мы проходим по книгам группы U слева направо, сравнивая каждую из них с опорной и перемещая ее либо в группу L, либо в группу R, останавливаясь по достижении опорной книги. Книга, которую мы сравниваем с опорной, - всегда крайняя слева в группе U.

Слайд 15

Быстрая сортировка Вызов процедуры Partition ( A, 9,15)

Слайд 16

Быстрая сортировка Вызов процедуры Partition ( A, 9,15), продолжение.

Слайд 17

Быстрая сортировка Вызов процедуры Partition ( A, 9,15), описание
Если автор книги находится

в алфавитном порядке после автора опорной книги, то книга становится крайней справа в группе R. Поскольку до этого она была крайней слева в группе U, а за группой U непосредственно следует группа R, мы должны просто переместить разделительную линию между группами R и U на один слот вправо, без перемещения каких-либо книг.
Если автор книги находится в алфавитном порядке до автора опорной книги или совпадает с автором опорной книги, то эта книга становится крайней справа в группе L. Мы обмениваем ее с крайней слева книгой в группе R и перемещаем разделительную линию между группами L и R и между группами R и U на один слот вправо.

Слайд 18

Быстрая сортировка Вызов процедуры Partition ( A, 9,15), результат.

Слайд 19

Быстрая сортировка
Чтобы преобразовать разбиение книг на полке в разбиение подмассива A[p..r],

мы сначала выбираем крайний справа элемент A[r] в качестве опорного. Затем мы проходим через подмассив слева направо, сравнивая каждый элемент с опорным. Мы поддерживаем в подмассиве индексы q и u , которые разделяют его следующим образом:
подмассив A[p..q-1] соответствует группе L: каждый его элемент не превышает опорный;
подмассив A[q..u-1] соответствует группе R : каждый его элемент больше опорного;
подмассив A[u..r-1] соответствует группе U: нам пока неизвестно, как его элементы соотносятся с опорным;
элемент A[r] соответствует группе P: это опорный элемент.

Слайд 20

Быстрая сортировка
Процедура Partition(A, p, r)
Вход: тот же, что и для процедуры

Merge-Sort.
Результат: перестановка элементов A[p..r], такая, что каждый элемент в A[p..q-1] не превышает A[q], а каждый элемент в A[q+1..r] больше A[q]. Возвращает значение индекса q.
1.Установить q равным p.
2.Для u=p до r-1:
Если A[u]<=A[r], обменять А[q] с A[u], а затем увеличить q на 1.
3.Обменять А[q] с A[r], а затем вернуть q.

Слайд 21

Быстрая сортировка Процедура Partition(A, p, r): перестановка элементов A[p..r], такая, что каждый элемент

в A[p..q-1] не превышает A[q], а каждый элемент в A[q+1..r] больше A[q]. Возвращает значение индекса q. 1.Установить q равным p. 2.Для u=p до r-1: Если A[u]<=A[r], обменять А[q] с A[u], а затем увеличить q на 1. 3.Обменять А[q] с A[r], а затем вернуть q.

Сортировка посредством выбора

Содержание

Сортировка вставками

Сортировка вставками А = 50, 20, 40, 75, 35 O(n2)

Сортировка слиянием (продолжение)

Сортировка слиянием (продолжение)A[p..q] A[q+1..r] A[p..r]n1= q-p+1 A[p..q] n2=r-q A[q+1..r] Массив B

Сортировка слиянием (продолжение)Процедура Merge(A, p, q, r)Вход:А: массивp, q, r: индексы

Слияние сортированных последовательностей

Быстрая сортировкаБыстрая сортировка работает «на месте», без привлечения дополнительной памяти.Асимптотическое время

Быстрая сортировкаПарадигма « разделяй и властвуй». Этап разделения: «опорная» книга –

Быстрая сортировкаРазделение. Сначала выберем одну книгу из слотов от p до

Быстрая сортировкаПроцедура быстрой сортировки подразумевает вызов процедуры Partition (A, p, r),

Быстрая сортировкаПервоначальный вызов Quicksort(A, 1, r) аналогичен вызову процедуры Merge-Sort. Пример

Быстрая сортировка Вызов процедуры PartitionПроцедура разбиения книг на полке в слотах с