Floyd-Rivest-algoritm

Floyd–Rivest
Klass Urvalsalgoritm
Datastruktur Array
Genomsnittlig prestanda n + min( k , n − k ) + O ( n 1/2 log 1/2 n )

Inom datavetenskap är Floyd -Rivest-algoritmen en urvalsalgoritm som utvecklats av Robert W. Floyd och Ronald L. Rivest som har ett optimalt förväntat antal jämförelser inom termer av lägre ordning . Det är funktionellt likvärdigt med quickselect , men går snabbare i praktiken i genomsnitt. Den har en förväntad gångtid på O ( n ) och ett förväntat antal jämförelser av n + min( k , n − k ) + O ( n 1/2 log 1/2 n ) .

Algoritmen presenterades ursprungligen i en teknisk rapport från Stanford University som innehöll två artiklar, där den hänvisades till som SELECT och parades med PICK, eller median av medianer . Den publicerades därefter i Communications of the ACM , Volym 18: Issue 3.

Algoritm

Floyd-Rivest-algoritmen är en söndra och erövra-algoritm som delar många likheter med quickselect . Den använder sampling för att hjälpa till att dela upp listan i tre uppsättningar. Den väljer sedan rekursivt det k: te minsta elementet från lämplig uppsättning.

De allmänna stegen är:

  1. Välj ett litet slumpmässigt urval S från listan L .
  2. Från S väljer du rekursivt två element, u och v , så att u < v . Dessa två element kommer att vara pivoterna för partitionen och förväntas innehålla det k: te minsta elementet i hela listan mellan dem (i en sorterad lista).
  3. Använd u och v , partitionera S i tre uppsättningar: A , B , och C . A kommer att innehålla elementen med värden mindre än u , B kommer att innehålla elementen med värden mellan u och v , och C kommer att innehålla elementen med värden större än v .
  4. Partitionera de återstående elementen i L (det vill säga elementen i L - S ) genom att jämföra dem med u eller v och placera dem i lämplig uppsättning. Om k är mindre än hälften av antalet element i L avrundat uppåt, så ska de återstående elementen jämföras med v först och sedan endast med u om de är mindre än v . Annars bör de återstående elementen jämföras med u först och endast med v om de är större än u .
  5. Baserat på värdet på k , tillämpa algoritmen rekursivt på lämplig uppsättning för att välja det k: te minsta elementet i L.

Genom att använda | S | = Θ( n 2/3 log 1/3 n ), vi kan få n + min( k , n − k ) + O ( n 2/3 log 1/3 n ) förväntade jämförelser. Vi kan få n + min( k , n − k ) + O ( n 1/2 log 1/2 n ) förväntade jämförelser genom att börja med ett litet S och upprepade gånger uppdatera u och v för att hålla storleken på B tillräckligt liten ( O ( n 1/2 log 1/2 n ) vid Θ( n ) bearbetade element) utan oacceptabel risk för att det önskade elementet ligger utanför B .

Pseudokodversion

Följande pseudokod ordnar om elementen mellan vänster och höger , så att för något värde k , där vänster ≤ k ≤ höger , kommer det k: te elementet i listan att innehålla det ( k − vänster + 1):e minsta värdet, med det i:te elementet är mindre än eller lika med k: te för alla vänster ≤ i ≤ k och det j:te elementet är större eller lika med för k ≤ j ≤ höger : 

 //  vänster är det vänstra indexet för intervallet  //  höger är det högra indexet för intervallet  //  k är det önskade indexvärdet, där array[k] är det (k+1):e minsta elementet när vänster = 
function select(array, left, right, k) is
    while right > left do
        // Use select recursively to sample a smaller set of size s
        // the arbitrary constants 600 and 0.5 are used in the original
        // version to minimize execution time.
        if right − left > 600 then
            n := right − left + 1
            i := k − left + 1
            z := ln(n)
            s := 0.5 × exp(2 × z/3)
            sd := 0.5 × sqrt(z × s × (n − s)/n) × sign(i − n/2)
            newLeft := max(left, k − i × s/n + sd)
            newRight := min(right, k + (n − i) × s/n + sd)
            select(array, newLeft, newRight, k)
        // partition the elements between left and right around t
        t := array[k] 
        i := left
        j := right
        swap array[left] and array[k]
        if array[right] > t then
            swap array[right] and array[left]
        while i < j do
            swap array[i] and array[j]
            i := i + 1
            j := j − 1
            while array[i] < t do
                i := i + 1
            while array[j] > t do
                j := j − 1
        if array[left] = t then
            swap array[left] and array[j]
        else
            j := j + 1
            swap array[j] and array[right]
        // Adjust left and right towards the boundaries of the subset
        // containing the (k − left + 1)th smallest element.
        if j ≤ k then
            left := j + 1
        if k ≤ j then
            right := j − 1

Se även

Hämtad från " https://en.wikipedia.org/w/index.php?title=Floyd–Rivest_algorithm&oldid=1096413384 "