Interpolationssort

Ej att förväxla med interpolationssökning .

Interpolationssortering är en sorts hinksortering. Den använder en interpolationsformel för att tilldela data till hinken. En generell interpolationsformel är:

Interpolation = INT(((Array[i] - min) / (max - min)) * (ArraySize - 1))

Algoritm

Interpolationssortering

Klass	Sorteringsalgoritm
Datastruktur	Array
Prestanda i värsta fall	$O(n^{2})$
Bästa möjliga prestanda	$O(n)$
Genomsnittlig prestanda	$O(n+k)$
Värsta tänkbara rymdkomplexitet	$O(n*3)$

Interpolationssortering (eller histogramsortering). Det är en sorteringsalgoritm som använder interpolationsformeln för att sprida datasöndring och erövring . Interpolationssortering är också en variant av hinksorteringsalgoritm . Interpolationssorteringsmetoden använder en array med längder på posthack som motsvarar den ursprungliga nummerkolumnen. Genom att använda underhållslängdsmatrisen kan den rekursiva algoritmen förhindras från att ändra rymdkomplexiteten till $O(n^{2})$ på grund av minnesstackning. Segmenteringsposten för längdmatrisen kan med hjälp av sekundär funktion dynamiskt deklarera och radera minnesutrymmet för matrisen . Den rymdkomplexitet som krävs för att styra det rekursiva programmet är $O(3n)$ . Innehåller en tvådimensionell uppsättning av dynamiskt allokerade minnen och en uppsättning av rekordlängder. Dock kan exekveringskomplexiteten fortfarande upprätthållas som en effektiv sorteringsmetod för $O(n+k)$ . Array av dynamiskt allokerat minne kan implementeras av länkad lista , stack , kö , associativ array , trädstruktur etc. Ett arrayobjekt som JavaScript är tillämpligt. Skillnaden i datastruktur är relaterad till hastigheten för dataåtkomst och därmed den tid som krävs för sortering . När värdena i den ordnade matrisen är enhetligt fördelade ungefär den aritmetiska progressionen är den linjära tiden för interpolationssortering ${\ displaystil O(n)}$ .

Interpolationssorteringsalgoritm

1. Ställ in en hinklängdsuppsättning för att registrera längden på den osorterade hinken. Initiera till den ursprungliga arraylängden.
2. [Huvudsortering] Om skoplängdsmatrisen rensas och sorteras är klar. Utför [Dela funktion] om den inte är raderad.
3. [Dela funktion] Utför Dividera genom att poppa en hinklängd från änden av hinklängdsmatrisen. Hitta högsta och lägsta värden i hinken. Om maxvärdet är lika med minimivärdet, slutförs sorteringen för att stoppa Divide.
4. Ställ in en tvådimensionell array som alla tomma hinkar. Dela i hinken enligt interpolationsnumret.
5. Efter att ha delat i hinkarna, tryck in längden på hinkarna i spannet med skoplängd. Och sätt tillbaka föremålen i den ursprungliga arrayen en efter en från alla hinkar som inte är tomma.
6. Återgå till [Huvudsortering].

Histogramsorteringsalgoritm

NIST-definitionen: En effektiv 3-pass förfining av en hinksorteringsalgoritm.

1. Det första passet räknar antalet artiklar för varje hink i en extra array och gör sedan en löpande summa så att varje extra post är antalet föregående objekt.
2. Det andra passet placerar varje föremål i sin rätta hink enligt hjälpinmatningen för nyckeln för det föremålet.
3. Det sista passet sorterar varje hink.

Öva

Interpolationssorteringsimplementering

JavaScript-kod:

  

      
     
  0  
     0    
  
    
       
         
       
       
               
              
                 
    
              
     
         0
          
          0          
               
                        
        
      
          0     
           0 
              0         
          
        
      
    
  
 Array  .  prototyp  .  interpolationSort  =  function  ()  {  var  divideSize  =  new  Array  ();  var  slut  =  detta  .  längd  ;  divideSize  [  ]  =  slut  ;  while  (  divideSize  .  length  >  )  {  divide  (  this  );  }  // Upprepa funktion dividera till ArrayList  funktion  dividera  (  A  )  {  var  size  =  divideSize  .  pop  ();  var  start  =  slutstorlek  ;  _  _  var  min  =  A  [  start  ];  var  max  =  A  [  start  ];  for  (  var  i  =  start  +  1  ;  i  <  slut  ;  i  ++  )  {  if  (  A  [  i  ]  <  min  )  {  min  =  A  [  i  ];  }  else  {  if  (  A  [  i  ]  >  max  )  {  max  =  A  [  i  ];  }  }  }  if  (  min  ==  max  )  {  end  =  slutstorlek  ;  _  _  }  annat  {  var  p  =  ;  var  bucket  =  new  Array  (  storlek  );  for  (  var  i  =  ;  i  <  storlek  ;  i  ++  )  {  hink  [  i  ]  =  ny  Array  ();  }  for  (  var  i  =  start  ;  i  <  slut  ;  i  ++  )  {  p  =  Math  .  golv  (((  A  [  i  ]  -  min  )  /  (  max  -  min  )  )  *  (  storlek  -  1  ));  hink  [  p  ].  push  (  A  [  i  ]);  }  for  (  var  i  =  ;  i  <  storlek  ;  i  ++  )  {  if  (  hink  [  i  ].  längd  >  )  {  for  (  var  j  =  ;  j  <  hink  [  i  ].  längd  ;  j  ++  )  {  A  [  start  ++  ]  =  hink  [  i  ][  j  ];  }  divideSize  .  push  (  hink  [  i  ].  längd  );  }  }  }  }  }; 

Interpolationssortering rekursiv metod

Värsta utrymmeskomplexitet : $O(n^{2})$

 

     0
     
     0
     0 
           
            
             
  
      
        
        0          
       0
        0     
                  
      
    
        0     
             
          0         
    
  
 Array  .  prototyp  .  interpolationSort  =  function  ()  {  //-- Edit date:2019/08/31 --//  var  start  =  ;  var  storlek  =  detta  .  längd  ;  var  min  =  detta  [  ];  var  max  =  detta  [  ];  for  (  var  i  =  1  ;  i  <  storlek  ;  i  ++  )  {  if  (  detta  [  i  ]  <  min  )  {  min  =  detta  [  i  ];  }  else  {  if  (  this  [  i  ]  >  max  )  {  max  =  this  [  i  ];}  }  }  if  (  min  !=  max  )  {  var  bucket  =  new  Array  (  size  ) ;  for  (  var  i  =  ;  i  <  storlek  ;  i  ++  )  {  hink  [  i  ]  =  ny  Array  ();  }  var  interpolation  =  ;  for  (  var  i  =  ;  i  <  storlek  ;  i  ++  )  {  interpolation  =  Math  .  golv  (((  detta  [  i  ]  -  min  )  /  (  max  -  min  ))  *  (  storlek  -  1  ));  hink  [  interpolation  ].  push  (  denna  [  i  ]);  }  for  (  var  i  =  ;  i  <  storlek  ;  i  ++  )  {  if  (  hink  [  i  ].  längd  >  1  )  {  hink  [  i  ].  interpolationSort  ();  }  // Rekursion  för  (  var  j  =  ;  j  <  hink  [  i  ].  längd  ;  j  ++  )  {  this  [  start  ++  ]  =  hink  [  i  ][  j  ];  }  }  }  }; 

Histogramsorteringsimplementering

  

     
      
      
      
      
  0  
     0    
  
    
       
         
       
       
               
              
                 
    
              
     
                  0 
               
                          
        
      
               
           0   
      
          
               
            
      
               
          
        
      
                   
    
  
 Array  .  prototyp  .  histogramSort  =  function  ()  {  //-- Edit date:2019/11/14 --//  var  end  =  this  .  längd  ;  var  sortedArray  =  new  Array  (  end  );  var  interpolation  =  new  Array  (  end  );  var  hitCount  =  new  Array  (  end  );  var  divideSize  =  new  Array  ();  divideSize  [  ]  =  slut  ;  while  (  divideSize  .  length  >  )  {  distribuera  (  this  );  }  // Upprepa funktion distribuera till Array  funktion  distribuera  (  A  )  {  var  size  =  divideSize  .  pop  ();  var  start  =  slutstorlek  ;  _  _  var  min  =  A  [  start  ];  var  max  =  A  [  start  ];  for  (  var  i  =  start  +  1  ;  i  <  slut  ;  i  ++  )  {  if  (  A  [  i  ]  <  min  )  {  min  =  A  [  i  ];  }  else  {  if  (  A  [  i  ]  >  max  )  {  max  =  A  [  i  ];  }  }  }  if  (  min  ==  max  )  {  end  =  slutstorlek  ;  _  _  }  else  {  for  (  var  i  =  start  ;  i  <  slut  ;  i  ++  )  {  hitCount  [  i  ]  =  ;  }  for  (  var  i  =  start  ;  i  <  slut  ;  i  ++  )  {  interpolation  [  i  ]  =  start  +  Math  .  golv  (((  A  [  i  ]  -  min  )  /  (  max  -  min  )  )  *  (  storlek  -  1  ));  hitCount  [  interpolation  [  i  ]]  ++  ;  }  for  (  var  i  =  start  ;  i  <  slut  ;  i  ++  )  {  if  (  hitCount  [  i  ]  >  )  {  divideSize  .  push  (  hitCount  [  i  ]);  }  }  hitCount  [  end  -  1  ]  =  end  -  hitCount  [  slut  -  1  ];  for  (  var  i  =  slut  -  1  ;  i  >  start  ;  i  --  )  {  hitCount  [  i  -  1  ]  =  hitCount  [  i  ]  -  hitCount  [  i  -  1  ];  }  for  (  var  i  =  start  ;  i  <  slut  ;  i  ++  )  {  sortedArray  [  hitCount  [  interpolation  [  i  ]]]  =  A  [  i  ];  hitCount  [  interpolation  [  i  ]]  ++  ;  }  for  (  var  i  =  start  ;  i  <  slut  ;  i  ++  )  {  A  [  i  ]  =  sorteradArray  [  i  ];  }  }  }  }; 

Variant

Sortering av interpolationstagg

Interpolationstaggsortering

Klass	Sorteringsalgoritm
Datastruktur	Array
Prestanda i värsta fall	$O(n^{2})$
Bästa möjliga prestanda	$O(n)$
Genomsnittlig prestanda	$O(n+k)$
Värsta tänkbara rymdkomplexitet	$O(2n+(n)bitar)$

Interpolation Tag Sort är en variant av Interpolation Sort. Genom att tillämpa skopsorterings- och uppdelningsmetoden distribueras arraydata till ett begränsat antal hinkar genom matematisk interpolationsformel, och hinken sedan rekursivt det ursprungliga bearbetningsprogrammet tills sorteringen är klar.

Interpolationstaggsortering är en rekursiv sorteringsmetod för interpolationssortering. Minnet kraschar för att undvika stack overflow orsakat av rekursion. Använd istället en boolesk datatyp-tagg-array för att använda den rekursiva funktionen för att frigöra minnet. Det extra minnesutrymme som krävs är nära $2n+(n)bitar$ . Innehåller en tvådimensionell array av dynamiskt allokerat minne och en boolesk datatyp-tagg array. Stack, kö, associativ array och trädstruktur kan implementeras som hinkar.

Eftersom JavaScript-arrayobjektet är lämpligt för denna sorteringsmetod, är skillnaden i datastruktur relaterad till hastigheten för dataåtkomst och därmed den tid som krävs för sortering. Den linjära tiden Θ(n) används när värdena i arrayen som ska sorteras är jämnt fördelade. Skopsorteringsalgoritmen begränsar inte sorteringen till den nedre gränsen för $O(nlogn)$ . Interpolationstaggsortering genomsnittliga prestandakomplexiteten är $O(n+k)$ .

Sorteringsalgoritm för interpolationstagg

1. Ställ in en taggarray lika med den ursprungliga matrisstorleken och initiera till ett falskt värde.
2. [Huvudsortering] Bestämmer om alla hinkar i den ursprungliga matrisen har sorterats. Om sorteringen inte är klar, utförs [Dela-funktionen].
3. [Dela funktion] Hitta högsta och lägsta värden i hinken. Om maxvärdet är lika med minimivärdet avslutas sorteringen och uppdelningen stoppas.
4. Sätt upp en tvådimensionell array som alla tomma hinkar. Dela i hinken enligt interpolationsnumret.
5. Efter uppdelning i hinken, markera startpositionen för skopan som ett sant värde i taggarrayen. Och sätt tillbaka föremålen i den ursprungliga arrayen en efter en från alla hinkar som inte är tomma.
6. Återgå till [Huvudsortering].

Öva

JavaScript-kod:

  

      
       
       0  
                  
        0          
     
   
                           
          
     
  

       
        
       
                
               
                  
                 
                                               
         0 
            
                
          0            
                 
                      
          
       
          0     
           0     
             
              0          
         
        
    
   
 Array  .  prototyp  .  InterpolaionTagSort  =  function  ()  {  // Whale Chen samtycker till "Wikipedia CC BY-SA 3.0 License". Signeringsdatum: 2019-06-21 //   var  end  =  this  .  längd  ;  if  (  slut  >  1  )  {  var  start  =  ;  var  Tag  =  new  Array  (  end  );  // Algoritm steg-1  för  (  var  i  =  ;  i  <  end  ;  i  ++  )  {  Tag  [  i  ]  =  false  ;  }  Dela  (  detta  );  }  while  (  end  >  1  )  {  // Algoritm steg-2  while  (  Tag  [  --  start  ]  ==  false  )  {  }  // Hitta nästa hinks start  Divide  (  this  );  }  function  Divide  (  A  )  {  var  min  =  A  [  start  ];  var  max  =  A  [  start  ];  for  (  var  i  =  start  +  1  ;  i  <  slut  ;  i  ++  )  {  if  (  A  [  i  ]  <  min  )  {  min  =  A  [  i  ];  }  else  {  if  (  A  [  i  ]  >  max  )  {  max  =  A  [  i  ];  }  }  }  if  (  min  ==  max  )  {  end  =  start  ;  }  // Algoritm steg-3 Börja bli nästa hink's end  else  {  var  interpolation  =  ;  var  storlek  =  slut  -  start  ;  var  Bucket  =  new  Array  (  storlek  );  // Algoritm steg-4  för  (  var  i  =  ;  i  <  storlek  ;  i  ++  )  {  Bucket  [  i  ]  =  new  Array  ();  }  for  (  var  i  =  start  ;  i  <  slut  ;  i  ++  )  {  interpolation  =  Math  .  golv  (((  A  [  i  ]  -  min  )  /  (  max  -  min  ))  *  (  storlek  -  1  ));  Hink  [  interpolation  ].  push  (  A  [  i  ]);  }  for  (  var  i  =  ;  i  <  storlek  ;  i  ++  )  {  if  (  Hink  [  i  ].  längd  >  )  {  // Algoritm steg-5  Tagg  [  start  ]  =  sant  ;  for  (  var  j  =  ;  j  <  Hink  [  i  ].  längd  ;  j  ++  )  {  A  [  start  ++  ]  =  Hink  [  i  ][  j  ];  }  }  }  }  }  // Algoritm steg-6  }; 

In-place Interpolation Tag Sort

In-Place Interpolation Tag Sort

Klass	Sorteringsalgoritm
Datastruktur	Array
Prestanda i värsta fall	$O(n)$
Bästa möjliga prestanda	$O(n)$
Genomsnittlig prestanda	$O(n)$
Värsta tänkbara rymdkomplexitet	$O(n)bits$

In-place interpolation tag sorten är en in-place algoritm för interpolationssort. In-place Interpolation Tag Sort kan uppnå sortering med endast N gångers byte genom att behålla N bittaggar; dock måste matrisen som ska sorteras vara en kontinuerlig heltalssekvens och inte upprepas, eller så är serien helt jämnt fördelad för att ungefärliggöra antalet aritmetiska progressioner .

Faktorkolumndata får inte upprepas. Till exempel kan sortering 0~100 sorteras i ett steg. Antalet utbyten är: $O(n)$ , beräkningstidskomplexiteten är: $O(n)$ , och den värsta rymdkomplexiteten är $O(n)bitar$ . Om egenskaperna för serien uppfyller de villkorliga kraven för denna sorteringsmetod: "Arrayen är ett kontinuerligt heltal eller en aritmetisk progression som inte upprepas", kommer in-place interpolation tag-sorteringen att vara en utmärkt sorteringsmetod som är extremt snabb och sparar minnesutrymme.

In-place Interpolation Tag Sort Algoritm

In-place Interpolation Tag Sort sorterar icke-upprepande på varandra följande heltalsserier, endast en boolesk datatyp taggarray med samma längd som den ursprungliga matrisen, matrisen beräknar interpolationen av data från början och interpolationen pekar på en ny position av arrayen. Position, positionen som har bytts markeras som sann i motsvarande position för taggarrayen och inkrementeras tills slutet av matrisen sorteras.

Algoritmprocess:

1. Ställ in lika många taggarrayer för att initiera till falska värden.
2. Besök arrayen när tagg[i] är falsk, beräkna positionen som motsvarar interpolationen=p.
3. Byt ut a[i] och a[p], låt tagg[p] = sant.
4. Turarrayen är klar och sorteringen är klar.

Öva

JavaScript-kod:

  
 
     
      
     0         
     0
     0
                   
               
     0
     0
     0     
         
                  
        
         
        
         
     
   

 Array  .  prototyp  .  InPlaceTagSort  =  function  ()  {  // Edit Date: 2019-07-02  var  n  =  this  .  längd  ;  var  Tag  =  new  Array  (  n  );  for  (  i  =  ;  i  <  n  ;  i  ++  )  {  Tag  [  i  ]  =  false  ;  }  var  min  =  detta  [  ];  var  max  =  detta  [  ];  för  (  i  =  1  ;  i  <  n  ;  i  ++  )  {  if  (  detta  [  i  ]  <  min  )  {  min  =  detta  [  i  ];  }  else  {  if  (  this  [  i  ]  >  max  )  {  max  =  this  [  i  ];  }  }  }  var  p  =  ;  var  temp  =  ;  for  (  i  =  ;  i  <  n  ;  i  ++  )  {  while  (  Tag  [  i  ]  ==  false  )  {  p  =  Math  .  golv  (((  detta  [  i  ]  -  min  )  /  (  max  -  min  ))  *  (  n  -  1  ));  temp  =  detta  [  i  ];  detta  [  i  ]  =  detta  [  p  ];  detta  [  p  ]  =  temp  ;  Tagg  [  p  ]  =  sant  ;  }  }  };  needSortArray  .  InPlaceTagSort  (); 

Ursprunget för sortering på plats utförd i $O(n)$ tid

I "Mathematical Analysis of Algorithms", (Information Processing '71, North Holland Publ.'72) anmärkte Donald Knuth "... att forskning om beräkningskomplexitet är ett intressant sätt att vässa våra verktyg för mer rutinmässiga problem vi möter från dag till dag. dag."

Den berömda amerikanske datavetaren Donald Knuth i den matematiska analysen av algoritmer påpekade att: "När det gäller sorteringsproblemet, påpekar Knuth, att tidseffektiv in-situ permutation är naturligt kopplad till problemet att hitta cykelledarna, och i -situ-permutationer skulle lätt kunna utföras i ${\displaystyle O(n)}-$ tid om vi skulle få manipulera n extra "tagg"-bitar som anger hur mycket av permutationen som har utförts vid något tillfälle. taggbitar, drar han slutsatsen "det verkar rimligt att anta att varje algoritm kommer att kräva för in-situ permutation minst $O(nlogn)$ steg i genomsnitt."

In-place Interpolation Tag Sort är en av sorteringsalgoritmerna som Donald Knuth -professorn sa: "manipulera n extra "tag"-bitar...att hitta cykelledarna, och in-situ-permutationer kan lätt utföras i $O(n)$ tid".

Liknande sorteringsmetod

1. Flashsort
2. Proxmap sortering
3. Amerikansk flagga sort

Hinksortering som blandar andra sorteringsmetoder och rekursiv algoritm

Skopsortering kan blandas med andra sorteringsmetoder för att slutföra sorteringen. Om det sorteras efter skopsort och skärsort är det också en ganska effektiv sorteringsmetod. Men när serien visas en stor avvikelse från värdet: Till exempel när seriens maximala värde är större än N gånger det näst största värdet. Efter att serien av kolumner har bearbetats är fördelningen att alla element utom maxvärdet hamnar i samma hink. Den andra sorteringsmetoden använder infogningssortering. Kan göra att exekveringskomplexiteten hamnar i $O(n^{2})$ . Detta har förlorat betydelsen och höghastighetsprestandan med att använda skopsortering.

Interpolationssortering är ett sätt att rekursivt använda hinksortering. Efter att ha utfört rekursion, använd fortfarande hinksortering för att sprida serien. Detta kan undvika ovanstående situation. Om du vill få den rekursiva interpolationssorteringskomplexiteten att falla in i ${\displaystyle O(n^{2})} ,$ är det nödvändigt att presentera en faktoriell förstärkning i hela serien. Faktum är att det är mycket liten chans att en serie specialfördelningar kommer att inträffa.

externa länkar

• interpolationSort.html
• histogramSort.html
• FlashSort-algoritmen
• Matematisk analys av algoritmer
• http://www.drdobbs.com/database/the-flashsort1-algorithm/184410496
• 桶排序遞迴方式演算法 Skoksortering Rekursiv metod. Whale Chen 2012/09/16
• 插值標簽排序演算法 Interpolationstaggsorteringsalgoritm. Whale Chen 2013/03/24
• interpolationssort (Pascal-version tillgänglig)
• w3schools JavaScript Array Sort testplattform