Головна

алгоритм

  1.  IX. Єдиний алгоритм синтезу нових понять зі старих
  2.  алгоритм
  3.  алгоритм
  4.  алгоритм
  5.  Алгоритм - це
  6.  Алгоритм Calc.

Quicksort є швидким алгоритмом сортування, який вирішує завдання використовуючи проблему divide-and-conquer (розділяй і володарюй). Quicksort це рекурсія призводить масив елементів до елементарного виду, тобто коли алгоритм рекурсивно ділить масив на менші і ще більш менші масиви. Quicksort сортує ці дуже маленькі масиви і комбінує результати створюючи сортовану версію вихідного масиву. Через рекурсивного характеру реалізацію quicksort кілька важко зрозуміти. Перш, ніж досліджувати реалізацію, ми спочатку розглянемо ідею алгоритму.

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

  1. Якщо розмір масиву дорівнює нулю або містить один елемент, то масив відсортований. Це і є основною випадок.
  2. Виберіть елемент в середині масиву, щоб використовувати його в якості центру. Це - крок вибору центру.
  3. Створіть два нових масиву. Помістіть всі елементи, які є меншими ніж елемент центру в один з подмассивов, що залишилися елементи в інший подмассів. Це - крок поділу.
  4. У підмасиві, який містить елементи менше ніж центральний, ще раз розділіть через вже його центр ще на два подмассіва (повтор кроків 2 і 3). Це - рекурсивний крок поділу.

Розглянемо рішення задачі на прикладі. Звернемося до рис. 1.


 Малюнок 1 несортоване масив

Так як масив на малюнку 1 містить більше ніж один елемент, quicksort починає роботу з кроку 2, вибору центру. Є багато різних стратегій, які ми можемо використовувати, щоб вибрати елемент центру. Зупинимося на найпростішому, що включає вибір середнього елемента масиву як елемент центру. Цей елемент містить значення 33. Після вибору елемента центру quicksort ділить залишаються елементи в два подмассіва. Один подмассів містить елементи розділеного масиву, значення якого є менше ніж 33, Інший подмассів містить елементи, значення яких більше ніж 33. Малюнок 2 ілюструє цей крок розділу. Тут на малюнку коло позначає елемент центру.


 Малюнок 2 Вибір центру і розділ

У першому підмасиві створимо ще два менших ще менших подмассіва. Quicksort алгоритм рекурсивно викликає себе в цих подмассіви. Зауважте, що обидва з цих масивів містять два або більше елемента. Тому, алгоритм вибирає елементи центру для кожного масиву і ділить їх залишаються елементи в менші масиви. Результат ділення наведено на малюнку 3.


 Малюнок 3 Друге поділ рівня

Quicksort алгоритм повинен тільки вибрати елементи центру, які містять більше ніж один елемент. Тепер в полі зору у нас чотири подмассіва, вони на малюнку 3 в нижньому ряду. Зчитуючи числа з ліво на право, бачимо, перший подмассів містить тільки один елемент зі значенням 3. Другий подмассів містить елементи 12 и 21, І третій подмассів містить елементи 52 и 53. Четвертий подмассів містить нуль елементів. Знак порожнього безлічі (коло з діагональною рискою) позначає, що цей подмассів містить нуль елементів. Quicksort алгоритм не чіпає перший і четвертий подмассіви, так як кожен з них містить менше ніж два елементи (Див. Крок 1). У цій точці ці два подмассіва вважаються вже відсортованими. Так як другий і третій масиви, містять більше ніж один елемент, то, ймовірно, вони не знаходяться в відсортованому порядку. Quicksort повинен рекурсивно розглянути їх і розділити на подмассіви, см рис. 4, нижня рядок.


 Малюнок 4 Після останнього необхідного розділу

Рекурсивна природа quicksort розділяє вихідний масив на ще менші подмассіви. В кінцевому рахунку поділ призводить до остаточної сортування всього масиву. Малюнок 5 зображує відсортовану версію вихідного масиву.


 Малюнок 5 Сортований масив




 Binary Search |  Selection Sort |  Binary пошук |  Використання функції сортування STL |  Короткий огляд Хеш-таблиць |  Хеш-функції |  The Algorithm |  An Implementation |  Using the STL Sorting Functions |  Overview of Hash Tables |

© um.co.ua - учбові матеріали та реферати