„QuickSelect“: „Quick Select“ algoritmas, paaiškintas kodo pavyzdžiais

Kas yra „QuickSelect“?

„QuickSelect“ yra pasirinkimo algoritmas, skirtas surasti K-ąjį mažiausią elementą nerūšiuotame sąraše.

Algoritmas paaiškintas

Suradęs suvestį (poziciją, padalijančią sąrašą į dvi dalis: kiekvienas kairėje esantis elementas yra mažesnis už pasukimą, o kiekvienas elementas dešinėje - daugiau nei pasisukimo taškas), algoritmas kartojasi tik tai daliai, kurioje yra k mažiausias elementas.

Jei skaidinio elemento (pasukimo) indeksas yra didesnis nei k, kairiosios dalies algoritmas kartojasi. Jei indeksas (pivot) yra toks pat kaip k, tada mes radome k-ąjį mažiausią elementą ir jis grąžinamas. Jei indeksas yra mažesnis nei k, algoritmas pasikartoja dešinėje.

Psudokodo pasirinkimas

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 

Padalijimas

Skirstymas yra surasti šarnyrą, kaip minėta aukščiau. (Kiekvienas kairėje esantis elementas yra mažesnis nei „pivot“, o kiekvienas dešinėje esantis elementas yra didesnis nei „pivot“) Skirstymo posūkio radimui yra du algoritmai.

  • „Lomuto“ skaidinys
  • „Hoare“ skaidinys

„Lomuto“ skaidinys

Šis skaidinys pasirenka suvestinę, kuri paprastai yra paskutinis masyvo elementas. Algoritmas palaiko indeksą i, kai jis nuskaito masyvą naudodamas kitą indeksą j taip, kad elementai nuo lo iki i (imtinai) būtų mažesni arba lygūs pivotui, o elementai i + 1 iki j-1 (imtinai) būtų didesni už sukimasis.

Ši schema pablogėja, O(n^2)kai masyvas jau yra tvarkingas.

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“ skaidinys

Hoare'as naudoja du indeksus, kurie prasideda skaidomo masyvo galuose, tada juda vienas kito link tol, kol aptinka inversiją: elementų pora, viena didesnė už pivot arba didesnė, kita mažesnė arba lygi pivot, yra neteisinga tvarka viena kitos atžvilgiu.

Tada apversti elementai keičiami. Kai indeksai susitinka, algoritmas sustoja ir grąžina galutinį indeksą. Yra daug šio algoritmo variantų.

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]