13.5. Сортування масивів

Сортування - класична задача програмування. Вона є невід'ємною частиною багатьох процесів обробки даних. Під сортуванням масиву розуміється процес перестановки елементів із ціллю впорядкування у відповідності з заданим критерієм. Наприклад, якщо маємо масив цілих чисел А, те після сортування по зростанню повинна виконуватись умова:

А[0]  А[1]  … ≤ А[N-1],

де N - розмір масиву.

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

Задача

Надано масив значень А[0], А[1], … , А[N-1], де N - кількість елементів масиву. Треба впорядкувати масив у відповідності до наданого критерію (по збільшенню чи по зменшенню). Елементи масиву А належать до деякої множини, елементи якої можна порівнювати між собою.

Алгоритм

Існує досить велика кількість алгоритмів сортування масивів. Розглянемо два з них:

• метод прямого вибору;

• метод парного обміну.

Сортування методом прямого вибору

Схема алгоритму сортування масиву по зростанню методом прямого вибору виглядає в такий спосіб.

1. Переглядаючи масив з першого елемента, знаходимо мінімальний елемент і поміщаємо його на місце першого, а перший - на місце мінімального.

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

3. І так далі до передостаннього елемента.

Нижче представлена програма сортування масиву цілих чисел по зростанню. Для демонстрації процесу сортування програма друкує масив після кожної перестановки елементів.

// Приклад 1

#include <syst.h>