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

Какво е QuickSelect?

QuickSelect е алгоритъм за избор за намиране на K-тия най-малък елемент в несортиран списък.

Обясненият алгоритъм

След намирането на пивота (позиция, която разделя списъка на две части: всеки елемент отляво е по-малък от пивота и всеки елемент отдясно е повече от пивота) алгоритъмът се повтаря само за частта, която съдържа k-тия най-малкият елемент.

Ако индексът на секционирания елемент (pivot) е повече от k, тогава алгоритъмът се повтаря за лявата част. Ако индексът (pivot) е същият като 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 

Преграда

Разделянето е да се намери въртенето, както е споменато по-горе. (Всеки елемент отляво е по-малък от ос и всеки елемент отдясно е повече от pivot) Има два алгоритъма за намиране на въртене на дяла.

  • Lomuto дял
  • Деление на Hoare

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 

Деление на Hoare

Hoare използва два индекса, които започват в краищата на масива, който се разделя, след което се придвижват един към друг, докато открият инверсия: двойка елементи, един по-голям или равен на ос, един по-малък или равен на ос, който са в грешен ред един спрямо друг.

След това обърнатите елементи се разменят. Когато индексите се срещнат, алгоритъмът спира и връща крайния индекс. Има много варианти на този алгоритъм.

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]