Алгоритми швидкого сортування

Базується на алгоритмі «Розділяй та пануй» і операції вибірки. В залежності від способа ділення набору на частини розрізняють декілька видів швидкого сортування:

1. Базовий алгоритм швидкого сортування :

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

2. Швидке сортування з розділенням на три частини – набір ділиться на три частини, елементи з значенням рівними розділяючому і зустрівшися в лівій частині переміщаючись до лівого краю, елементи з значеннями рівним розподіляючому і зустрівшися в правій частині переміщуються до правого краю, потім частини сортуються окремо.

3. Швидке сортування вираховуванням медіани із 3 елементів :

Суть – разделяющий элемент выбирается произвольно из трех (в основной из первого, последнего и среднего):

Средний меняется местами с предпоследним

Первый, предпоследний и последний элементы упорядочиваются (наименьший – на первое место, наибольший – на последнее)

Сортируется набор данных между первым и предпоследним элементами

Окончанием рекурсивной сортировки является проверка условия: если количество элементов в поднаборе меньше некоторого установленного значения, то сортировка такой части данным алгоритмом игнорируется

14. Опишіть сутність алгоритмів групи сортування злиттям, наведіть їхню класифікацію і особливості.

Сортування злиттям – це процес об’єднання двох відсортованих наборів в один.

Класифікація:

1. Алгоритм двухвидового злиття – із двох відсортованих наборів даних послідовно вибирається найменше (найбільше) і переміщається в третій набір.( і-й елемент із одного набора зрівнюється з j – м елементом із другого набора і найменший (найбільший ) елемент записується в третій набір )

2. Алгоритм «восходящего» сортування – набір ділиться на дві частини і виконується рекурсивне сортування обох частин з послідовним злиттям.

3. Алгоритм «нисходящего» сортування – не рекурсивне сортування виконання якої пропонує використання принципа «об’єднуй та пануй» (спочатку виконується злиття сусідніх елементів, потім сусідніх пра, потім сусідніх подвійних пар і т. д. )

15. Дайте визначення такої структури даних як «черга за пріоритетом», наведіть її представлення і реалізацію.

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

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

Применение: системы планирования заданий (ключ представляет собой значение приоритета).

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

Неупорядоченное представление определяет «ленивый» подход к решению задачи удаления элемента (когда выполнение работы откладывается до необходимого момента).

Упорядоченное представление – «энергичный» подход (когда заранее выполняется необходимый объем работ, чтобы обеспечить максимальную эффективность реализации операции удаления).

Сортирующее дерево – это совокупность узлов с ключами, образующими полное пирамидально упорядоченное

бинарное дерево, представленное в виде массива.

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

При формировании такого дерева выдерживается следующий порядок:

1. Создается корневой узел

2. Спускаясь вниз, перемещаются слева направо, добавляя каждому узлу предыдущего уровня по два узла текущего уровня.

16. Опишіть сутність базового алгоритму пірамідального сортування, наведіть відмінності у реалізації з чергою за пріоритетом.

Метод пирамидальной сортировки

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

Каждая позиция массива рассматривается как корень небольшого дерева и два потомка это узла (два поддерева) представляют собой сортирующие деревья.

Изначально просмотр сортируемого массива данных начинается с половины и далее просматривается массив в обратном порядке.

17. Опишіть сутність групи алгоритмів порозрядного сортування, їх особливості, приклад.

Сортування за розрядами — швидкий стабільний алгоритм впорядкування даних. Застосовується для впорядкування елементів, що є ланцюжками над будь-яким скінченним алфавітом (напр. рядки, або цілі числа). В якості допоміжного використовує будь-який інший стабільний алгоритм сортування.

Алгоритм застосовувався для впорядкування перфокарт.

Ідея алгоритму: Ідея полягає в тому, щоб спочатку впорядкувати всі елементи за молодшим розрядом, потім стабільно впорядкувати за другим розрядом, потім за третім і так далі аж до найстаршого. Оскільки, припускається, що кожен розряд приймає значення з невеликого діапазону, то кожен цикл впорядкування можна виконувати швидко і з малими затратами пам'яті.

18. Дайте визначення поняттю "пошуку", наведіть особливості реалізації і класифікацію алгоритмів пошуку.

обробки. Ефективність алгоритмів пошуку інформації залежить від упорядкованості і структурованості даних. Дані зберігаються в виді записів, які мають ключ, який використовується при пошуку. Пошук інформації оснований на операції рівності результатів, які являються повідомленнями про здійснення успішного або неуспішного пошуку (попадання або промах)