Лекція "Покращені методи сортування"

Лекція № 6

Тема: Покращені методи сортування

Мета: Ознайомити студентів з покращеними методами сортування масивів, алгоритмами сортування, аналізом їх швидкодії і кількості використаних операцій та обміну.

 

План

1. Сортування злиттям.
2. Швидке сортування.
3. Сортування Шелла.

 

Навчально-методичне забезпечення, ТЗН: конспект лекцій.

 

Література:

1. [2] стор. 294-300.
2. [3] стор. 89-97.

ВИКЛАД ЛЕКЦІЙНОГО МАТЕРІАЛУ

 

1. Сортування злиття

 

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

Ідея методу

1)  Послідовність а розіб’ємо на дві частини b i c.

2)  Частини  b  i  c  зливатимемо,  при  цьому  одиночні  елементи

утворюватимуть упорядковані пари.

3)  Одержана послідовність під іменем а знову обробляється, але

упорядковані пари заміняються четвірками.

4)  Повторюючи попепердні кроки, зливаємо четвірки у вісьмірки і т.д.,

кожний раз подвоюючи довжину злитих підпослідовностей до того

часу, доки не буде упорядкована вся послідовність.

Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу.

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

Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.

а) Процедура злиття впорядкованих частин масиву у буфер-проміжний масив

temp з подальшим перенесенням вмісту temp в a[left]...a[right]

void merge(int a[], long left, long split, long right) {

long pos1=left; // поточна позиція читання з першої

послідовності a[left]...a[split]

long pos2=split+1; // поточна позиція читання з другої

послідовності a[split+1]...a[right]

long pos3=0;  // поточна позиція запису в temp

int *temp;

temp = new int[right-left+1];

23

// продовжується злиття, поки є хоча б один елемент в кожній

послідовності while (pos1 <= split && pos2 <= right)

{

if (a[pos1] < a[pos2]) { temp[pos3] = a[pos1]; pos3++;pos1++;}

else {temp[pos3] = a[pos2];  pos3=pos3++;pos2++;}

}

//  одна послідовність закінчилась- копіювати залишок іншої в

кінець буфера

while (pos1 <= split) // поки перша послідовність непорожня

{ temp[pos3] = a[pos1]; pos3++;pos1++;}

while (pos2 <= right) // пока друга послідовність непорожня

{ temp[pos3] = a[pos2]; pos3++; pos2++; }

// скопіювати буфер temp в a[left]...a[right]

for (pos3 = 0; pos3 < right-left+1; pos3++)

a[left+pos3] = temp[pos3];

delete [] temp;

}

б) Процедура безпосереднього впорядкування масиву

void mergeSort(int a[], long left, long right) {

long split;  // індекс, за яким ділимо масив

if (left<right)// якщо є більше, ніж 1 елемент

{

split = (left + right)/2;

mergeSort(a, left, split); // сортувати ліву половину

????????????????????????? // сортувати праву половину

merge(a, left, split, right);  // об’єднати масиви в один

}

}

Код сортування злиттям:

#include <stdio. h>

#include <conio. h>

#include <stdlib. h>

#include <time. h>

 // Merge-----------------------------------------------------------------

void merge (int *a, int l, int m, int r)

{

int h, i,j,b [10000],k;

h=l;

i=l;

j=m+1;

while ( (h<=m) && (j<=r))

{

if (a [h] <=a [j])

{

b [i] =a [h];

h++;

}

else

{

b [i] =a [j];

j++;

}

i++;

}

if (h>m)

{

for (k=j; k<=r; k++)

{

b [i] =a [k];

i++;

}

}

else

{

for (k=h; k<=m; k++)

{

b [i] =a [k];

i++;

}

}

for (k=l; k<=r; k++) {a [k] =b [k]; }

}

void MergeSort (int *a, int l, int r)

{

int m;

if (l<r)

{

m= (l+r) /2;

MergeSort (a,l,m);

MergeSort (a,m+1,r);

merge (a,l,m,r);

}

}

 // ----------------------------------------------------------------------

void main ()

{

FILE *f,*rez;

int *X, N;

clock_t start, end;

clrscr ();

f=fopen ("massiv. txt","rt");

N=0;

while (! feof (f))

{

fscanf (f,"%d",X+N);

N++;

}

fclose (f);

start= clock ();

MergeSort (X,0,N-1);

end= clock ();

printf ("The time was:%f s\n", (end - start) / CLK_TCK);

rez=fopen ("rezult. txt","wt");

for (int i=0; i<N; i++)

fprintf (rez,"%d\n",* (X+i));

fclose (rez);

getch ();

}

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

 

Швидке сортування (англ. Quick Sort) - алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Хоаром, який не потребує додаткової пам'яті і виконує у середньому O (n log (n)) операцій. Однак, у найгіршому випадку робить O (n²) порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності.

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

Опис алгоритму:

вибрати елемент, званий опорним.

порівняти всі інші елементи з опорним, на підставі порівняння розбити безліч на три - «менші опорного», «рівні» та «великі», розташувати їх у порядку менші-рівні-великі.

повторити рекурсивно для «менших» і «великих».

Швидке сортування

Метод заснований на підході «розділяй і володарюй». Загальна схема така:

1)  із масиву вибираєтся деякий опорний елемент a[i];

2)  запускаєтся процедура розділення масиву, яка переміщує всі ключі,

менші, або рівні a[i], вліво від нього, а всі ключі, більші, або рівніa[i] –

вправо;

A[2i]  A[2i+1]

A[i]

21

3)  тепер масив складається із двох підмножин, причому ліва менша, або

рівна правій;

4)  для обох підмасивів: якщо в підмасиві більше двух елементів,

рекурсивно запускаємо для нього ту же процедуру.

В кінці отримаємо повністю відсортовану послідовність.

Примітка: на практиці звичайно поділяють сортовані безліч не на три, а на дві частини: наприклад, «менші опорного» і «рівні і великі». Такий підхід в загальному випадку виявляється ефективніше, тому що для здійснення такого поділу достатньо одного проходу по сортованому безлічі і однократного обміну лише деяких обраних елементів.

Швидке сортування є алгоритмом на основі порівнянь, і не є стабільним.

Швидке сортування, придумана Ч. А. Р. Хоаром^[9] (CharlesAntonyRichardHoare) і названа його ім'ям, є самим кращим методом сортування з представлених в цій книзі і зазвичай вважається кращим з існуючих нині алгоритмом сортування загального призначення. У її основі лежить сортування обмінами — дивовижний факт, враховуючи жахливу продуктивність бульбашкового сортування!

Швидке сортування побудоване на ідеї ділення. Загальна процедура полягає в тому, щоб вибрати деяке значення, що називається компарандом(comparand)^[10], а потім розбити масив на дві частини. Усі елементи, великі або рівні компаранду, переміщаються на одну сторону, а менші — на іншу. Потім цей процес повторюється для кожної частини до тих пір, поки масив не буде відсортований. Наприклад, якщо початковий масив складається з символів fedacb, а як компаранда використовується символ d, перший прохід швидкого сортування переупорядкує масив таким чином:

Початок      f e d a c b

 

Прохід 1     b c a d e f

Потім сортування повторюється для обох половин масиву, тобто bса і def. Як ви бачите, цей процес за своєю суттю рекурсивний, і, дійсно, в чистому вигляді швидке сортування реалізується як рекурсивна функція^[11].

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

/* Функція, викликаюча функцію швидкого сортування. */

voidquick(char *items, intcount)

{

qs(items, 0, count-1);

}

 

/* Швидке сортування. */

voidqs(char *items, intleft, intright)

{

registerint i, j;

char x, y;

 

  i = left; j = right;

  x = items[(left+right)/2]; /* вибір компаранда */

 

do {

while((items[i] < x) && (i <right)) i++;

while((x <items[j]) && (j >left)) j--;

 

if(i <= j) {

      y = items[i];

items[i] = items[j];

items[j] = y;

      i++; j--;

    }

  } while(i <= j);

 

if(left< j) qs(items, left, j);

if(i <right) qs(items, i, right);

}

У цій версії функція quick() готує виклик головної сортуючоїфункції qs(). Це забезпечує загальний інтерфейс з параметрами items і count, але несуттєво, оскільки можна викликати безпосередньо функцію qs() з трьома аргументами.

Компаранд — операнд в операції порівняння. Іноді називається також основою і критерієм розбиття.

Переваги:

Один з найбільш швидкодіючих (на практиці) з алгоритмів внутрішнього сортування загального призначення.

Простий в реалізації.

Потребує лише додаткової пам'яті для своєї роботи. (Не покращений рекурсивний алгоритм у гіршому випадку пам'яті)

Добре поєднується з механізмами кешування і віртуальної пам'яті.

Існує ефективна модифікація (алгоритм Седжвіка) для сортування рядків - спочатку порівняння з опорним елементом тільки за нульовим символу рядка, далі застосування аналогічної сортування для «більшого» і «меншого» масивів теж за нульовим символу, і для «рівного» масиву по вже першого символу .

 

Недоліки:

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

Наївна реалізація алгоритму може привести до помилки переповнення стека, так як їй може знадобитися зробити вкладених рекурсивних викликів.

Швидке впорядкування

void quickSort(int a[], long N) {

// На вході - масив a[], N – номер останнього елемента.

long i = 0, j = N; // поставити вказівники а початкові місця

int temp, p;

p = a[ N>>1 ]; // центральний елемент

// процедура розділення

do {

while ( a[i] < p ) i++;

while ( a[j] > p ) j--;

if (i<= j) ?????здійснити обмін елементами

} while ( i<=j );

//  рекурсивні виклики, якщо є, що сортувати

if ( j > 0 ) quickSort(a, j);

if ( N >i ) quickSort(a+i, N-i);

}

 

Код сортування злиттям:

 

#include <stdio. h>

#include <conio. h>

#include <stdlib. h>

#include <time. h>

 // ----------------------------------------------------------------------

void QuickSort (int *arr, int a, int b)

{

int i=a, j=b, m = rand ()% (b-a) +a;

int x = * (arr+m);

do

{

while (i<=b && * (arr+i) < x) i++;

while (j>=a && * (arr+j) > x) j--;

if (i <= j)

{

if (i < j)

{

int buf=* (arr+i);

* (arr+i) =* (arr+j);

* (arr+j) =buf;

}

i++;

j--;

}

} while (i <= j);

if (i < b) QuickSort (arr, i,b);

if (a < j) QuickSort (arr,a,j);

}

 // ---------------------------------------------------------------------

void main ()

{

FILE *f;

int *X, N;

clock_t start, end;

N=0;

f=fopen ("massiv. txt","rt");

start= clock ();

while (! feof (f))

{

fscanf (f,"%d",X+N);

N++;

}

QuickSort (X,0,N-1);

end= clock ();

printf ("The time was:%f s\n", (end - start) / CLK_TCK);

start= clock ();

fclose (f);

getch ();

}

 

3. Сортування Шелла

 

Сортування Шелла називається так по імені свого автора, Дональда Л. Шелла (DonaldLewisShell)^[4]. Проте ця назва закріпилася, ймовірно, також тому, що дія цього методу часто ілюструється рядами морських раковин, що перекривають один одного (по-англійськи "shell" — "раковина"). Загальна ідея запозичена з сортування вставками і грунтується на зменшенні кроків. Розглянемо діаграму на мал.. Спочатку сортуються усі елементи, віддалені один від одного на три позиції. Потім сортуються елементи, розташовані на відстані двох позицій. Нарешті, сортуються усі сусідні елементи.

Прохід 1     f   d   a   c   b   e              \___\___\___/   /   /                   \___\_____/   /                        \_______/   Прохід 2     c   b   a   f   d   e              \___\___|___|___/   /                   \______|______/         Прохід 3     a   b   c   d   e   f              |___|___|___|___|___|     Результат    a   b   c   d   e   f

Мал. 21.2. Сортування Шелла

Те, що цей метод дає добрі результати, або навіть те, що він взагалі сортує масив, побачити не так просто. Проте, це вірно. Кожен прохід сортування поширюється на відносно невелику кількість елементів або на елементи, розташовані вже у відносному порядку. Тому сортування Шелла ефективне, а кожен прохід підвищує впорядкованість^[6].

Конкретна послідовність кроків може бути і інший. Єдине правило полягає в тому, щоб останній крок дорівнював 1. Наприклад, така послідовність:

9, 5, 3, 2, 1

дає добрі результати і застосовується в показаній тут реалізації сортування Шелла. Слід уникати послідовностей, які є мірами числа 2 — з математично складних міркувань вони зменшують ефективність сортування (але сортування як і раніше працює!).

/* Сортування Шелла. */

voidshell(char *items, intcount)

{

 

registerint i, j, gap, k;

char x, a[5];

 

  a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;

 

for(k=0; k < 5; k++) {

gap = a[k];

for(i=gap; i <count; ++i) {

      x = items[i];

for(j=i-gap; (x <items[j]) && (j >= 0); j=j-gap)

items[j+gap] = items[j];

items[j+gap] = x;

    }

  }

}

Ви могли помітити, що внутрішній цикл for має дві умови перевірки. Очевидно, що порівняння x<items[j] необхідно для процесу сортування. Вираження j>=0 запобігає виходу за кордон масиву items. Ці додаткові перевірки в деякій мірі знижують продуктивність сортування Шелла.

У злегка модифікованих версіях цього методу сортування застосовуються спеціальні елементи масиву, що називаються сигнальними мітками. Вони не належать до власне сортованого масиву, а містять спеціальні значення, що відповідають найменшому можливому і найбільшому можливому елементам^[7]. Це усуває необхідність перевірки виходу за межі масиву. Проте застосування сигнальних міток елементів вимагає конкретної інформації про сортовані дані, що зменшує універсальність функції сортування.

2.2 Сортування методом Шелла

Сортування Шелла є досить цікавою модифікацією алгоритму сортування простими вставками.

Розглянемо наступний алгоритм сортування масиву a [0] .. a [15] (Рис.2.3).

 

Рисунок 2.3 – Початковий стан масиву а

 

Спочатку сортуємо простими вставками кожні 8 груп з 2-х елементів (a [0], a [8 [), (a [1], a [9]), ... , (а [7], a [15]) (Рис. 5.4).

 

Рисунок 2.4 – Схема роботи методу сортування Шелла

 

Потім сортуємо кожну з чотирьох груп по 4 елемента (a [0], a [4], a [8], a [12]), ..., (a [3], a [7], a [11] , a [15]) (Рис. 2.5).

 

Рисунок 2.5 – Другий шаг сортування

 

В нульової групи будуть елементи 4, 12, 13, 18, в першій - 3, 5, 8, 9 тощо.

Далі сортуємо 2 групи по 8 елементів, починаючи з (a [0], a [2], a [4], a [6], a [8], a [10], a [12], a [14] ) (Рис. 2.6).

 

Рисунок 2.6 – Сортування груп елементів

 

В кінці сортуємо вставками всі 16 елементів (Рис. 2.7).

 

Рисунок 2.7 – Результат сортування методом Шелла

 

Очевидно, лише останнє сортування необхідне, щоб розташувати всі елементи по своїх місцях. Так навіщо потрібні інші?

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

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

 

Контрольні запитання

1. Дати характеристику сортування злиттям.
2. Описати швидке сортування.
3. Пояснити сортування Шелла.