Częściowe sortowanie

W informatyce częściowe sortowanie jest zrelaksowaną odmianą problemu sortowania . Sortowanie całkowite to problem polegający na zwróceniu listy elementów w taki sposób, że wszystkie jej elementy pojawiają się w kolejności, podczas gdy sortowanie częściowe polega na zwróceniu listy k najmniejszych (lub k największych) elementów w kolejności. Pozostałe elementy (powyżej k najmniejsze) mogą być również sortowane, jak w przypadku sortowania częściowego na miejscu, lub mogą zostać odrzucone, co jest powszechne w przypadku częściowego sortowania strumieniowego. Typowym praktycznym przykładem częściowego sortowania jest obliczenie „Top 100” z jakiejś listy.

Jeśli chodzi o indeksy, na częściowo posortowanej liście, dla każdego indeksu i od 1 do k, i -ty element znajduje się w tym samym miejscu, co na liście w pełni posortowanej: element i częściowo posortowanej listy zawiera statystykę porządku i listy wejść.

Problemy offline

Rozwiązanie oparte na stercie

Sterty dopuszczają proste częściowe sortowanie jednoprzebiegowe, gdy k jest ustalone: ​​wstaw pierwsze k elementów wejścia do sterty maksymalnej. Następnie wykonaj jedno przejście nad pozostałymi elementami, dodaj każdy po kolei do sterty i usuń największy element. Każda operacja wstawiania zajmuje O (log k ) , co daje całkowity czas O ( n log k ) ; ten algorytm „częściowego sortowania sterty” jest praktyczny dla małych wartości k iw trybie online ustawienia. Opisany poniżej algorytm „wyboru sterty online”, oparty na stercie min, przyjmuje O ( n + k log n ) .

Rozwiązanie poprzez partycjonowanie wyboru

Dalsze złagodzenie wymagające tylko listy k najmniejszych elementów, ale bez wymogu ich uporządkowania, czyni problem równoważnym selekcji opartej na partycjach ; pierwotny problem częściowego sortowania można rozwiązać za pomocą takiego algorytmu selekcji, aby uzyskać tablicę, w której pierwsze k elementów jest k najmniejszych , i posortować je przy całkowitym koszcie O ( n + k log k ) operacji. Popularnym wyborem implementacji tego schematu algorytmu jest połączenie szybkiego wyboru i szybkie sortowanie ; wynik jest czasami nazywany „quickselsort”.

Powszechne w obecnych (od 2022 r.) Implementacjach C++ STL jest przekazywanie wyboru sterty dla listy k elementów, po którym następuje sortowanie sterty w celu uzyskania końcowego wyniku.

Specjalistyczne algorytmy sortowania

Bardziej wydajne od wyżej wymienionych są wyspecjalizowane algorytmy sortowania częściowego oparte na metodach mergesort i quicksort . W wariancie quicksort nie ma potrzeby rekurencyjnego sortowania partycji, które zawierają tylko elementy, które spadną za k- tym miejscem w finalnie posortowanej tablicy (zaczynając od „lewej” granicy). Tak więc, jeśli oś znajdzie się w pozycji k lub późniejszej, rekursujemy tylko na lewej partycji: 

     funkcja  częściowe_szybkiesort(A, i, j, k)  to  jeśli  i < j  to  p ← pivot(A, i, j) p ← partition(A, i, j, p) częściowe_szybkie sortowanie(A, i, p-1, k )  jeśli  p < k-1  to  częściowe_szybkie sortowanie(A, p+1, j, k)

Wynikowy algorytm nazywa się częściowym sortowaniem szybkim i wymaga oczekiwanego czasu tylko O ​​( n + k log k ) i jest dość wydajny w praktyce, zwłaszcza jeśli sortowanie przez wybieranie jest używane jako przypadek podstawowy, gdy k staje się małe względem n . Jednak złożoność czasowa w najgorszym przypadku jest nadal bardzo zła w przypadku złego wyboru osi obrotu. Wybór przestawny wzdłuż linii algorytmu wyboru w czasie liniowym najgorszego przypadku (patrz Quicksort § Wybór obrotu ) można wykorzystać do uzyskania lepszej wydajności w najgorszym przypadku. Częściowe sortowanie szybkie, szybkie wybieranie (w tym wariant wielokrotny) i szybkie sortowanie można uogólnić na tak zwane sortowanie fragmentów .

Sortowanie przyrostowe

Sortowanie przyrostowe to wersja problemu sortowania częściowego, w której dane wejściowe są podawane z góry, ale k jest nieznane: mając k -posortowaną tablicę, powinno być możliwe rozszerzenie częściowo posortowanej części, aby tablica stała się ( k +1) - posortowane.

Sterty prowadzą do rozwiązania O ( n + k log n ) „online heapselect” do przyrostowego sortowania częściowego: najpierw „heapify”, w czasie liniowym, kompletna tablica wejściowa w celu utworzenia min-sterty. Następnie wyodrębnij minimum sterty k razy.

Modyfikując szybki wybór, można uzyskać inne sortowanie przyrostowe. Wersja nadana przez Paredesa i Navarro utrzymuje stos przestawnych połączeń między wywołaniami, dzięki czemu można wykonać sortowanie przyrostowe poprzez wielokrotne żądanie najmniejszego elementu tablicy A z następującego algorytmu:

Algorytm IQS( A : tablica, i : liczba całkowita, S : stos) zwraca i 'ty najmniejszy element w A

  • Jeśli i = góra( S ) :
    • Pop S
    • Powrót A [ i ]
  • Niech pivot ← losowo [ i , top( S ))
  • Zaktualizuj przestawną ← partycję ( A [ i : top ( S )), A [pivot])
  • Wepchnij czop na S
  • Zwróć IQS( A , i , S )

Stos S jest inicjowany tak, aby zawierał tylko długość n z A . k - sortowanie tablicy odbywa się przez wywołanie IQS( A , i , S ) dla i = 0, 1, 2, ... ; ta sekwencja wywołań ma złożoność przypadku średniego O ( n + k log k ) , co jest asymptotycznie równoważne O ( n + k log n ) . W najgorszym przypadku czas jest kwadratowy, ale można to naprawić, zastępując losowy wybór obrotu algorytmem mediany median .

Obsługa języków/bibliotek

Zobacz też

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Partial_sorting&oldid=1141740417 ”