Andel utöka sortera
| Klass | Sorteringsalgoritm |
|---|---|
| Datastruktur | Array |
| Prestanda i värsta fall | O( n log n ) |
| Bästa möjliga prestanda | O( n log n ) |
| Genomsnittlig prestanda | O( n log n ) |
| Värsta tänkbara rymdkomplexitet | O(log n ) hjälp |
Proportion extend sort (förkortat PESort ) är en på plats, jämförelsebaserad sorteringsalgoritm som försöker förbättra prestandan, särskilt prestandan i värsta fall , för quicksort .
Den grundläggande partitioneringsoperationen i quicksort har ett linjärt åtkomstmönster som är extremt effektivt på moderna minneshierarkier , men prestandan hos algoritmen är kritiskt beroende av valet av ett pivotvärde. En bra pivot delar upp data som ska sorteras i nästan lika stora halvor. Ett dåligt val kommer att resultera i en kraftigt skev division, vilket lämnar en del nästan lika stor som det ursprungliga problemet och orsakar O ( n 2 ) prestanda.
Proportion extend sort börjar med ett sorterat prefix av k element, och använder sedan medianen för det provet för att partitionera följande pk- element. Genom att begränsa storleksförhållandet p mellan provet och data som partitioneras (dvs. proportionen med vilken det sorterade prefixet utökas) begränsas obalansen. I detta har det vissa likheter med samplesort .
Historia
Proportion extend sort publicerades av Jing-Chao Chen 2001 som en förbättring av hans tidigare proportion split sort design. Dess genomsnittliga log 2 n + O ( n prestanda , som endast mättes experimentellt i originalartikeln, analyserades av Richard Cole och David C. Kandathil 2004 och av Chen 2006, och visade sig kräva ) jämförelser i genomsnitt. En något förfinad variant, symmetripartitionssortering, publicerades 2007.
Algoritm
Algoritmen börjar med en array uppdelad i en sorterad del S intill en osorterad del U . (Den ursprungliga proportionen utöka sortering hade alltid den sorterade delen före den osorterade delen; den symmetriska varianten tillåter endera ordningen.) Det är möjligt att börja med det första elementet som den sorterade delen (ett enstaka element är alltid sorterat), eller att sortera en litet antal element med en enklare infogningssortering . De initialt sorterade elementen kan också tas från hela arrayen för att förbättra prestandan i fallet med försorterade data.
Därefter, och mest kritiskt, längden på den osorterade delen | U | är begränsad till en multipel p av längden på den sorterade delen | S | . Specifikt, om | U | > p 2 | S | , sortera sedan rekursivt S och den intilliggande p | S | element i U , gör resultatet ( p +1 gånger längre än originalet) till det nya S , och upprepa tills villkoret är uppfyllt.
Om det inte finns någon gräns för den osorterade delen ( p =∞ ), är algoritmen ekvivalent med snabbsortering. Om den osorterade delen har längden 1 ( p =0 , nästan), så är algoritmen ekvivalent med binär infogningssort. Värden runt p ≈16 ger den bästa genomsnittliga prestandan, konkurrenskraftig med quicksort, medan mindre värden förbättrar det värsta fallet.
Eliezer Albacea publicerade en liknande algoritm 1995 som heter Leapfrogging samplesort där storleken är begränsad så | U | ≤ | S |+1 , senare generaliserad till (2k −1 )(| S |+1) .
Den sorterade delen av arrayen delas på mitten (vid medianen), och ena hälften flyttas (genom att byta ut den med osorterade element) till den bortre änden av arrayen, så vi har en initial delvis partitionerad array av formen LUR , där L är den vänstra halvan av den sorterade delen, U är den osorterade delen med begränsad längd och R är den högra halvan av den sorterade delen.
Sedan utförs det vanliga quicksort-partitioneringssteget på U UL , och delar upp det (på plats) i och U R . U L och U R sorteras inte, men varje element i U L är mindre än eller lika med medianen, och varje element i U R är större eller lika. Slutresultatet LU L U R R består av två arrayer av den nödvändiga formen (en sorterad del intill en osorterad del) och sorteras rekursivt .
Leapfrogging samplesort och den ursprungliga proportionen extend sort har den sorterade delen alltid före den osorterade delen, uppnådd genom att partitionera UL U innan R flyttas , vilket resulterar i LRU L U R , och sedan utbyte R med slutet av , vilket resulterar i LU L RU R . Även om den symmetriska versionen är lite knepigare, har den fördelen att L- och R -delarna fungerar som övervakningsvärden för partitioneringsslingorna, vilket eliminerar behovet av att testa i slingan om gränserna för U har nåtts.
De flesta av implementeringsförfiningarna som används för quicksort kan tillämpas, inklusive tekniker för att upptäcka och effektivt hantera mestadels sorterade indata. I synnerhet implementeras undersorter under en viss storlekströskel vanligtvis med hjälp av en enkel infogningssortering.
Som med quicksort kan antalet rekursiva nivåer begränsas till log 2 n om den mindre subsorteringen görs först och den större implementeras som ett tail call . Till skillnad från quicksort begränsas antalet nivåer av O (log n ) även om detta inte görs.