Delvis sortering

Inom datavetenskap är partiell sortering en avslappnad variant av sorteringsproblemet . Total sortering är problemet med att returnera en lista med objekt så att alla dess element visas i ordning, medan partiell sortering returnerar en lista med de k minsta (eller k största) elementen i ordning. De andra elementen (ovanför de k minsta) kan också sorteras, som i en partiell sortering på plats, eller kan kasseras, vilket är vanligt vid strömmande partiell sortering. Ett vanligt praktiskt exempel på partiell sortering är att beräkna "Topp 100" i någon lista.

När det gäller index, i en delvis sorterad lista, för varje index i från 1 till k, är det i -te elementet på samma plats som det skulle vara i den helt sorterade listan: element i i den delvis sorterade listan innehåller orderstatistik i i inmatningslistan.

Offlineproblem

Heap-baserad lösning

Heaps tillåter en enkel enkelpass partiell sortering när $k$ är fixerad: infoga de första $k$ elementen i ingången i en max-hög. Gör sedan en passage över de återstående elementen, lägg till var och en i högen i tur och ordning och ta bort det största elementet. Varje insättningsoperation tar $O (log k)$ tid, vilket resulterar i $O (n log k)$ tid totalt; denna "partial heapsort"-algoritm är praktisk för små värden på $k$ och i onlineinställningar . En " $O (n + k log n ) online$ heapselect"-algoritm som beskrivs nedan, baserad på en min-heap, tar .

Lösning genom partitionering

En ytterligare avslappning som endast kräver en lista över de $k$ minsta elementen, men utan att dessa måste beställas, gör problemet likvärdigt med partitionsbaserat urval ; det ursprungliga partiella sorteringsproblemet kan lösas med en sådan urvalsalgoritm för att erhålla en array där de första $k$ elementen är de $k$ minsta, och sortering av dessa, till en total kostnad av $O (n + k log k)$ operationer. Ett populärt val för att implementera detta algoritmschema är att kombinera quickselect och quicksort ; resultatet kallas ibland "quickselsort".

Vanligt i nuvarande (från och med 2022) C++ STL-implementeringar är ett pass av heapselect för en lista med k element, följt av en heapsort för det slutliga resultatet.

Specialiserade sorteringsalgoritmer

Mer effektiva än de ovan nämnda är specialiserade partiell sorteringsalgoritmer baserade på mergesort och quicksort . I quicksort-varianten finns det inget behov av att rekursivt sortera partitioner som bara innehåller element som skulle falla efter den $k:$ te platsen i den slutligt sorterade arrayen (med början från "vänster" gränsen). Således, om pivoten faller i position $k$ eller senare, återkommer vi endast på den vänstra partitionen:

     funktion  partial_quicksort(A, i, j, k)  är  om  i < j  då  p ← pivot(A, i, j) p ← partition(A, i, j, p) partial_quicksort(A, i, p-1, k )  om  p < k-1  så  partial_quicksort(A, p+1, j, k)

Den resulterande algoritmen kallas partiell quicksort och kräver en förväntad tid på endast $O (n + k log k)$ , och är ganska effektiv i praktiken, speciellt om en urvalssortering används som basfall när $k$ blir litet i förhållande till $n$ . Dock är tidskomplexiteten i värsta fall fortfarande mycket dålig, i fallet med ett dåligt pivotval. Pivotval i linje med den sämsta linjära tidsvalsalgoritmen (se Quicksort § Val av pivot ) skulle kunna användas för att få bättre prestanda i värsta fall. Partiell quicksort, quickselect (inklusive multipelvarianten) och quicksort kan alla generaliseras till vad som kallas en chunksort .

Inkrementell sortering

Inkrementell sortering är en version av det partiella sorteringsproblemet där ingången ges i förväg men $k$ är okänd: givet en $k$ -sorterad array bör det vara möjligt att utöka den delvis sorterade delen så att arrayen blir $(k +1)$ - sorterad.

Högar leder till en $O (n + k log n)$ "online heapselect"-lösning för inkrementell partiell sortering: först "heapify", i linjär tid, hela inmatningsmatrisen för att producera en min-hög. Extrahera sedan minimum av högen $k$ gånger.

En annan inkrementell sortering kan erhållas genom att ändra snabbval. Den version som beror på Paredes och Navarro upprätthåller en stack av pivoter över samtal, så att inkrementell sortering kan åstadkommas genom att upprepade gånger begära det minsta objektet i en array $A$ från följande algoritm:

Algoritm $IQS(A : array, i : heltal, S : stack)$ returnerar det $i$ :e minsta elementet i $A$

Om i = topp( S ) :
- Pop $S$
- Returnera $A [i]$
Låt $pivotera \leftarrow slumpmässigt [i, topp(S))$
Uppdatera $pivot \leftarrow partition(A [i : top(S)), A [pivot])$
Tryck $pivoten$ på $S$
Returnera $IQS(A, i, S)$

Stacken $S$ initieras för att endast innehålla längden $n$ av $A.$ $k$ -sortering av arrayen görs genom att anropa $IQS(A, i, S)$ för $i = 0, 1, 2, ...$ ; denna sekvens av anrop har medelvärdeskomplexitet $O (n + k log k)$ , vilket är asymptotiskt ekvivalent med $O (n + k log n)$ . Den värsta tiden är kvadratisk, men detta kan fixas genom att ersätta det slumpmässiga pivotvalet med medianalgoritmen för medianerna .

Språk/biblioteksstöd

C ++ -standarden specificerar en biblioteksfunktion som kallas std::partial_sort .
Python - standardbiblioteket innehåller funktioner som är störst och minst i sin heapq- modul.
Julias standardbibliotek innehåller en PartialQuickSort - algoritm som används i partialsort! och varianter.

Se även

Urvalsalgoritm

externa länkar

JM Chambers (1971). Delvis sortering . CACM 14 (5):357–358.