Sortowanie cierpliwości - Patience sorting
| Klasa | Algorytm sortowania |
|---|---|
| Struktura danych | Szyk |
| Najgorsza wydajność | O ( n log n ) |
| Najlepsza wydajność | O ( n ) ; występuje, gdy dane wejściowe są wstępnie posortowane |
W informatyce , cierpliwość sortowania jest sortowanie algorytm inspirowany i nazwane, gra w karty cierpliwość . Wariant algorytmu skutecznie oblicza długość najdłuższego rosnącego podciągu w danej tablicy .
Przegląd
Nazwa algorytmu pochodzi od uproszczonego wariantu gry karcianej cierpliwość. Gra rozpoczyna się potasowaniem talii kart. Karty są układane pojedynczo w stosy na stole, zgodnie z poniższymi zasadami.
- Początkowo nie ma stosów. Pierwsza rozdana karta tworzy nowy stos składający się z jednej karty.
- Każda kolejna karta jest umieszczana na lewym istniejącym stosie, którego górna karta ma wartość większą lub równą wartości nowej karty lub na prawo od wszystkich istniejących stosów, tworząc w ten sposób nowy stos.
- Gdy nie ma już kart do rozdania, gra się kończy.
Ta gra karciana jest przekształcona w dwufazowy algorytm sortowania w następujący sposób. Mając tablicę n elementów z jakiejś całkowicie uporządkowanej domeny, rozważ tę tablicę jako zbiór kart i zasymuluj grę w sortowanie cierpliwości. Kiedy gra się skończy, odzyskaj posortowaną sekwencję, kilkakrotnie wybierając minimalną widoczną kartę; Innymi słowy, przeprowadzić K -Way połączyć z p stosów, z których każdy jest wewnętrznie sortowane.
Analiza
Pierwsza faza sortowania cierpliwości, symulacja gry karcianej, może być zaimplementowana w celu wykonania O ( n log n ) porównań w najgorszym przypadku dla tablicy wejściowej n -elementowej: będzie co najwyżej n stosów, a konstrukcja górna karty stosów tworzą rosnącą sekwencję od lewej do prawej, więc żądany stos można znaleźć za pomocą wyszukiwania binarnego . Druga faza, łączenie pali, może odbywać się w czasie O ( n log n ), również przy użyciu kolejki priorytetowej .
Gdy dane wejściowe zawierają naturalne „przebiegi”, tj. Nie-malejące podtablice, wydajność może być znacznie lepsza. W rzeczywistości, gdy tablica wejściowa jest już posortowana, wszystkie wartości tworzą jeden stos i obie fazy przebiegają w czasie O ( n ) . Średniej przypadku złożoność jest nadal O ( n log n ) : każdy równomiernie losowa sekwencja wartości wytworzy oczekiwanej liczby z O ( √ n ) pali, które podjęcia O ( n log √ N ) = O ( n log n ) Czas produkować i łączyć.
Ocenę praktycznego zachowania cierpliwego dokonują Chandramouli i Goldstein, którzy pokazują, że naiwna wersja jest około dziesięć do dwudziestu razy wolniejsza niż najnowocześniejsze szybkie sortowanie ich wzorcowego problemu. Przypisują to stosunkowo niewielkiej ilości badań poświęconych sortowaniu cierpliwemu i opracowują kilka optymalizacji, które sprawiają, że jego wydajność jest dwukrotnie większa niż w przypadku szybkiego sortowania.
Jeśli wartości kart mieszczą się w zakresie 1 ,. . . , n , istnieje wydajna implementacja z O ( n log n ) najgorszym możliwym czasem działania dla układania kart w stosy, opierając się na drzewie Van Emde Boas .
Relacje z innymi problemami
Sortowanie cierpliwości jest ściśle związane z grą karcianą zwaną grą Floyda. Ta gra jest bardzo podobna do gry naszkicowanej wcześniej:
- Pierwsza rozdana karta tworzy nowy stos składający się z jednej karty.
- Każda kolejna karta jest umieszczana na jakimś istniejącym stosie, którego górna karta ma wartość nie mniejszą niż wartość nowej karty lub na prawo od wszystkich istniejących stosów, tworząc w ten sposób nowy stos.
- Gdy nie ma już kart do rozdania, gra się kończy.
Celem gry jest ukończenie z jak najmniejszą liczbą stosów. Różnica w stosunku do algorytmu sortowania cierpliwości polega na tym, że nie ma wymogu umieszczania nowej karty na skrajnym lewym stosie, gdzie jest to dozwolone. Sortowanie cierpliwości stanowi zachłanną strategię w tej grze.
Aldous i Diaconis sugerują zdefiniowanie 9 lub mniej stosów jako zwycięskiego wyniku dla n = 52 , co ma miejsce z prawdopodobieństwem około 5%.
Algorytm znajdowania najdłuższego rosnącego podciągu
Najpierw wykonaj algorytm sortowania, jak opisano powyżej. Liczba stosów to długość najdłuższego podciągu. Za każdym razem, gdy karta jest umieszczana na wierzchu stosu, odłóż wskaźnik wstecz na wierzchnią kartę z poprzedniego stosu (która z założenia ma niższą wartość niż nowa karta). Na koniec postępuj zgodnie ze wskazówkami z górnej karty w ostatnim stosie, aby odzyskać malejący fragment o największej długości; jego odwrotność jest odpowiedzią na algorytm najdłuższego rosnącego podciągu.
S. Bespamyatnikh i M. Segal podają opis efektywnej implementacji algorytmu, nie powodującego dodatkowego asymptotycznego kosztu w porównaniu z sortowaniem (ponieważ przechowywanie, tworzenie i przechodzenie wstecz-pointów wymaga liniowego czasu i przestrzeni). Ponadto pokazują, jak raportować wszystkie najdłuższe rosnące podciągi z tych samych wynikowych struktur danych .
Historia
Sortowanie cierpliwości zostało nazwane przez CL Mallowsa, który przypisał jego wynalazek ASC Ross na początku lat 60. Według Aldousa i Diaconisa sortowanie cierpliwości zostało po raz pierwszy uznane za algorytm obliczania najdłuższej rosnącej długości podciągów przez Hammersleya. ASC Ross i niezależnie Robert W. Floyd rozpoznali to jako algorytm sortowania. Wstępną analizę wykonał Mallows. Gra Floyda została stworzona przez Floyda w korespondencji z Donaldem Knuthem .
Posługiwać się
Algorytm sortowania cierpliwości można zastosować do sterowania procesem . W serii pomiarów istnienie długiego rosnącego podciągu może być użyte jako marker trendu. Artykuł z 2002 roku w magazynie SQL Server zawiera implementację SQL, w tym kontekście, algorytmu sortowania cierpliwości dla długości najdłuższego rosnącego podciągu.
