Методичні вказівки до лабораторних робіт з дисципліни «програмування на мові високого

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

Послідовно порівнюється елемент а0 з кожним наступним ai і, якщо ai<а0, то эти два элемента меняются местами; таким образом наименьший элемент оказывается на своем месте в начале массива. Затем этот метод применяется к элементу а1 и т. д.

У цьому методі проходи масиву виконуються по черзі: зліва направо, а потім справа наліво. Послідовно порівнюються пари сусідніх елементів (а0 і а1, а1 і а2, і т. Д.) І, якщо треба, переставляються. Запам'ятовується індекс останнього переставляється елемента (right). Далі масив проглядається справа наліво, починаючи з індексу right. У цьому проході масиву також виконуються порівняння сусідніх елементів і їх перестановка. Запам'ятовується індекс останнього переставляється елемента (left). Далі знову виконується прохід зліва направо від індексу left до індексу right і т. Д.

Вибирається інтервал d між порівнюваними елементами, і виконується сортування масиву методом «бульбашки», але з кроком d. Після етапу сортування масиву з обраним інтервалом, цей інтервал зменшується і знову виконується сортування масиву методом «бульбашки». Рекомендується наступна послідовність значень d. 1, 3, 7, 15, 31, ..., т. е.

Максимальне значення d не повинно перевищувати довжину масиву. Таким чином, в цьому алгоритмі спочатку порівнюються і, якщо треба переставляються далеко стоять елементи, а на останньому проході - сусідні.

Швидке сортування (метод Хоара).

Комбінований метод швидкого сортування з методом «бульбашки».

У цьому методі рекурсивний алгоритм поділу масиву швидкого сортування застосовується тільки для підпослідовностей масиву, довжина яких не менше певного розміру m (m <=n ). Для сортировки коротких подпоследовательностей используется метод «пузырька».

Елементи масиву діляться на вже впорядковану послідовність а 0, а 1, ..., а i-1 і невпорядкованих аi, ai + 1, ..., an-1. У кожному проході з невпорядкованою послідовності витягується елемент аi (в першому проході i = 1) і вставляється в упорядковану послідовність з i елементів без порушення впорядкованості в ній. Цей алгоритм повторюється для i = 2,3, ..., n-1. Алгоритм вставки аi в упорядковану послідовність з i елементів полягає в просуванні вставляється елемента в початок послідовності, порівнюючи його з аi-1, ai-2 і т. Д. Просування закінчується на елементі аj<=ai или при прохождении всей последовательности.

У цьому методі, на відміну від лінійної вставки, для відшукання місця для вставки елемента ai в упорядковану послідовність використовується алгоритм бінарного пошуку, при якому елемент ai порівнюється із середнім елементом впорядкованої послідовності, а потім процес ділення навпіл триває до тих пір, поки не буде знайдена точка включення.

Алгоритм використовує додатковий робочий масив. У позицію, розташовану в центрі робочого масиву поміщається елемент а0. Він буде медіаною. Зліва від медіани треба розташувати всі елемент, менші медіани, а праворуч - великі чи рівні. З сортованого масиву послідовно вибирається елемент, порівнюється з медіаною і вставляється без порушення впорядкованості в ліву чи праву частини масиву. Якщо область пам'яті, виділена для однієї з частин, буде вичерпана, то всі елементи робочого масиву зсуваються в протилежному напрямку і значення медіани змінюється. В кінці алгоритму впорядковані елементи повинні бути скопійовані в вихідний масив.

Метод фон Неймана.

Впорядкувати пари сусідніх елементів масиву а (а0 і а1, а2 і а3 і т. Д.) І перенести їх в допоміжний масив b. Потім взяти по дві сусідні пари з b і, слив їх в впорядковані четвірки, знову записати в а; потім кожні дві четвірки з b злити в впорядковані вісімки і переписати в а і т. д. Упорядкований масив повинен виявитися в масиві а.

Зовнішня двухфазная сортування прямим злиттям.

Зовнішня сортування використовується для сортування файлів, розміри яких не дозволяють записати їх у тимчасові масиви в оперативній пам'яті. Для сортування використовуються три файли: c (вихідний файл), a і b (допоміжні файли). Елементи вихідного файлу з поперемінно записуються то в а. то в файл b (фаза поділу). Таким чином, в кожному файлі створюються одноелементні послідовності. Далі формуються двоелементний впорядковані послідовності, в яких один елемент береться з а. а інший з b (фаза злиття). Ці двоелементний послідовності записуються в файл с. Далі двоелементний послідовності поперемінно записуються то в а. то в файл b (фаза поділу). Потім двоелементний послідовності з файлів a і b зливаються в впорядковані четвірки і записуються в файл з (фаза злиття). Алгоритм розбиття файлу з навпіл і формування упорядкованих послідовностей шляхом злиття пар послідовностей з файлів a і b повторюється до тих пір, поки в файлах a і b не утворюється по одній впорядкованої послідовності, які остаточно зливаються в відсортоване файл с.

У завданні реалізувати «внутрішню» версію алгоритму для сортування масиву з n елементів.

Зовнішня однофазная сортування прямим злиттям.

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

У завданні реалізувати «внутрішню» версію алгоритму для сортування масиву з n елементів.

Зовнішня сортування природним злиттям.

Сортування, при якій зливаються дві найдовші з можливих впорядкованих послідовностей, називається природним злиттям. В алгоритмі використовується вихідний файл з і два допоміжних файлу a і b. В алгоритмі при першому проході визначаються як можна більш довгі впорядковані послідовності файлу с. Далі ці послідовності поперемінно записуються в файли a і b. На кожному наступному проході пари i-х упорядкованих послідовностей файлів a і b (i = 1,2,3, ...) зливаються в довші впорядковані послідовності і переносяться в файл с, після чого настає фаза поділу: послідовності поперемінно записуються в файли a. В кінці алгоритму єдина впорядкована послідовність повинна виявитися в файлі с.

У завданні реалізувати «внутрішню» версію алгоритму для сортування масиву з n елементів.

Зовнішня сортування збалансованим злиттям.

В алгоритмі використовується вихідний файл з і три допоміжних файлу a, b, d. В даному алгоритмі при першому проході визначаються як можна більш довгі впорядковані ділянки файлу с. Далі ці ділянки поперемінно записуються в файли a і b. На наступному етапі пари i-х упорядкованих послідовностей файлів a і b (i = 1,2,3, ...) зливаються в довші впорядковані послідовності і поперемінно переносяться в файли з иd. Потім зливаються пари послідовностей файлів з иd і поперемінно переносяться в файли aіb і т. Д. В кінці алгоритму єдина впорядкована послідовність повинна виявитися в файлі с.

У завданні реалізувати «внутрішню» версію алгоритму для сортування масиву з n елементів.

Алгоритм застосовується до впорядкованого масиву, в якому треба знайти номер елемента із заданим значенням x. Спочатку х порівнюється із середнім елементом масиву. Якщо збіг знайдено, то повертається індекс середнього елемента, інакше визначається, в якій половині масиву слід виконувати пошук, застосовуючи до неї алгоритм бінарного пошуку.

Алгоритм застосовується до впорядкованого масиву, в якому треба знайти номер елемента із заданим значенням x. Якщо відомо, що х знаходиться між елементами al і ar, то номер чергового елемента для порівняння обчислюється за формулою

Якщо збіг знайдено, то повертається індекс елемента (m), інакше визначається, в якій частині масиву слід виконувати пошук, застосовуючи до неї алгоритм інтерполяційного пошуку.

#include

#include

void sort (int a [], int n)