Co to znaczy, że algorytm sortowania jest „stabilny”?

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?

sorting

— Daenyth
źródło

Na pytanie to można łatwo odpowiedzieć w ciągu minuty za pomocą wikipedii. en.wikipedia.org/wiki/Sorting_alameterm

— Mare Infinitus

@MareInfinitus Dokładniej: en.wikipedia.org/wiki/Sorting_alameterm#Stability

— BЈовић

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

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,

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:

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.

wprowadź opis zdjęcia tutaj

— Robert Harvey
źródło

Korekta: Niestabilny algorytm wykazuje niezdefiniowane zachowanie, gdy dwa elementy są równe, jest całkiem możliwe, że czasami zachowany jest porządek.

— aaaaaaaaaaaa

Ładne zdjęcie, bardzo podobne do wikipedia en.wikipedia.org/wiki/Sorting_algorytm

— Mare Infinitus

@MareInfinitus: Jest w domenie publicznej. Sprawdź atrybucję oryginalnego obrazu.

— Robert Harvey

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

@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.

— David Z

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.

— Pytanie C.
źródło

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.

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

„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

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

@QuestionC Wygląda na to, że sortowanie bloków jest stabilne i pasuje do tych granic.