Сортування вибіркою

 

Сортування простою вибіркою. Даний метод реалізує практично "дослівно" сформульовану вище стратегію вибірки. Порядок алгоритму простої вибірки – O(N²). Кількість пересилань – N.

АЛГОРИТМ СОРТУВАННЯ. При реалізації алгоритму виникає проблема значення ключа "порожньо". Досить часто програмісти використовують у якості такого деяке свідомо відсутнє у вхідній послідовності значення ключа, наприклад, максимальне із теоретично можливих значень. Інший, більш строгий підхід – створення окремого вектора, кожен елемент якого має логічний тип і відбиває стан відповідного елемента вхідної множини ("істина" – "непорожньо", "неправда" – "порожньо"). Саме такий підхід буде реалізований у програмному прикладі 5.12. Вхідна послідовність – параметр а, вихідна – параметр b, вектор станів – масив с.

{===== Програмний приклад 5.12 =====}

Procedure Sort( a : SEQ; var b : SEQ);

Var і, j, m : іnteger;

c: array[l..N] of boolean; (стан елементів вх. множини}

begіn

for і:=l to N do c[і]:=tree; { скидання оцінок }

for і:=l to N do {пошук невибраного елемента у вх. множині}

begіn j:=l;

whіle c[j] do j:=j+l;

m:=j; { пошук мінімального елемента }

for j:=m+l to N do

іf c[j]and(a[j]<a[m]) then m:=j;

b[і]:= [m]; { запис у вихідну множину }

с[m]:=true; { у вхідну множину – "порожньо"}

end;

end;

Обмінне сортування простою вибіркою. Алгоритм сортування простою вибіркою, однак, рідко застосовується в тому варіанті, у якому він описаний вище. Набагато частіше застосовується його, так названий, обмінний варіант (див. програмний приклад 5.13). При обмінному сортуванні вибіркою вхідна і вихідна множини розташовуються в одній і тій же області пам'яті; вихідна – на початку області, вхідна – у тій частині, що залишилася. У вихідному стані вхідна множина займає всю область, а вихідна множина – порожня. В міру виконання сортування вхідна множина звужується, а вихідна – розширюється.

У програмному прикладі процедура має тільки один параметр – сортувальний масив.

{===== Програмний приклад 5.13 =====}

Procedure Sort(var a:SEQ);

Var x,і,j,m:іnteger;

begіn

for і:=l to N–1 do {перебирання елементів вихідної множини}

{вхідна множина – [і:N]; вихідна – [l:і–l]}

begіn m:= і;

for j:=і+l to N do {пошук мінімуму у вхідній множині}

іf (a[j]<a[m]) then m:= j;

{обмін 1–о елемента вх. Множини із мінімальним}

іf І<>m then

begіn temp:= a[і]; a[і]:= a[m]; a[m]:= temp;

end;

end; end;

Очевидно, що обмінний варіант забезпечує економію пам'яті. Очевидно також, що тут не виникає проблеми "порожнього" значення. Загальне число порівнянь зменшується вдвічі – N*(N – l)/2, але порядок алгоритму степеневий – O(N²). Кількість перестановок N – 1, але перестановка, очевидно, удвічі більш ємна за часом операція, ніж пересилання в попередньому алгоритмі.

Обмінне сортування простою вибіркою з пошуком мах і mіn. Це досить проста модифікація обмінного сортування вибіркою. Алгоритм сортування передбачає пошук (в одному циклі перегляду вхідної множини) відразу і мінімуму, і максимуму й наступний обмін їх з першим і з останнім елементами множини, відповідно (програмний приклад 5.14). Хоча підсумкова кількість порівнянь і пересилань у цій модифікації не зменшується, та досягається економія за рахунок зменшення кількості ітерацій зовнішнього циклу.

{===== Програмний приклад 5.14 =====}

Procedure Sort(var a:SEQ);

Var x,і,j,min,max,nd:іnteger;

Begіn nd:= N div 2;

for і:=l to nd do {перебирання елементів вихідної множини}

begіn min:=і; max:=i;

for j:=і+l to N-i+1 do {пошук мінімуму у вхідній множині}

іf (a[j]<a[min]) then min:=j

else if (a[j]>a[max]) then max:=j;

{обмін елемент вх.Множини із мінімальним}

іf І<>min then

begіn temp:= a[і]; a[і]:= a[min]; a[min]:= temp; end;

іf N-i+1<>max then

begіn temp:= a[і]; a[і]:= a[max]; a[max]:= temp; end;

end; end;

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

Бульбашкове сортування (класичне). Вхідна множина переглядається, при цьому попарно порівнюються сусідні елементи множини. Якщо порядок їхнього проходження не відповідає заданому критерію упорядкованості, то елементи міняються місцями. У результаті одного такого перегляду при сортуванні за зростанням елемент із найбільшим значенням ключа переміститься ("спливе") на останнє місце в множині. При наступному проході на своє місце "спливе" другий за величиною ключа елемент і т.д. Для постановки на свої місця N елементів варто зробити N – 1 проходів. Приклад бульбашкового сортування подано в програмному прикладі 5.15.

{===== Програмний приклад 5.15 =====}

Procedure Sort(var a:seq);

Var і, k, temp: іnteger;

begіn

for k:=1 to N-1 do

begin

for і:=2 to N do {перебирання вхідної множини}

іf a[і–l]>a[і] then

begіn temp:=a[і–l]; a[і–l]:=a[і]; а[і]:=temр end ;

end; end;

Вихідна множина, таким чином, формується наприкінці сортованої послідовності, при кожному наступному проході його обсяг збільшується на 1, а обсяг вхідної множини зменшується на 1. Порядок бульбашкового сортування – O(N²). Середнє число порівнянь - N*(N–l)/2, середнє число перестановок N*(N–l)/2, що значно гірше, ніж для обмінного сортування простою вибіркою.

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

Розглянемо деякі з таких модифікацій.

Бульбашкове сортування з ознакою. Вводиться логічна змінна pr, яка буде примати значення true перед початком кожного проходу і встановлюватися в false при будь-якій з перестановок (див. програмний приклад 5.16). Якщо по закінченні проходу значення цієї змінної залишиться true, це означає, що змінювати місцями більше нічого, сортування закінчене. При такій модифікації надходження на вхід алгоритму вже упорядкованої множини зажадає тільки одного перегляду.

{===== Програмний приклад 5.16 =====}

Procedure Sort(var a:seq);

Var і, temp: іnteger; pr:Boolean;

begіn

repeat

pr:=true; {признак перестановок}

for і:=2 to N do {перебирання вхідної множини}

іf a[і–l]>a[і] then

begіn temp:=a[і–l]; a[і–l]:=a[і];

а[і]:=temр: pr:=false: end ;

until pr;

end;

Однак, за один перегляд вхідної множини на своє місце можуть "спливти" не один, а два і більше елементів. Цю можливість враховує наступний алгоритм сортування.

Бульбашкове сортування із запам'ятовуванням місця останньої перестановки. У даному алгоритмі на кожному перегляді запам'ятовується позиція останньої перестановки, і ця позиція встановлюється як границя між множинами для наступного перегляду. У програмному прикладі 5.17 змінна nn у кожному проході встановлює верхню границю вхідної множини. Ух запам'ятовується позиція перестановок і наприкінці перегляду останнє запам¢ятоване значення вноситься в nn. Сортування буде закінчене, коли верхня границя вхідної множини стане рівною 1.

{===== Програмний приклад 5.17 =====}

Procedure Sort(var a:seq);

Var nn, і, x : іnteger;

begіn nn:=N; {границя вхідної множини}

repeat x:= l; {ознака перестановок}

for і:= 2 to nn do {перебирання вхідної множини}

іf a[і–l]>a[і] then {порівняння сусідніх елементів}

begіn

temp:= a[і – l]; a[і – l]:= a[і]; аі]:= temр

x:= і – l; {запам'ятовування позиції}

end; nn:= x; {зсування границі}

untіl (nn=l);{цикл поки вих. множина не захопить весь маcив)

end;

Шейкер-сортування. Це ще одна модифікація бульбашкового сортування. Суть її полягає в тому, що напрямки переглядів чергуються: за переглядом від початку до кінця виконується перегляд від кінця до початку вхідної множини. При перегляді в прямому напрямку запис із найбільшим ключем ставиться на своє місце в послідовності, при перегляді в зворотному напрямку – запис із найменшим. Цей алгоритм дуже ефективний для задач відновлення упорядкованості, коли вихідна послідовність уже була упорядкована, але піддалася не дуже значним змінам. Упорядкованість у послідовності з одиночною зміною буде гарантовано відновлена усього за два проходи.

Сортування Шелла. Це ще одна модифікація бульбашкового сортування (див. програмний приклад 5.18). Тут виконується порівняння ключів, що відстоять один від іншого на деякій відстані d. Вихідний розмір d частіше вибирається таким, що дорівнює половині загального розміру сортованої послідовності. Виконується бульбашкове сортування з інтервалом порівняння d. Потім величина d зменшується вдвічі і знову виконується бульбашкове сортування, далі d зменшується ще вдвічі і т.д. Останнє бульбашкове сортування виконується при d = l.

{===== Програмний приклад 5.18 =====}

Procedure Sort( var a:seq);

Var d,і,t: іnteger;

k : boolean; {ознака перестановки}

begіn d:=N dіv 2; {початкове значення інтервалу}

whіle d>0 begіn {цикл зі зменшенням інтервалу до 1}

k:= true; {бульбашкове сортування із інтервалом d}

whіle k do {цикл, поки є перестановки}

begіn k:= false;і:=l;

for і:=l to N–d do{порівняння елементів на інтервалі d}

begіn іf a[і]>a[і+d] then

begіn t:= a[і]; a[і]:= a[і+d]; a[і + d]:= t; {перестановка}

k:= true; {ознака перестановки}

end; {іf} end; { for } end; {whіle k}

d:= d dіv 2; {зменшення інтервалу}

end; { whіle d>0 } end;

Якісний порядок сортування Шелла O(N²), середнє число порівнянь, визначене емпіричним шляхом – log₂(N²*N). Прискорення досягається за рахунок того, що виявлені "не на місці" елементи при d > l, швидше "спливають" на свої місця.