Sortering av turneringar

Sortering av turneringar

Klass	Sorteringsalgoritm
Datastruktur	Array
Prestanda i värsta fall	O( n log n )
Genomsnittlig prestanda	O( n log n )

Turneringssortering är en sorteringsalgoritm . Det förbättrar den naiva urvalssorteringen genom att använda en prioritetskö för att hitta nästa element i sorteringen. I den naiva urvalssorteringen krävs O ( n ) operationer för att välja nästa element av n element; i en turneringssort tar det O(log n ) operationer (efter att ha byggt den första turneringen i O( n )). Turneringssort är en variant av heapsort .

Vanlig applikation

Ersättningssorter för turneringar används för att samla in de första körningarna för externa sorteringsalgoritmer. Konceptuellt läses en extern fil och dess element skjuts in i prioritetskön tills kön är full. Sedan dras minimielementet från kön och skrivs som en del av den första körningen. Nästa inmatningselement läses och skjuts in i kön, och min väljs igen och läggs till körningen. Det finns ett litet knep att om det nya elementet som skjuts in i kön är mindre än det senaste elementet som lagts till i körningen, så höjs elementets sorteringsvärde så att det blir en del av nästa körning. I genomsnitt kommer en körning att vara 100 % längre än kapaciteten för prioritetskön.

Turneringssorter kan också användas i N-vägs sammanslagningar.

Etymologi

Namnet kommer från dess likhet med en singel-elimineringsturnering där det finns många spelare (eller lag) som spelar i dubbelsidiga matcher. Varje match jämför spelarna och den vinnande spelaren befordras till att spela en match på nästa nivå upp. Hierarkin fortsätter tills den sista matchen bestämmer den slutliga vinnaren. Turneringen avgör den bästa spelaren, men spelaren som blev slagen i den sista matchen kanske inte är den näst bästa – han kan vara underlägsen andra spelare som vinnaren vann.

Genomförande

Följande är en implementering av turneringssortering i Haskell , baserat på Scheme -kod av Stepanov och Kershenbaum.

 


   
          
          
 
           
     
               
            


   
            
              
   
      


   
          
          
          
                   
    
    
      
      


   
             
             
             
                    
  
              
                                   


     
            
            
                   
                   
                   
     
       
         

   
     
    0      importera  Data.Tree  -- | Anpassad från `TOURNAMENT-SORT!` i Stepanov och Kershenbaums rapport.   tournamentSort  ::  Ord  t  =>  [  t  ]  -- ^ Inmatning: en osorterad lista  ->  [  t  ]  -- ^ Resultat: sorterad version av ingångsturneringenSort  alist  =  go  (  ren  <  $>  alist  )  -- först, linda varje element som en skog med ett träd  där  go  []  =  [  ]  go  trees  =  (  rootLabel  winner  )  :  (  go  (  subForest  winner  ))  där  vinnare  =  playTurneringsträd  -- |  Anpassad  från `TOURNAMENT!` i Stepanov och Kershenbaum-rapporten  playTournament  ::  Ord  t  =>  Forest  t  -- ^ Input skog  -  >  Träd  t  -- ^ Det senast uppflyttade trädet i input  playTournament  [  träd  ]  =  trädspelTurneringsträd  =  playTournament  (  playRound  trees  []  )  -- | Anpassad från `TOURNAMENT-ROUND!` i Stepanov och Kershenbaum-rapporten   playRound  ::  Ord  t  =>  Skog  t  -- ^ En skog av träd som ännu inte har tävlat i omgång ->  Skog  t  --  ^ En skog av träd som har vann i omgången  ->  Skog  t  -- ^ Utdata: en skog som innehåller främjade versioner  -- av träden som vann sina spel  playRound  []  done  =  done  playRound  [  tree  ]  done  =  tree  :  done  playRound  (  tree0  :  tree1  :  trees  )  klar  =  playRound  trees  (  vinnare  :  klar  )  där  vinnare  =  playGame  tree0  tree1  -- | Anpassad från `TOURNAMENT-PLAY!` i Stepanov och Kershenbaum-rapporten   playGame  ::  Ord  t  =>  Träd  t  -- ^ Inmatning: ...  ->  Träd  t  -- ^ ... två träd  ->  Träd  t  -- ^ Resultat: `promote winner loser`, där `winner` är  -- trädet med den *mindre* roten av de två ingångarna  playGame  tree1  tree2  |  rootLabel  tree1  <=  rootLabel  tree2  =  främja  tree1  tree2  |  annars  =  främja  träd2  träd1  -- | Anpassad från `GRAB!` i Stepanov och Kershenbaum-rapporten   främja  ::  Träd  t  -- ^ `Vinnaren`  ->  Träd  t  -- ^ `Förloraren`  ->  Träd  t  -- ^ Resultat: ett träd vars rot är roten av `vinnare`  -- och vars barn är:  -- * `förlorare`,  -- * alla barn till `vinnare`  främja  vinnare  förlorare  =  Node  {  rootLabel  =  rootLabel  vinnare  ,  subForest  =  förlorare  :  subForest  vinnare  }  main  ::  IO  ()  main  =  print  $  tournamentSortera  testlista  där  testList  =  [  ,  1  ,  2  ,  3  ,  4  ,  5  ] 

• Kershenbaum et al 1988, "Higher Order Imperative Programming"