5. «Швидке» сортування

Перелік алгоритмів, що розглядаються

  • швидке сортування Хоара.

Короткі теоретичні відомості

Питання для повторення

  1. Рекурсія.

Постановка задачі

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

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

Розглядається упорядкування масива a цілих чисел, занумерованих від 0 до N-1.

1.Загальна логіка алгоритму

Ідея

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

Псевдокод процедури QSort(частина масиву)
визначити опорний елемент х
здійснити перестановку
якщо у лівій частині більше 1 елемента
    то QuickSort(ліва частина)
якщо у правій частині більше 1 елемента
    то QuickSort(права частина)

2. Реалізація перестановки

Ідея
Нехай вказівники L i R такі, що всі елементи зліва від a[L] менші опорного елемента, а елементи справа від a[R] — більші опорного. Рухаючи вказівник L вправо (вказівник R вліво), знайти елемент не менший (не більший) опорного і обміняти їх місцями. Процес продовжується, доки вказівник L не опиниться правіше вказівника R.
Псевдокод
повторювати
{
  поки a[L] < x
    L = L + 1;
  поки a[R] > x
    R = R - 1;
  якщо L <= R
    то
    {
      переставити (a[l],a[r])
      L = L + 1; R = R - 1;
    }
}
доки (L > R)

Завдання для виконання

Постановка задачі

Скласти програму, що реалізує алгоритм Хоара сортування масиву, і зберегти її у власній папці. Програма повинна забезпечувати:
  • автоматичну генерацію масиву цілих чисел та виведення його на екран;
  • сортування масиву;
  • підрахунок кількості порівнянь і обмінів у процесі впорядкування.

Технічні умови

  • кількість елементів у масиві не перевищує 100;
  • елементи масиву є невід'ємними цілими числами, що не перевищують 50.

Хід роботи

  1. Скласти програму QuickSort.cpp, що забезпечує сортування масиву методом Хоара. Опорним елементом вибирається середній елемент масиву.
  2. Виконавши програму покроково для масиву 6 чисел, записати послідовність виклику процедур та скласти таблицю виконання для кожної з них.

Запитання для самоконтролю

  1. До якої категорії за визначальними принципами сортування може бути віднесений алгоритм Хоара?
  2. Сформулюйте основну ідею алгоритму Хоара.
  3. Яким чином організовується перестановка елементів відносно опорного?
  4. Поясніть, як вибір опорного елемента впливає на ефективність алгоритму.