Sortera pärlor

Bead sort , även kallad gravity sort , är en naturlig sorteringsalgoritm , utvecklad av Joshua J. Arulanandham, Cristian S. Calude och Michael J. Dinneen 2002, och publicerad i The Bulletin of the European Association for Theoretical Computer Science . Både digitala och analoga hårdvaruimplementationer av pärlsortering kan uppnå en sorteringstid på O ( n ) ; implementeringen av denna algoritm tenderar dock att vara betydligt långsammare i programvara och kan endast användas för att sortera listor med positiva heltal . Det verkar också som att även i bästa fall kräver algoritmen O ( n ² ) utrymme.

Algoritmöversikt

Steg 1: Upphängda pärlor på vertikala stolpar.

Steg 2: Pärlorna har fått falla.

Pärlsorteringsoperationen kan jämföras med det sätt på vilket pärlor glider på parallella stolpar, till exempel på en kulram . Varje stolpe kan dock ha ett distinkt antal pärlor. Inledningsvis kan det vara bra att föreställa sig pärlorna upphängda på vertikala stolpar. I steg 1 visas ett sådant arrangemang med n=5 rader av pärlor på m=4 vertikala stolpar. Siffrorna till höger om varje rad anger numret som raden i fråga representerar; raderna 1 och 2 representerar det positiva heltal 3 (eftersom var och en innehåller tre pärlor) medan den översta raden representerar det positiva heltal 2 (eftersom den bara innehåller två pärlor).

Om vi ​​sedan låter pärlorna falla representerar nu raderna samma heltal i sorterad ordning. Rad 1 innehåller det största antalet i uppsättningen, medan rad n innehåller det minsta. Om den ovan nämnda konventionen för rader som innehåller en serie pärlor på polerna 1.. k och lämnar polerna k +1.. m tomma har följts, kommer det att fortsätta att vara fallet här.

Åtgärden att låta pärlorna "falla" i vårt fysiska exempel har tillåtit de större värdena från de högre raderna att fortplanta sig till de lägre raderna. Om värdet som representeras av rad a är mindre än värdet i rad a+1 , kommer några av pärlorna från rad a+1 att hamna i rad a ; detta kommer säkert att hända, eftersom rad a inte innehåller pärlor i de positionerna för att stoppa pärlorna från rad a+1 från att falla.

Mekanismen bakom pärlsorteringen liknar den bakom räknesortering ; antalet pärlor på varje stolpe motsvarar antalet element med ett värde lika med eller större än indexet för den polen.

Komplexitet

Bead sortering kan implementeras med fyra generella nivåer av komplexitet, bland annat:

• O (1): Alla pärlor flyttas samtidigt i samma tidsenhet, vilket skulle vara fallet med det enkla fysiska exemplet ovan. Detta är en abstrakt komplexitet och kan inte implementeras i praktiken.
• O ( ${\displaystyle {\sqrt {n}}} )$ : I en realistisk fysisk modell som använder gravitation är tiden det tar att låta pärlorna falla proportionell mot kvadratroten av den maximala höjden, som är proportionell mot n .
• O (n): Pärlorna flyttas en rad i taget. Detta är fallet som används i analoga och digitala hårdvarulösningar .
• O (S), där S är summan av heltal i ingångsmängden: Varje pärla flyttas individuellt. Detta är fallet när sortering av pärlor implementeras utan en mekanism för att hjälpa till att hitta tomma utrymmen under pärlorna, till exempel i programvaruimplementeringar.

Liksom Pigeonhole-sorteringen är pärlsortering ovanlig eftersom den i värsta fall kan prestera snabbare än O ( n log n ), den snabbaste möjliga prestanda för en jämförelsesortering i värsta fall. Detta är möjligt eftersom nyckeln för en pärlsortering alltid är ett positivt heltal och pärlsorteringen utnyttjar dess struktur.

Genomförande

Denna implementering är skriven i Python ; det antas att input_list kommer att vara en sekvens av heltal. Funktionen returnerar en ny lista istället för att mutera den som skickats in, men den kan modifieras trivialt för att fungera på plats effektivt.

 
    
      
    
    
    
      0  
       
        
        
        
        
                
    
    
    
    
    
       
        
        
        
              
    
      def  beadsort  (  input_list  ):  """Bead sort."""  return_list  =  []  # Initiera en 'transponerad lista' för att innehålla lika många element som #  det maximala värdet för indata -- i själva verket tar det 'högsta'  # kolumn med inmatade pärlor och lägga ut den platt  transposed_list  =  [  ]  *  max  (  input_list  )  för  num  i  input_list  :  # För varje element (varje 'kolumn med pärlor') i inmatningslistan, # '  lägg pärlorna platt' genom att öka som många element i den  # transponerade listan eftersom kolumnen är hög.  # Dessa kommer att ackumuleras ovanpå tidigare tillägg.  transposed_list  [:  num  ]  =  [  n  +  1  för  n  i  transposed_list  [:  num  ]]  # Vi har nu släppt pärlorna. För att avtransponera räknar vi   # 'nedre raden' av tappade pärlor, och härmar sedan att ta bort denna  # rad genom att subtrahera 1 från varje 'kolumn' i den transponerade listan.  # När en kolumn inte når tillräckligt högt för den aktuella raden,  kommer # dess värde i transponed_list att vara <= 0.  för  i  i  intervallet  (  len  (  input_list  )):  # Räknevärden > i är hur vi berättar hur många pärlor som finns i den  # nuvarande 'nedre raden'. Observera att Pythons bools kan   # utvärderas som heltal; Sant == 1 och Falskt == 0.   return_list  .  append  (  summa  (  n  >  i  för  n  i  transponerad_lista  ))  # Den resulterande listan är sorterad i fallande ordning  return  return_list 

Vi kan även implementera algoritmen med hjälp av Java .

        
    
        
           0
                 
                
                  
            
        
 
        
            
 
        
            0     
                0     
                  
            
        
 
        
            0     
               0
                0     
                  
                  0
            
 
                       
                  
                    
            
        
     public  static  void  beadSort  (  int  []  a  )  {  // Hitta det maximala elementet  int  max  =  a  [  ]  ;  for  (  int  i  =  1  ;  i  <  a  .  längd  ;  i  ++  )  {  if  (  a  [  i  ]  >  max  )  {  max  =  a  [  i  ]  ;  }  }  // allokera minne  int  [][]  beads  =  new  int  [  a  .  längd  ][  max  ]  ;  // markera pärlorna  för  (  int  i  =  ;  i  <  a  .  längd  ;  i  ++  )  {  for  (  int  j  =  ;  j  <  a  [  i  ]  ;  j  ++  )  {  pärlor  [  i  ][  j  ]  =  1  ;  }  }  // flytta ner pärlorna  för  (  int  j  =  ;  j  <  max  ;  j  ++  )  {  int  sum  =  ;  for  (  int  i  =  ;  i  <  a  .  längd  ;  i  ++  )  {  sum  +=  pärlor  [  i  ][  j  ]  ;  pärlor  [  i  ][  j  ]  =  ;  }  for  (  int  i  =  a  .  längd  -  1  ;  i  >=  a  .  längd  -  summa  ;  i  --  )  {  a  [  i  ]  =  j  +  1  ;  }  }  } 

externa länkar

•   "Bead-Sort: A Natural Sorting Algorithm" (PDF) . Arkiverad från originalet (PDF) 2017-08-09 . Hämtad 2005-01-01 . (114 KiB )
• Bead Sort in MGS , en visualisering av en pärlsortering implementerad i MGS programmeringsspråk
• Bead Sort på MathWorld
• Bead Sort interaktiv visualisering