Определение и виды сортировки презентация

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

2 вида:

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

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

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

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

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

Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

меняет взаимного расположения элементов с одинаковыми ключами

Простые способы сортировки соответствуют устойчивой сортировке, улучшенные - неустойчивой.

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

- 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)

просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов

Разновидности:
Простые вставки
Вставки с барьерным элементом
Бинарные вставки или вставки методом бинарного поиска

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

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

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

RIGHT

LEFT

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

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

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

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

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

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

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

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

количества чисел, при этом их произведение не должно превышать число 300.