СОРТУВАННЯ

 

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

Якщо елементи позначити через

a1, a2, . . . , an-1, an,

то сортування означає перестановку іх у такому порядку

a i1, a i2, . . . , a in-1, a in,

що задана функція впорядкування f(x) буде нестрого монотонною на цій послідовності:

f(a i1) Ј f(a i2) Ј . . . Ј f(a in-1) Ј f(a in).

Значення f(ai) називаються ключем елементу ai. Так само, як у алгоритмах пошуку, будемо вважати, що дані мають структурований тип:

type 
  Item = record
    key : integer;
    rest = record
      { ... the rest}
    end;
  end;

Алгоритм сортування називається сталим (stable (англ.), устойчивым (рос.)), якщо у відсортованому масиві він не змінює порядку розташування елеиентів.

Ефективність методів сортування будемо визначати двома параметрами:


C - кількістю порівнянь (від compare);
M - кількістю пересилань елементів (від move).

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

При сортуванні масивів вважається, що масив увесь розміщено у пам'яті, тому не розглядаються алгоритми, що пересилають елементи повністю у інший масив, на який може не вистачити пам'яті. З іншого боку, для сортування масиву важливим є зменшення як C так і M, особливо для значних n.

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

На початок