QuickSelect: Алгоритм швидкого вибору, пояснений прикладами коду

Що таке QuickSelect?

QuickSelect - це алгоритм вибору, щоб знайти K-й найменший елемент у несортованому списку.

Пояснений алгоритм

Після пошуку стержня (позиція, яка розділяє список на дві частини: кожен елемент ліворуч менше, ніж півот, а кожен елемент праворуч більше, ніж півот), алгоритм повторюється лише для тієї частини, яка містить k-й найменший елемент.

Якщо індекс розділеного елемента (опорного) більше, ніж k, тоді алгоритм повторюється для лівої частини. Якщо індекс (опорна точка) збігається з k, то ми знайшли k-й найменший елемент і він повертається. Якщо індекс менше k, тоді алгоритм повторюється для правої частини.

Вибір псевдокоду

Input : List, left is first position of list, right is last position of list and k is k-th smallest element. Output : A new list is partitioned. quickSelect(list, left, right, k) if left = right return list[left] // Select a pivotIndex between left and right pivotIndex := partition(list, left, right, pivotIndex) if k = pivotIndex return list[k] else if k < pivotIndex right := pivotIndex - 1 else left := pivotIndex + 1 

Перегородка

Розділ полягає у пошуку стержня, як згадувалося вище. (Кожен елемент ліворуч менше, ніж півот, а кожен елемент праворуч більше, ніж півот.) Існує два алгоритми для пошуку стержня розділу.

  • Розділ Lomuto
  • Розділ Хоара

Розділ Lomuto

Цей розділ вибирає зведення, яке, як правило, є останнім елементом масиву. Алгоритм підтримує індекс i, оскільки він сканує масив, використовуючи інший індекс j, такий що елементи від lo до i (включно) менше або дорівнюють повороту, а елементи i + 1 - j-1 (включно) більше, ніж поворот.

Ця схема погіршується, O(n^2)коли масив уже впорядкований.

algorithm Lomuto(A, lo, hi) is pivot := A[hi] i := lo for j := lo to hi - 1 do if A[j] < pivot then if i != j then swap A[i] with A[j] i := i + 1 swap A[i] with A[hi] return i 

Розділ Хоара

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

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

algorithm Hoare(A, lo, hi) is pivot := A[lo] i := lo - 1 j := hi + 1 loop forever do i := i + 1 while A[i]  pivot if i >= j then return j swap A[i] with A[j]