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

І Автор цього метода Ч. Хоар назвав його швидким сортуванням, оскільки для біль шості масивів цей метод потребує приблизно (n/6) log n обмінів елементів і п log п порівнянь, тобто набагато менше, ніж будь-який з елементарних методів. Метод функціонує за принципом «розділяй та пануй»: елементи масиву діляться на дві частини, і кожна з них потім сортується окремо. Для цього обирають деякий елемент х, назвемо його розділовим. Мета полягає у розташуванні всіх менших за х елементів зліва від х, а всіх більших за х елементів — справа від х. Поділивши масив, слід повторити процедуру сортування для кожної частини, потім — для частин цих частин і т. д., доки кожна з частин масиву не міститиме лише один елемент. Зауважимо, що у деяких модифікаціях методу Хоара розташування та значення розділового елемента можуть змінюватися під час розподілу елементів. Розглянемо одну з таких модифікацій.

Отже, алгоритм методу Хоара є рекурсивним і для його реалізації було б зручно застосувати рекурсивну процедуру. Параметрами цієї процедури будуть змінні left та right, що позначатимуть ліву та праву межу розглядуваної частини масиву. Розділовим елементом вважатимемо середній за номером елемент частини масиву і присвоїмо значення цього елемента змінній х. Рекурсивний виклик процедури для поділу лівого підмасиву на дві частини здійснюється в тому разі, як­що ліва межа підмасиву менша за індекс його середнього елемента, а для поділу правого підмасиву — якщо права межа більша за індекс середнього елемента. Для поділу елементів на дві частини застосовуємо два цикли while у середині циклу repeat-until. На кожній ітерації зовнішнього циклу здійснюватиметься один об­мін елементами між лівою та правою частинами. Внутрішні цикли (здійснюють перегляд масиву зліва та справа) призначені для знаходження чергової пари еле­ментів, що мають бути переставлені. Зазначимо, що переставленим може бути і сам розділовий елемент, при цьому він може втратити властивість розділовості. Цей факт не впливає на коректність роботи розглянутої далі програми.