Курсовая работа: Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів

end

End ;

Аналіз алгоритму Quick Sort. Щобоцінитиефективністьалгоритму, позначимочерезQ(N) середнюкількістькроків, необхіднихдлявпорядкуванняN елементів. Припустимо також, S=1 , тобто не використовується сортування прямими методами на коротких послідовностях.

При першому проходженні Quick Sort порівнює всі елементи з ведучим і виконується не більше ніж за C*N кроків, де C - деяка константа. Потім потрібно відсортувати дві підпослідовності довжинами I-1 та N-I . Тому середня кількість кроків, потрібних для впорядкування N елементів, залежить від середньої кількості кроків, потрібних для впорядкування I-1 та N-I елементів відповідно. Оскільки всі можливі значення є рівноймовірними, то спрведлива наступна оцінка :

.

Врахувавши, що

,

отримаємо

.(1)

Покажемо за індукцією по N , що для , де K=2C+2B , B=Q(0)=Q(1) . Останнє співвіднощення означає, що Quick Sort вимагає постійної однакової кількості кроків для впорядкування 0 або 1 елемента.

1) N=2 : ;

2) припустимо, що для I=2, 3, ..., N-1 ;

3) перевіримо справедливість для I=N . Співвідношення (1) з врахуванням попереднього припущення можна переписати у вигляді

або

.(2)

Оскільки функція I*ln(I) є опуклою вниз, то для цілих значень аргументу справедлива оцінка

Врахувавши останню нерівність, із співвідношення (2) одержимо

.

Оскільки , то

.

Остаточно отримаємо

.(3)

Таким чином ефективність алгоритму Quick Sort є величина порядку O(N*ln(N)).

Всі наведені викладки справедливі для аналізу по операціях порівняння. Кількість же перестановок залежить від початкового розміщення елементів у послідовності. Характерно, що для цього методу у випадку зворотньо впорядкованого масиву об’єм переміщень ключів не буде максимальним. Адже на кожному етапі ведучий елемент буде найбільшим і опиниться на своєму місці після першого ж порівняння і перестановки, тобто M=N-1 . Максимальна кількість переприсвоєнь ключів співпадатиме з кількістю порівнянь, мінімальна - рівна нулю.

Алгоритм Quick Sort, як і розглянуті прямі методи, описує процес стійкого сортування.

2.3 Сортування вибором при допомозі дерева – алгоритм Тree Sort

Алгоритм сортування деревом ТreeSort власне кажучи є поліпшенням алгоритму сортування вибором. Процедура вибору найменшого елемента удосконалена як процедура побудови так званого сортуючого дерева. Сортуюче дерево - це структура даних, у якій представлений процес пошуку найменшого елемента методом попарного порівняння елементів, що стоять поруч. Алгоритм сортує масив у два етапи.

I етап : побудова сортуючого дерева;