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

Загальні відомості про сортування масивів

Методи сортування.

Інформаційні матеріали теми

1. Загальні відомості про сортування масивів

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

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

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

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

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

· сортування включеннями;

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

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

· швидке сортування.

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

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

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

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

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

const n=...;

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

type

massiv = array[1..n] of integer;

var

a:massiv;

i:integer;

2. Методи сортування.