Сортировка массивов.

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

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

Основні вимоги до сортування масивів – раціональне використання пам'яті. Це означає, що переупорядкування елементів потрібно виконувати в цьому ж самому масиві.

Існує кілька різних методів сортування, що відрізняються ступенем складності й ефективністю. Зручна міра ефективності утворюється при підрахунку числа С - необхідних порівнянь ключів і М – кількості пересилань елементів. Ці числа визначаються деякими функціями від числа n – кількості елементів, що впорядковуються.

Методи, що сортують елементи усередині масиву, можна розбити в залежності від покладеного в їх основі прийому:

· сортування простим вибором;

· сортування простою перестановкою;

· сортування бульбашковим методом;

При розгляді основних методів зробимо припущення:

· в ролі структури даних для розгляду алгоритмів сортування оберемо одновимірний цілочисельний масив;

· сортування буде здійснюватись без використання допоміжних масивів;

· впорядкування здійснюється за зростанням;

· в головній програмі діє такий опис даних.

const n=...;

{кількість елементів масиву визначається користувачем}

type

massiv = array[1..n] ofinteger;

var

a: massiv;

i: integer;

Пример:

1. Простым выбором

2. Простой перестановкой

3. Пузырьковый метод

На каждом шаге находится минимальный (максимальный) неотсортированной части. Он меняется с первым элементом в неотсортированной части, после чего отсортированная часть увеличивается на один элемент. На первом шаге весь массив считается неотсортированным. Сортировка заканчивается за (n-1) шаг.