Теоретичні відомості

Розглянемо npocтi алгоритми упорядкування (сортування) одновимірних таблиць. Мета сортування - полегшити наступний пошук елементів. Bи6ip алгоритму сортування залежить від структури оброблюваного списку. Критеріями ефективності сортування є швидкодія й економія пам'яті, що може бути важливим у разі великих списків.

Метод прямого вибору.Скажімо, вам потрібно з вихідної послідовності А [i], що складається з N елементів, утворити спадну послідовність (точніше, послідовність з незростаючих елементів). Зафіксуємо перший елемент i переглянемо інший масив (N-і) елементів, відшукавши в ньому найбільший. Якщо цей елемент виявиться більшим від першого, поміняємо його місцями з першим елементом. Потім зафіксуємо елемент 2 i переглянемо (N-2) елементи, що залишились. Знайшовши найбільший елемент, поміняемо його з елементом 2. Подібну процедуру продовжуватимемо, поки не залишиться один, найбільший, елемент.

Наведемо програму мовою Pascal, що здійснює сортування масиву з 5 еле-ментів (рядків) методом прямого вибору:

Program SortSelect;

const Num=5;

A:array[l..Num] of string=('ca','aa','d^і,'a','ab^і);

Var Temp:string; I,J,L:integer;

begin

Writeln ('Начальный массив');

for I:=l to Num do

Write (' ' ,A[I] ) ;

Writeln; Writeln;

for I:=l to Num-і do

for J:=I+і to Num do

begin

if A[I]<A[J] then

begin

Temp:=A[I]; A[I]:=A[J]; A[J]:=Temp;

end;

for L:=l to Num do Write(' ',A[L]); Writeln;
end; end.

Процес сортування в цьому прикладі проілюструємо виведенням одержуваної послідовності елементів після кожної операції порівняння.

Неважко підрахувати, що кількість операцій порівняння в методі прямого вибору дорівнюватиме числу комбінацій з Nmах по 2, тобто Nmax!/ (2! (Nmax-2) !), де Nmax - розмір початкового масиву.