Szybki wybór - Quickselect

Szybki wybór

Animowana wizualizacja algorytmu szybkiego wyboru. Wybór 22. najmniejszej wartości.
Klasa	Algorytm wyboru
Struktura danych	Szyk
Wydajność w najgorszym przypadku	О( n 2 )
Wydajność w najlepszym przypadku	( n )
Średnia wydajność	O( n )

W informatyce , quickselect jest algorytm wyboru , aby znaleźć k th najmniejszego elementu w liście nieuporządkowanej. Jest to związane z algorytmem sortowania quicksort . Podobnie jak quicksort, został opracowany przez Tony'ego Hoare'a i dlatego jest również znany jako algorytm wyboru Hoare'a . Podobnie jak sortowanie szybkie, jest wydajny w praktyce i ma dobrą wydajność w średnim przypadku, ale ma słabą wydajność w najgorszym przypadku. Quickselect i jego warianty to algorytmy selekcji najczęściej wykorzystywane w wydajnych implementacjach rzeczywistych.

Quickselect wykorzystuje to samo ogólne podejście, co quicksort, wybierając jeden element jako element przestawny i dzieląc dane na dwa na podstawie elementu przestawnego, odpowiednio jako mniejsze lub większe od elementu przestawnego. Jednak zamiast rekurencji w obie strony, jak w quicksort, quickselect powraca tylko w jedną stronę – stronę z elementem, którego szuka. Zmniejsza to średnią złożoność z do , w najgorszym przypadku . ${\ Displaystyle O (n \ log n)}$${\ Displaystyle O (n)}$${\ Displaystyle O (n ^ {2})}$

Podobnie jak w przypadku quicksort, quickselect jest na ogół implementowany jako algorytm w miejscu i poza wybraniem k- tego elementu, również częściowo sortuje dane. Zobacz algorytm selekcji w celu dalszej dyskusji na temat związku z sortowaniem.

Algorytm

W quicksort istnieje podprocedura o nazwie, partitionktóra może, w czasie liniowym, pogrupować listę (od indeksów leftdo right) na dwie części: te mniejsze niż pewien element i większe lub równe elementowi. Oto pseudokod, który wykonuje partycję o elemencie list[pivotIndex]:

function partition(list, left, right, pivotIndex) is
    pivotValue := list[pivotIndex]
    swap list[pivotIndex] and list[right]  // Move pivot to end
    storeIndex := left
    for i from left to right − 1 do
        if list[i] < pivotValue then
            swap list[storeIndex] and list[i]
            increment storeIndex
    swap list[right] and list[storeIndex]  // Move pivot to its final place
    return storeIndex

Jest to znane jako schemat partycji Lomuto , który jest prostszy, ale mniej wydajny niż oryginalny schemat partycji Hoare'a .

W quicksort sortujemy rekurencyjnie obie gałęzie, co prowadzi do najlepszego czasu. Jednak podczas selekcji wiemy już, w której partycji znajduje się nasz pożądany element, ponieważ element obrotowy znajduje się w końcowej pozycji posortowanej, ze wszystkimi poprzedzającymi go w kolejności nieposortowanej i wszystkimi następującymi po nim w kolejności nieposortowanej. Dlatego pojedyncze wywołanie rekurencyjne lokalizuje żądany element we właściwej partycji i budujemy na tym w celu szybkiego wyboru: ${\ Displaystyle O (n \ log n)}$

// Returns the k-th smallest element of list within left..right inclusive
// (i.e. left <= k <= right).
function select(list, left, right, k) is
    if left = right then   // If the list contains only one element,
        return list[left]  // return that element
    pivotIndex  := ...     // select a pivotIndex between left and right,
                           // e.g., left + floor(rand() % (right − left + 1))
    pivotIndex  := partition(list, left, right, pivotIndex)
    // The pivot is in its final sorted position
    if k = pivotIndex then
        return list[k]
    else if k < pivotIndex then
        return select(list, left, pivotIndex − 1, k)
    else
        return select(list, pivotIndex + 1, right, k) 

Zwróć uwagę na podobieństwo do szybkiego sortowania: tak jak algorytm selekcji opartej na minimum jest częściowym sortowaniem selekcji, jest to częściowe sortowanie szybkie, generujące i dzielące tylko swoje partycje. Ta prosta procedura oczekiwała wydajności liniowej i, podobnie jak sortowanie szybkie, ma w praktyce całkiem dobrą wydajność. Jest to również algorytm na miejscu , wymagający tylko stałego narzutu pamięci, jeśli dostępna jest optymalizacja wywołania ogona lub jeśli eliminuje rekurencję ogona za pomocą pętli: ${\ Displaystyle O (\ log n)}$${\ Displaystyle O (n)}$

function select(list, left, right, k) is
    loop
        if left = right then
            return list[left]
        pivotIndex := ...     // select pivotIndex between left and right
        pivotIndex := partition(list, left, right, pivotIndex)
        if k = pivotIndex then
            return list[k]
        else if k < pivotIndex then
            right := pivotIndex − 1
        else
            left := pivotIndex + 1

Złożoność czasowa

Podobnie jak quicksort, quickselect ma dobrą średnią wydajność, ale jest wrażliwy na wybrany punkt obrotu. Jeśli wybrane zostaną dobre osie, czyli takie, które konsekwentnie zmniejszają zbiór wyszukiwania o dany ułamek, to zbiór wyszukiwania zmniejsza się wykładniczo i przez indukcję (lub sumowanie szeregu geometrycznego ) widać, że wydajność jest liniowa, ponieważ każdy krok jest liniowy i całkowity czas jest stały razy ten (w zależności od tego, jak szybko zmniejsza się zbiór wyszukiwania). Jeśli jednak konsekwentnie wybierane są złe przechyły, na przykład za każdym razem zmniejsza się tylko o jeden element, najgorsze wyniki są kwadratowe: . Dzieje się tak na przykład przy wyszukiwaniu maksymalnego elementu zbioru, przy użyciu pierwszego elementu jako elementu przestawnego i posortowanych danych. ${\ Displaystyle O (n ^ {2})}$

Warianty

Najprostszym rozwiązaniem jest wybór losowego obrotu, który daje prawie pewien czas liniowy. Deterministycznie można użyć strategii mediana-of-3 pivot (jak w przypadku szybkiego sortowania), która zapewnia liniową wydajność na częściowo posortowanych danych, co jest powszechne w świecie rzeczywistym. Jednak wymyślone sekwencje mogą nadal powodować złożoność najgorszego przypadku; David Musser opisuje sekwencję „mediana 3 zabójców”, która umożliwia atak przeciwko tej strategii, co było jedną z motywacji dla jego algorytmu introselekcji .

Można zapewnić liniową wydajność nawet w najgorszym przypadku, stosując bardziej wyrafinowaną strategię obrotu; odbywa się to w medianie algorytmu median . Jednak narzut związany z obliczaniem punktu obrotu jest wysoki, dlatego generalnie nie jest to stosowane w praktyce. Można połączyć podstawowy szybki wybór z medianą median jako rezerwą, aby uzyskać zarówno szybką średnią wydajność, jak i liniową wydajność w najgorszym przypadku; odbywa się to w introselect .

Dokładniejsze obliczenia średniej złożoności czasowej dają najgorszy przypadek przypadkowych osi obrotu (w przypadku mediany; inne k są szybsze). Stałą można poprawić do 3/2 za pomocą bardziej skomplikowanej strategii przestawnej, uzyskując algorytm Floyda-Rivesta , który ma średnią złożoność dla mediany, przy czym inne k są szybsze. ${\ Displaystyle n (2 + 2 \ log 2 + o (1)) \ leq 3,4n + o (n)}$${\ Displaystyle 1,5n + O (n ^ {1/2})}$

Zobacz też

• Algorytm Floyda-Rivesta
• Introselect
• Mediana median

Bibliografia

Linki zewnętrzne

• " qselect ", algorytm Quickselect w Matlab, Manolis Lourakis