Сортування - класична задача програмування. Вона є невід'ємною частиною багатьох процесів обробки даних. Під сортуванням масиву розуміється процес перестановки елементів із ціллю впорядкування у відповідності з заданим критерієм. Наприклад, якщо маємо масив цілих чисел А, те після сортування по зростанню повинна виконуватись умова:
А[0] £ А[1] £ … ≤ А[N-1],
де N - розмір масиву.
Задача сортування часто зустрічається в інформаційних системах і використовується як попередній етап у задачах пошуку. Пошук у впорядкованих масивах здійснюється набагато швидче, ніж пошук у невпорядкованих масивах.
Задача
Надано масив значень А[0], А[1], … , А[N-1], де N - кількість елементів масиву. Треба впорядкувати масив у відповідності до наданого критерію (по збільшенню чи по зменшенню). Елементи масиву А належать до деякої множини, елементи якої можна порівнювати між собою.
Алгоритм
Існує досить велика кількість алгоритмів сортування масивів. Розглянемо два з них:
- метод прямого вибору;
- метод парного обміну.
Сортування методом прямого вибору
Схема алгоритму сортування масиву по зростанню методом прямого вибору виглядає в такий спосіб.
1. Переглядаючи масив з першого елемента, знаходимо мінімальний елемент і поміщаємо його на місце першого, а перший - на місце мінімального.
2. Переглядаючи масив, починаючи із другого елемента, знаходимо мінімальний елемент і поміщаємо його на місце другого, а другий - на місце мінімального.
3. І так далі до передостаннього елемента.
Нижче представлена програма сортування масиву цілих чисел по зростанню. Для демонстрації процесу сортування програма друкує масив після кожної перестановки елементів.
// Приклад 1
#include <syst.h>