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

Ідея швидкого сортування така. Певним чином вибирається значення v. Значення елементів масиву A обмінюються так, що елементи на його початку мають менші від v значення, а від деякого місця k значення елементів більші або рівні v. Це значення називається відокремлюючим; воно знаходиться на своєму місці, якщо A[k]=v. Після розміщення відокремлюючого значення на потрібному місці достатньо окремо відсортувати частини масиву від A[1] до A[k-1] та від A[k+1] до кінця.

Сортування частини масиву A[lo] … A[hi] з відокремлюючим значенням A[lo] задається такою процедурою: procedure quicksort ( A : ArT; lo, hi : Indx ) ; var k, j : Indx; v : T; label 1; begin if lo >= hi then goto 1; if (lo = hi - 1) and (A[lo] > A[hi]) then begin swap ( A[lo], A[hi] ); goto 1 end; k := lo + 1; j := hi; v := A[lo]; {?!} while ( k < j ) do if A[k] < v then k := k + 1 else begin if A[j] < v then swap ( A[k], A[j] ); j := j - 1 end; { k = j } if A[k] >= v then k := k - 1; { A[k] є останнім від початку елементом, } { значення якого менше v } swap ( A[lo], A[k] ); { A[k] = v } quicksort ( A , lo, k - 1 ); quicksort ( A , k + 1, hi ); 1: end

Якщо за виконання кожного виклику після циклу while значення змінної k приблизно рівне (lo+hi)/2, то складність швидкого сортування масиву з n елементів можна оцінити як O(nlogn). Середня кількість порівнянь елементів усіх можливих числових послідовностей довжини n також має оцінку O(nlogn); доведення є, наприклад, у книзі [Аху]. Емпіричні дослідження свідчать, що швидке сортування вимагає в середньому елементарних дій приблизно вдвічі менше, ніж сортування деревом, і вчетверо менше, ніж сортування злиттям. Але якщо початковий масив близький до відсортованого, то його сортування за наведеним алгоритмом вимагає вже O(n2) порівнянь. У такому випадку відокремлюючим елементом не можна вибирати значення A[lo].

Існує багато способів вибору іншого відокремлюючого значення.

Наприклад, можна вибрати значення елемента з випадковим номером серед номерів lo, … , hi, або середнє із значень A[lo], A[hi], та A[(lo+hi)div2]. У такому разі перед оператором процедури v := A[lo]; {?!} треба задати обмін значень A[lo] та відповідного елемента, чиє значення вибирається відокремлюючим. За масивом із N рядків визначається додатковий індексовий масив: попаpно pізні значення його елементів належать діапазону 1 N і є індексами в масиві рядків.

3. Порядок виконання роботи

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

2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.

3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого тексто-вого редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.

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

5. Написати контрольне опитування по темі.

6. Оформити звіт по роботі.

Без підготовкі до лабораторної роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.