Упорядкування даних. Одним із важливих є клас обчислювальних задач – упорядкування файлів, тобто розміщення елементів даних у певному порядку, що дозволяє значно прискорити пошук і обробку інформації. Упорядкування даних може бути за зростанням, за спаданням, за алфавітним порядком.
Упорядковувати доводиться як прості структури даних (масиви чисел), так і складні (масиви записів). У випадку записів упорядкування здійснюється за ключами, тобто окремими полями або групою полів запису. Ключі можуть бути як числовими, так і символьними. Переміщення ключа при упорядкуванні вимагає переміщення всього запису, але це не викликає принципових труднощів, тому будемо розглядати впорядкування масивів.
Упорядкування може бути внутрішнім і зовнішнім. Якщо дані, які впорядковуються, повністю розміщуються в пам’яті, то упорядкування буде внутрішнім. Якщо даних багато і для їх розміщення вимагається зовнішня пам’ять, то впорядкування буде зовнішнім. При зовнішньому впорядкуванні масив даних розбивається на частини, які впорядковуються методами внутрішнього впорядкування, які потім зливаються в один упорядкований масив.
Методи внутрішнього впорядкування базуються на таких підходах:
1. Вибірка: вибирається найбільший (або найменший) елемент масиву і поміщається на перше місце, потім аналогічна процедура виконується з елементами, що залишилися.
2. Обмін: багатократно порівнюються і впорядковуються сусідні елементи.
