Co to znaczy, że algorytm sortowania jest „stabilny”?
43
Czytając o różnych algorytmach sortowania, zauważyłem, że niektóre są „stabilne”, a inne nie. Co to oznacza i jakie kompromisy wiążą się na tej podstawie przy wyborze algorytmu?
To pytanie nie ma własnych badań. Odpowiedzi obrazem z Wikipedii. I dostaje naprawdę dobre opinie, co jakoś mnie zasmuca. IMHO powinno być zamknięte, a nie otrzymywać pozytywnych opinii.
Mare Infinitus
4
Z drugiej strony właśnie to zobaczyłem i nauczyłem się czegoś nowego. Gdybym wiedział, że tego nie wiem, mógłbym to zbadać, ale ponieważ OP zadał pytanie, teraz wiem, czego nie wiedziałem, a czego nie wiedziałem.
Kazark,
4
Zasadniczo „po prostu google to” lub „poszukaj w wikipedii” nie są znaczącymi akceptowalnymi odpowiedziami na stronach StackExchange. Ponieważ nie udzielają odpowiedzi na to, co osoba wnosząca skargę weryfikuje jako prawidłowe pytanie, dzwoniąc do władz Google i Wikipedii. JEŚLI pytanie jest z łatwością duplikatem innego pytania lub pytań w programie programiści.stackexchange, możesz złożyć skargę.
Michael Paulukonis
Odpowiedzi:
88
Sortowanie stabilne to takie, które zachowuje pierwotną kolejność zestawu danych wejściowych, przy czym algorytm porównania nie rozróżnia dwóch lub więcej elementów.
Rozważ algorytm sortowania, który sortuje karty według rangi , ale nie według koloru. Stabilny rodzaj gwarantuje zachowanie pierwotnej kolejności kart o tej samej wartości; niestabilny rodzaj nie.
Korekta: Niestabilny algorytm wykazuje niezdefiniowane zachowanie, gdy dwa elementy są równe, jest całkiem możliwe, że czasami zachowany jest porządek.
@MareInfinitus: Jest w domenie publicznej. Sprawdź atrybucję oryginalnego obrazu.
Robert Harvey
2
Dobry obraz wyjaśnia szybsze i głębsze niż wiele słów przeciętnego przypadku. Kwestie prawne nie były tym, o czym chciałem porozmawiać.
Mare Infinitus
3
@RobertHarvey Właściwie uważam, że edytor ma rację. Twój post mówi obecnie, że stabilne sortowanie zachowuje porządek kart w tym samym kolorze, ale karty w tym samym kolorze będą miały różne rangi, a zatem należy je zmienić, aby osiągnąć porządek sortowany. Na przykład sortowanie nie zachowuje kolejności 2 i 5 serc. To kolejność kart o tej samej wartości (i różnych kolorach) sprawia, że różnica między stabilnym a niestabilnym.
Jeśli chodzi o kompromis ... cóż, stabilne sortowanie jest mniej wydajne, ale czasami jest to potrzebne.
Na przykład, gdy użytkownik kliknie nagłówek kolumny, aby posortować wartości w interfejsie użytkownika, uzasadnione jest oczekiwanie, że jego poprzednia kolejność sortowania zostanie zastosowana w przypadku równych wartości.
Czy to jest mniej wydajne? Wydaje się to „oczywiste”, ale niektóre z najlepszych algorytmów sortowania są z natury stabilne (np. Wszystko oparte na sortowaniu scalającym, takie jak sortowanie Tim), nie muszą wykonywać żadnych wyraźnych dodatkowych prac, aby być stabilnym.
9
Stabilność nie ma nic wspólnego z wydajnością. Mergesort działa w O (n * log n) i jest stabilny. Heapsort ma podobną wydajność, ale nie jest stabilny.
Mare Infinitus
2
„Stabilny” może również dotyczyć struktur danych, np. „stabilna sterta” to sterta, która usuwa z kolejki elementy o tym samym priorytecie w tej samej kolejności, w jakiej zostały umieszczone w kolejce. Jest to bardzo ważne dla wydajnych algorytmów wyszukiwania ścieżek.
BlueRaja - Danny Pflughoeft
1
Nie ma stabilnych rodzajów, które są porównaniami O (n ln n), a także O (1) w pamięci. Prędkość nie jest jedyną miarą wydajności. Fakt, że nie można stabilnie sortować na miejscu, ma znaczenie.
Pytanie C
3
@QuestionC Wygląda na to, że sortowanie bloków jest stabilne i pasuje do tych granic.
Odpowiedzi:
Sortowanie stabilne to takie, które zachowuje pierwotną kolejność zestawu danych wejściowych, przy czym algorytm porównania nie rozróżnia dwóch lub więcej elementów.
Rozważ algorytm sortowania, który sortuje karty według rangi , ale nie według koloru. Stabilny rodzaj gwarantuje zachowanie pierwotnej kolejności kart o tej samej wartości; niestabilny rodzaj nie.
źródło
Stabilne algorytmy zachowują względną kolejność elementów.
Zatem stabilny algorytm sortowania zachowa względną kolejność wartości, które są porównywalne jako równe.
Rozważmy algorytm sortowania, w którym sortujemy kolekcję punktów 2d na podstawie ich wymiaru X.
Kolekcja do sortowania:
{(6, 3), (5, 5), (6, 1), (1, 3)}Sortowane stabilne:
{(1, 3), (5, 5), (6, 3), (6, 1)}Regularne sortowanie: albo
{(1, 3), (5, 5), (6, 3), (6, 1)}, albo{(1, 3), (5, 5), (6, 1), (6, 3)}Jeśli chodzi o kompromis ... cóż, stabilne sortowanie jest mniej wydajne, ale czasami jest to potrzebne.
Na przykład, gdy użytkownik kliknie nagłówek kolumny, aby posortować wartości w interfejsie użytkownika, uzasadnione jest oczekiwanie, że jego poprzednia kolejność sortowania zostanie zastosowana w przypadku równych wartości.
źródło