Олимпиады для учителей, учеников и дошкольников. Специальные наградные, результаты сразу, комфортное участие.

СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Выбрать материалы

Скидки до 50 % на комплекты
только до 07.06.2025

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

Был в сети 03.06.2023 16:09

Слобожанин Никита Николаевич

Разработчик web и мультимедийных приложений

399

111 253

Подписчики

Подписки

Специализация

Информатика

Обо мне Блог Файлы Тесты Галерея Активность Награды

Виды сортировок

Категория: Информатика

03.06.2023 16:02

Просмотр содержимого документа
«Виды сортировок»

ГАПОУ СО «Каменск-Уральский техникум торговли и сервиса»

Виды сортировок

Выполнил:

Слобожанин Никита Николаевич,

студент группы ИС-206,

09.02.05 «Информационные системы и

программирование»

Руководитель:

Экгауз Евгения Яковлевна

«Основы алгоритмизации»

Каменск-Уральский, 2022г.

Сортировка пузырьком / Bubble sort

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

Как работает?

Шейкерная сортировка / Shaker sort. Или сортировка перемешивание

Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа налево.

Как работает?

Сортировка расческой / Comb sort

Её идея состоит в том, чтобы «устранить» элементы с небольшими значения в конце массива, которые замедляют работу алгоритма. При «расчёсывании» сначала берётся достаточно большое расстояние между сравниваемыми значениями, а потом оно сужается вплоть до минимального.

Как работает?

Сортировка вставками / Insertion sort

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

Как работает?

Сортировка Шелла / Shellsort

При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1 (то есть обычной сортировкой вставками).

Как работает?

Сортировка деревом / Tree sort

Универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей.

Как работает?

Гномья сортировка / Gnome sort

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

Как работает?

Сортировка выбором / Selection sort

Может быть как устойчивый, так и неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае ( n 2 ), предполагая что сравнения делаются за постоянное время.

Как работает?

Пирамидальная сортировка / Heapsort

При этой сортировке сначала строится пирамида из элементов исходного массива. Пирамида (или двоичная куча) — это способ представления элементов, при котором от каждого узла может отходить не больше двух ответвлений. А значение в родительском узле должно быть больше значений в его двух дочерних узлах.

Как работает?

Быстрая сортировка / Quicksort

Этот алгоритм состоит из трёх шагов. Сначала из массива нужно выбрать один элемент — его обычно называют опорным. Затем другие элементы в массиве перераспределяют так, чтобы элементы меньше опорного оказались до него, а большие или равные — после. А дальше рекурсивно применяют первые два шага к подмассивам справа и слева от опорного значения.

Как работает?

Сортировка слиянием / Merge sort

Сортировка слиянием пригодится для таких структур данных, в которых доступ к элементам осуществляется последовательно (например, для потоков). Здесь массив разбивается на две примерно равные части и каждая из них сортируется по отдельности. Затем два отсортированных подмассива сливаются в один.

Как работает?

Сортировка подсчетом / Counting sort

Алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов.

Как работает?

Блочная сортировка / Bucket sort

Алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем

Как работает?

Поразрядная сортировка / Radix sort

Существует две разновидности: LSD (least significant digit) и MSD (least significant digit). В первом случае происходит сортировка элементов по младшим разрядам. После этого они группируются по следующему с конца разряду, пока они не закончатся. В MSD сортировка происходит по старшему разряду.