Тема 5. Методи упорядкування даних

Одним із важливих є клас задач – упорядкування файлів, тобто розміщення елементів даних у певному порядку, що дозволяє значно прискорити пошук і обробку інформації. Упорядкування даних може бути за зростанням, за спаданням, за алфавітним порядком.

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

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

Методи внутрішнього впорядкування базуються на таких підходах:

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

2. Обмін: багатократно порівнюються і впорядковуються сусідні елементи.

3. Вставка: кожний новий елемент уставляється в правильну позицію стосовно вже розміщених у масиві і впорядкованих елементів.

4. Злиття: впорядковані підмножини елементів об’єднуються в більші впорядковані підмножини.

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

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

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

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

Метод злиття. Якщо масиви упорядковані за зростанням для їх злиття за зростанням порівнюємо елементи масивів і : якщо , то записуємо в масив і переходимо до , інакше в масив записуємо і переходимо до і т. д. Для злиття масивів за спаданням порівнюємо елементи з кінця масиву і якщо , то записуємо в масив і переходимо до , інакше в масив записуємо і переходимо до і т. д. Цей процес завершується, якщо вичерпуються елементи масиву або . Якщо вичерпався масив , то елементи, які залишилися у масиві , дописуються в масив . Якщо вичерпався масив , то елементи, які залишилися в масиві , дописуються в масив .