Определение и виды сортировки

Август 22, 2022

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

Содержание

2. Определение сортировки Сортировка - процесс упорядочения множества подобных информационных объектов в некотором определённом порядке с целью
3. Виды сортировки Сортировки, в зависимости от типа сортируемого объекта, можно разделить на 2 вида: Сортировка файлов
4. Сортировка массивов Внутренняя сортировка, или сортировка массивов, оперирует массивами, целиком помещающимися в оперативной памяти с произвольным
5. Сортировка файлов Внешняя сортировка, или сортировка файлов, оперирует запоминающими устройствами большого объёма. Доступ к носителю осуществляется
6. Критерии оценки алгоритмов Время или вычислительная сложность— основной параметр, характеризующий быстродействие алгоритма. Идеальное поведение для упорядочения
7. Свойства алгоритмов сортировки Устойчивость Естественность поведения Использование операции сравнения
8. 2 подхода к сортировке массивов Простые способы Улучшенные способы Устойчивость — устойчивая сортировка не меняет взаимного
9. Список простых способов сортировки Список простых, или устойчивых, способов сортировки: Сортировка вставками - O(n^2) Сортировка выбором
10. Список улучшенных способов сортировки Список улучшенных, или неустойчивых, способов: Быстрая сортировка, или QuickSort - O(n log
11. Сортировка вставками Сортировка вставками — алгоритм сортировки, в котором элементы исходной последовательности просматриваются по одному, и
12. Простые вставки
13. Простые вставки
14. Простые вставки Алгоритм состоит из (n-1)-го прохода, каждый из которых включает 4 действия: Взятие очередного i-го
15. Вставки с барьерным элементом
16. Вставки с барьерным элементом
17. Вставки с барьерным элементом Введение барьерного элемента позволяет отказаться от проверки условия выхода за пределы массива,
18. Метод бинарного поиска элемента Бинарный поиск - классический алгоритм поиска элемента в отсортированном массиве, использующий дробление
19. Вставки методом бинарного поиска
20. Вставки методом бинарного поиска
21. Вставки методом бинарного поиска Особенности метода: Неестественность поведения – если элементы в исходном массиве расположены в
22. Сортировка выбором Метод прямого выбора в некотором смысле противоположен методу прямой вставки. При прямой вставке на
23. Сортировка выбором
24. Сортировка выбором Как правило, алгоритм сортировки с прямым выбором предпочтительнее метода прямой вставки. Однако если элементы
25. Сортировка выбором Порядок шагов для сортировки: Выбрать минимальный элемент из всего исходного массива и поместить его
26. Методы сортировки обменом Сущность этого метода отражена в названии. Самые «легкие» элементы массива «всплывают», а самые
27. Метод простого обмена
28. Метод простого обмена
29. Пузырёк с флажком При реализации сортировки методом обмена приходится выполнять одиночные проходы n-1 раз. Этого можно
30. Пузырёк с флажком
31. Пузырёк с флажком
32. Плавающий пузырёк Если на некотором шаге выполняется просмотр i-го элемента и слева от него имеется уже
33. Плавающий пузырёк
34. Плавающий пузырёк
35. Шейкерная сортировка Легко увидеть, что в алгоритме сортировки “пузырьком” “легкие пузырьки” всплывают за один проход, а
36. Шейкерная сортировка
37. Шейкерная сортировка
39. Скачать презентацию

Слайд 2

Определение сортировки
Сортировка - процесс упорядочения множества подобных информационных объектов в некотором

определённом порядке с целью облегчения последующего поиска нужных элементов.

Слайд 3

Виды сортировки
Сортировки, в зависимости от типа сортируемого объекта, можно разделить на

2 вида:

Сортировка файлов

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

Слайд 4

Сортировка массивов
Внутренняя сортировка, или сортировка массивов, оперирует массивами, целиком помещающимися в

оперативной памяти с произвольным доступом к любой ячейке.
Данные обычно упорядочиваются на том же месте без дополнительных затрат памяти.

Слайд 5

Сортировка файлов
Внешняя сортировка, или сортировка файлов, оперирует запоминающими устройствами большого объёма.

Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
Объём данных не позволяет им разместиться в ОЗУ.
Это приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство.

Слайд 6

Критерии оценки алгоритмов
Время или вычислительная сложность— основной параметр, характеризующий быстродействие алгоритма.

Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только операцию сравнения всегда нуждаются в O(n log n) сравнениях.
Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Слайд 7

Свойства алгоритмов сортировки
Устойчивость
Естественность поведения
Использование операции сравнения

Слайд 8

2 подхода к сортировке массивов
Простые способы
Улучшенные способы
Устойчивость — устойчивая сортировка не

меняет взаимного расположения элементов с одинаковыми ключами
Простые способы сортировки соответствуют устойчивой сортировке, улучшенные - неустойчивой.

Слайд 9

Список простых способов сортировки
Список простых, или устойчивых, способов сортировки:
Сортировка вставками -

O(n^2)
Сортировка выбором - O(n^2)
Пузырьковая сортировка - O(n^2)
Гномья сортировка - O(n^2)
Сортировка слиянием - O(n log n)
Сортировка подсчётом - O(n+k)
Блочная сортировка - O(n)

Слайд 10

Список улучшенных способов сортировки
Список улучшенных, или неустойчивых, способов:
Быстрая сортировка, или QuickSort

- O(n log n) - O(n^2)
Сортировка Шелла, или ShellSort - O(n log^2 n)
Пирамидальная сортировка, или HeapSort - O(n log n)
Сортировка расчёской, или ComsSort - O(n log n)
Плавная сортировка, или SmoothSort - O(n log n)
Интроспективная сортировка, или IntroSort - O(n log n)
Терпеливая сортировка, или PatienceSort - O(n log n)
Поразрядная сортировка - O(nk)

Слайд 11

Сортировка вставками
Сортировка вставками — алгоритм сортировки, в котором элементы исходной последовательности

просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов
Разновидности:
Простые вставки
Вставки с барьерным элементом
Бинарные вставки или вставки методом бинарного поиска

Слайд 12

Простые вставки

Слайд 13

Простые вставки

Слайд 14

Простые вставки
Алгоритм состоит из (n-1)-го прохода, каждый из которых включает 4

действия:
Взятие очередного i-го неотсортированного элемента и сохранение его
Поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности
Сдвиг элементов от j-го до (i-1)-го вправо, чтобы освободить позицию для вставки
Вставка взятого элемента в найденную j-ую позицию

Слайд 15

Вставки с барьерным элементом

Слайд 16

Вставки с барьерным элементом

Слайд 17

Вставки с барьерным элементом
Введение барьерного элемента позволяет отказаться от проверки условия

выхода за пределы массива, т. к. условие остановки при поиске места для элемента определяется следующим правилом: слева меньшие или равные вставляемому элементу, а справа строго большие его.

Слайд 18

Метод бинарного поиска элемента
Бинарный поиск - классический алгоритм поиска элемента в

отсортированном массиве, использующий дробление массива на половины.

RIGHT

LEFT

Слайд 19

Вставки методом бинарного поиска

Слайд 20

Вставки методом бинарного поиска

Слайд 21

Вставки методом бинарного поиска
Особенности метода:
Неестественность поведения – если элементы в исходном

массиве расположены в обратном порядке, то потребуется минимальное количество сравнений, если же массив уже упорядочен, то максимальное
Данный метод не меняет количества необходимых перестановок, а только количество сравнений

Слайд 22

Сортировка выбором
Метод прямого выбора в некотором смысле противоположен методу прямой вставки.

При прямой вставке на каждом шаге рассматривается только один очередной элемент исходной последовательности.
При прямом выборе для поиска одного минимального элемента просматриваются все элементы исходной неотсортированной последовательности.

Слайд 23

Сортировка выбором

Слайд 24

Сортировка выбором
Как правило, алгоритм сортировки с прямым выбором предпочтительнее метода прямой

вставки. Однако если элементы вначале упорядочены или почти упорядочены, прямое включение будет оставаться несколько более быстрым

Слайд 25

Сортировка выбором
Порядок шагов для сортировки:
Выбрать минимальный элемент из всего исходного массива

и поместить его на первое место, а первый элемент – на место минимального
Просматривая массив от второго элемента до конца, найти минимальный элемент и поместить его на второе место, а второй на место минимального.
Повторять эту операцию для каждого элемента кроме последнего

Слайд 26

Методы сортировки обменом
Сущность этого метода отражена в названии. Самые «легкие» элементы

массива «всплывают», а самые «тяжелые» - «тонут». Необходимо просмотреть весь массив и менять стоящие рядом элементы в том случае, если они стоят не по порядку. Таким образом, наверх выталкивается самый «легкий» элемент. Это повторяется для оставшихся элементов массива.
Разновидности:
Метод простого обмена (Пузырёк)
Пузырёк с флажком
Метод «Плавающего пузырька»
Шейкерная сортировка

Слайд 27

Метод простого обмена

Слайд 28

Метод простого обмена

Слайд 29

Пузырёк с флажком
При реализации сортировки методом обмена приходится выполнять одиночные проходы

n-1 раз. Этого можно избежать, если перед проведением очередного прохода проверять, была ли произведена перестановка на предыдущем проходе. Для этого нужно ввести вспомогательную переменную «флажок». Если перестановки не было, значит массив упорядочен и сортировку можно прекратить.

Слайд 30

Пузырёк с флажком

Слайд 31

Пузырёк с флажком

Слайд 32

Плавающий пузырёк
Если на некотором шаге выполняется просмотр i-го элемента и слева

от него имеется уже упорядоченная последовательность элементов, то в конечном счете i-й элемент займет любую позицию от 1-й до i-й. Выполняется движение к концу массива, до тех пор, пока не обнаружится нарушение сортирующего условия. После соответствующего обмена элементов начинается движение в обратном направлении до тех пор, пока выполняются необходимые обмены элементов. Если обменов при обратном движении уже нет, то движение продолжается с места остановки. Описанная процедура повторяется до тех пор, пока не будет достигнут конец массива.

Слайд 33

Плавающий пузырёк

Слайд 34

Плавающий пузырёк

Слайд 35

Шейкерная сортировка
Легко увидеть, что в алгоритме сортировки “пузырьком” “легкие пузырьки” всплывают

за один проход, а “тяжелые” – тонут за несколько. Такая асимметрия вызвала появление новой идеи сортировки, “пузырьком”, а именно: сортировать не в одну сторону, а поочередно в обе, т.е. на каждом шаге осуществляется проход как в одну сторону, так и в другую. Таким образом, на каждом шаге “легкий пузырек” всплывает на поверхность, а “тяжелый” – тонет.

Слайд 36

Шейкерная сортировка

Слайд 37

Определение и виды сортировки

Содержание

Определение сортировки Сортировка - процесс упорядочения множества подобных информационных объектов в некотором

Виды сортировкиСортировки, в зависимости от типа сортируемого объекта, можно разделить на

Сортировка массивовВнутренняя сортировка, или сортировка массивов, оперирует массивами, целиком помещающимися в

Сортировка файловВнешняя сортировка, или сортировка файлов, оперирует запоминающими устройствами большого объёма.

Критерии оценки алгоритмовВремя или вычислительная сложность— основной параметр, характеризующий быстродействие алгоритма.

Свойства алгоритмов сортировкиУстойчивостьЕстественность поведенияИспользование операции сравнения

2 подхода к сортировке массивовПростые способыУлучшенные способыУстойчивость — устойчивая сортировка не

Список простых способов сортировкиСписок простых, или устойчивых, способов сортировки:Сортировка вставками -

Список улучшенных способов сортировкиСписок улучшенных, или неустойчивых, способов:Быстрая сортировка, или QuickSort

Сортировка вставкамиСортировка вставками — алгоритм сортировки, в котором элементы исходной последовательности

Простые вставки

Простые вставки

Простые вставкиАлгоритм состоит из (n-1)-го прохода, каждый из которых включает 4

Вставки с барьерным элементом

Вставки с барьерным элементом

Вставки с барьерным элементомВведение барьерного элемента позволяет отказаться от проверки условия

Метод бинарного поиска элементаБинарный поиск - классический алгоритм поиска элемента в

Вставки методом бинарного поиска

Вставки методом бинарного поиска

Вставки методом бинарного поискаОсобенности метода:Неестественность поведения – если элементы в исходном

Сортировка выборомМетод прямого выбора в некотором смысле противоположен методу прямой вставки.

Сортировка выбором

Сортировка выборомКак правило, алгоритм сортировки с прямым выбором предпочтительнее метода прямой

Сортировка выборомПорядок шагов для сортировки:Выбрать минимальный элемент из всего исходного массива

Методы сортировки обменомСущность этого метода отражена в названии. Самые «легкие» элементы

Метод простого обмена

Метод простого обмена

Пузырёк с флажкомПри реализации сортировки методом обмена приходится выполнять одиночные проходы

Пузырёк с флажком

Пузырёк с флажком

Плавающий пузырёкЕсли на некотором шаге выполняется просмотр i-го элемента и слева

Плавающий пузырёк

Плавающий пузырёк

Шейкерная сортировкаЛегко увидеть, что в алгоритме сортировки “пузырьком” “легкие пузырьки” всплывают

Шейкерная сортировка

Шейкерная сортировка

Похожие презентации

Определение сортировки
Сортировка - процесс упорядочения множества подобных информационных объектов в некотором

Виды сортировки
Сортировки, в зависимости от типа сортируемого объекта, можно разделить на

Сортировка массивов
Внутренняя сортировка, или сортировка массивов, оперирует массивами, целиком помещающимися в

Сортировка файлов
Внешняя сортировка, или сортировка файлов, оперирует запоминающими устройствами большого объёма.

Критерии оценки алгоритмов
Время или вычислительная сложность— основной параметр, характеризующий быстродействие алгоритма.

Свойства алгоритмов сортировки
Устойчивость
Естественность поведения
Использование операции сравнения

2 подхода к сортировке массивов
Простые способы
Улучшенные способы
Устойчивость — устойчивая сортировка не

Список простых способов сортировки
Список простых, или устойчивых, способов сортировки:
Сортировка вставками -

Список улучшенных способов сортировки
Список улучшенных, или неустойчивых, способов:
Быстрая сортировка, или QuickSort

Сортировка вставками
Сортировка вставками — алгоритм сортировки, в котором элементы исходной последовательности

Простые вставки
Алгоритм состоит из (n-1)-го прохода, каждый из которых включает 4

Вставки с барьерным элементом
Введение барьерного элемента позволяет отказаться от проверки условия

Метод бинарного поиска элемента
Бинарный поиск - классический алгоритм поиска элемента в

Вставки методом бинарного поиска
Особенности метода:
Неестественность поведения – если элементы в исходном

Сортировка выбором
Метод прямого выбора в некотором смысле противоположен методу прямой вставки.

Сортировка выбором
Как правило, алгоритм сортировки с прямым выбором предпочтительнее метода прямой

Сортировка выбором
Порядок шагов для сортировки:
Выбрать минимальный элемент из всего исходного массива

Методы сортировки обменом
Сущность этого метода отражена в названии. Самые «легкие» элементы

Пузырёк с флажком
При реализации сортировки методом обмена приходится выполнять одиночные проходы

Плавающий пузырёк
Если на некотором шаге выполняется просмотр i-го элемента и слева

Шейкерная сортировка
Легко увидеть, что в алгоритме сортировки “пузырьком” “легкие пузырьки” всплывают