Czym jest stabilność algorytmów sortowania i dlaczego jest ważna?

292

Jestem bardzo ciekawy, dlaczego stabilność jest lub nie jest ważna w algorytmach sortowania?

— DarthVader
źródło

2

Do celów paralelizacji? np .: sortowanie scalone jest stabilne i może być dobrze zrównoleglone, podobnie jak szybkie sortowanie.

— DarthVader

13

Klasyczny QuickSort jest niestabilny

— Konstantin Spirin

9

stable sort algo -IBM (Insertion, Bubble, Merge)

— roottraveller

Uwaga dla tych, którzy mogą źle zrozumieć taką koncepcję jak ja: Porządek równych elementów jest gwarantowany. oznacza: jeśli elementy w stabilnym sortowaniu są uważane za równe, wówczas byłyby zgodne z poprzednią kolejnością. Nie tak myślałem: jeśli elementy w poprzedniej kolejności będą uważane za równe, to w nadchodzącym stabilnym stanie będą postępować według poprzedniej kolejności. Chociaż może się okazać, że to drugie zrozumienie ma również sens w wielu przypadkach.

— Rick

371

Mówi się, że algorytm sortowania jest stabilny, jeśli dwa obiekty z jednakowymi kluczami pojawiają się w tej samej kolejności w posortowanym wyjściu, jak pojawiają się w tablicy wejściowej do posortowania. Niektóre algorytmy sortowania są z natury stabilne, takie jak sortowanie wstawiane, sortowanie scalone, sortowanie bąbelkowe itp. Niektóre algorytmy sortujące nie są takie jak sortowanie sterty, szybkie sortowanie itp.

Tło : „stabilny” algorytm sortowania utrzymuje elementy z tym samym kluczem sortowania w kolejności. Załóżmy, że mamy listę 5-literowych słów:

peach
straw
apple
spork

Jeśli posortujemy listę według pierwszej litery każdego słowa, wówczas sortowanie stabilne wygeneruje:

apple
peach
straw
spork

W algorytmie sortowania niestabilnegostraw lub sporkmoże być zamiennego, ale w stabilnym pozostają one w tych samych pozycjach względnych (to znaczy, ponieważ strawpojawia się wcześniej sporkna wejściu, pojawia się również przed sporkwyjściem).

Możemy posortować listę słów za pomocą tego algorytmu: stabilne sortowanie według kolumny 5, następnie 4, następnie 3, następnie 2, a następnie 1. Na koniec zostanie poprawnie posortowane. Przekonaj się o tym. (nawiasem mówiąc, ten algorytm nazywa się sortowaniem radix)

Teraz, aby odpowiedzieć na twoje pytanie, załóżmy, że mamy listę imion i nazwisk. Jesteśmy proszeni o sortowanie „według nazwiska, a następnie według”. Możemy najpierw sortować (stabilny lub niestabilny) według imienia, a następnie sortować według nazwiska. Po tych sortowaniach lista jest głównie sortowana według nazwiska. Jednak tam, gdzie nazwiska są takie same, są one sortowane.

Nie możesz układać niestabilnych rodzajów w ten sam sposób.

— Joey Adams
źródło

Jak by to się nazywało, aby słowa w prawidłowej kolejności sortowania słomy sportowej brzoskwini jabłkowej? Stabilna rodzaj dał nam jabłko brzoskwinia słomkowy Spork jednak st powinno być po sp (alfabetycznie poprawne), więc ostateczny prawidłowy porządek powinien być jabłko brzoskwinia sportu słomy

— user1416486

2

@ user1416486: Sortujemy tylko według pierwszej litery. Z tym założeniem strawi sporkporównaj równe. Sortowanie stabilne zachowuje kolejność wprowadzania, podczas gdy sortowanie niestabilne nie daje takiej gwarancji. „Prawidłowe” zależy od aplikacji. Funkcja sortowania w większości języków programowania pozwala użytkownikowi dostarczyć niestandardową funkcję zamawiania. Jeśli funkcja użytkownika traktuje różne elementy jako równe (np. To samo imię, inne nazwisko), pomaga wiedzieć, czy oryginalne zamówienie zostanie zachowane. Zobacz funkcje sortowania tablic OCaml, aby zobaczyć prawdziwy przykład.

— Joey Adams,

3

Nie rozumiem linii .. taki sam klucz sortowania ? Co rozumiesz przez klucz? Wyjaśnij instrukcję ... taki sam klucz sortujący

— saplingPro

2

@saplingPro: „klucz sortujący” oznacza rzecz, według której sortujesz elementy. Zatem podczas sortowania według pierwszej litery, a następnie dla każdego elementu jego „klucz sortujący” jest pierwszą literą.

— Joey Adams

12

Przykład - Załóżmy, że masz listę z każdą pozycją zawierającą informacje o miejscu docelowym lotu i godzinie odlotu. Najpierw sortujesz listę według czasu. Następnie sortujemy je według miejsca docelowego. Jeśli drugi rodzaj jest stabilny , teraz wszystkie loty są powiązane do tego samego miejsca docelowego razem w kolejności rosnącej czasu odlotu. Gdyby to nie było stabilne, nie byłyby w rosnącej kolejności.

— roottraveller

55

Algorytm stabilnego sortowania to taki, który sortuje identyczne elementy w tej samej kolejności, w jakiej pojawiają się na wejściu, podczas gdy niestabilne sortowanie może nie spełniać przypadku. - _{^{Dziękuję mojemu wykładowcowi algorytmów Didemowi Gozupkowi za wgląd w algorytmy}} .

Stabilne algorytmy sortowania:

Sortowanie przez wstawianie
Scal sortowanie
Sortowanie bąbelkowe
Tim Sort
Liczenie Sortuj
Blokuj sortowanie
Quadsort
Sortuj bibliotekę
Shaker do koktajli Sortuj
Sortowanie gnomów
Sortowanie nieparzyste - nawet

Niestabilne algorytmy sortowania:

Sortuj sterty
Sortuj wybór
Sortowanie w skorupkach
Szybkie sortowanie
Introsort (z zastrzeżeniem Quicksort)
Sortowanie drzew
Sortowanie cykliczne
Smoothsort
Sortuj według turniejów (w zależności od Hesapsort)

— snr
źródło

2

Twoje wartości nie są równe. Porównujesz 9,7 i 9,8, ale zgodnie z kontrolą stabilności potrzebujesz takich samych wartości jak 9,7 lub oba 9,8. A potem te same wartości powinny być uporządkowane w tym samym algorytmie stabilnym.

— erhun

1

Nie, aby sprawdzić stabilność, twoje wartości powinny być takie same. Mam na myśli założenie, że używasz dwóch 9,7 i nazwij je w węźle A i węźle B. Jeśli każda kolejność operacji sortowania jest podobna do A, B (zamiast są równe) zrozum, że algorytm sortowania jest stabilny (jak sortowanie po scaleniu). Jeśli kolejność A, B jest zmieniana podczas wielokrotnego sortowania (1. sortuj A, B, a następnie B, A ponownie A, B itd.), Zrozum, że algorytm sortowania jest niestabilny (jak szybkie sortowanie) @ snr

— erhun

@snr [9, 6] nie jest obecny w macierzy wejściowej. Myślę, że miałeś na myśli [9, 8] w ostatnim pasku tablicy.

— Usman

4

@erhun Wydaje mi się, że sortuje tylko według pierwszej liczby (tej przed przecinkiem) i używa drugiej liczby tylko jako odniesienia, aby zobaczyć, że pierwsze 9 różni się od drugiej 9.

— Tiago

20

Stabilność sortowania oznacza, że rekordy z tym samym kluczem zachowują swoją względną kolejność przed sortowaniem i po nim.

Tak więc stabilność ma znaczenie, jeśli i tylko wtedy, gdy rozwiązany problem wymaga zachowania tej względnej kolejności.

Jeśli nie potrzebujesz stabilności, możesz użyć szybkiego algorytmu pochłaniania pamięci z biblioteki, takiego jak heapsort lub quicksort, i zapomnij o tym.

Jeśli potrzebujesz stabilności, jest to bardziej skomplikowane. Stabilne algorytmy mają większe wykorzystanie procesora i / lub pamięci w większym stopniu niż algorytmy niestabilne. Więc jeśli masz duży zestaw danych, musisz wybrać między pobiciem procesora a pamięcią. Jeśli jesteś ograniczony zarówno procesorem, jak i pamięcią, masz problem. Dobry stabilny algorytm kompromisowy to sortowanie według drzewa binarnego; artykuł w Wikipedii ma żałośnie łatwą implementację C ++ opartą na STL.

Możesz przekształcić niestabilny algorytm w stabilny, dodając oryginalny numer rekordu jako klucz ostatniego miejsca dla każdego rekordu.

— Bob Murphy
źródło

1

Stabilne algorytmy, takie jak Scal sortowanie, mają taką samą złożoność O (NlogN) jak Quicksort; jednak stały mnożnik wysiłku jest większy.

— Jonathan Leffler

Tak, a użycie pamięci podczas sortowania scalonego wynosi O (N), podczas gdy w Quicksort jest to O (log N). Powodem, dla którego wspomniałem o Quicksort, jest to, że qsort () jest standardową procedurą biblioteki C, więc jest ona ponownie dostępna.

— Bob Murphy,

1

Najlepsza ogólna odpowiedź IMHO. technika wielu klawiszy wspomniana w innych jest interesująca, ale przereklamowana; jest prosty do zastosowania, ale zwykle jest znacznie wolniejszy niż oczywiste alternatywy (wystarczy użyć jednego sortowania z porównaniem wielu klawiszy; lub posortować według pierwszego klucza, a następnie zidentyfikować i posortować listy podrzędne z duplikatami). Fakt, że stabilne sortowanie daje przewidywalny wynik, może być ważny w niektórych aplikacjach. W szczególności, jeśli masz dwie listy wejściowe A, B, które są identyczne, z wyjątkiem listy B ma dodatkowy wpis, wyniki dla stabilnego sortowania będą identyczne, z wyjątkiem tego, że B ma ten sam dodatkowy wpis. I +1 za ostatnie pgph.

— greggo,

16

To zależy od tego, co robisz.

Wyobraź sobie, że masz kilka rekordów osób z polem imienia i nazwiska. Najpierw posortuj listę według imienia. Jeśli następnie posortujesz listę za pomocą stabilnego algorytmu według nazwiska, będziesz mieć listę posortowaną według imienia ORAZ nazwiska.

— svens
źródło

4

Myślę, że masz na myśli „nazwisko I imię”. Nazwisko to zazwyczaj nazwisko.

— Bacon Bits

14

Istnieje kilka powodów, dla których stabilność może być ważna. Jednym z nich jest to, że jeśli dwa rekordy nie muszą być zamieniane przez ich zamianę, możesz spowodować aktualizację pamięci, strona jest oznaczona jako brudna i należy ją ponownie zapisać na dysku (lub innym wolnym nośniku).

— Clinton Pierce
źródło

Co zamiana rekordów ma wspólnego ze stabilnością?

— user1683793

4

Mówi się, że algorytm sortowania jest stabilny, jeśli dwa obiekty z jednakowymi kluczami pojawią się w tej samej kolejności w posortowanym wyjściu, tak jak pojawiają się w nieposortowanej tablicy wejściowej. Niektóre algorytmy sortowania są z natury stabilne, takie jak sortowanie wstawiane, sortowanie scalone, sortowanie bąbelkowe itp. Niektóre algorytmy sortujące nie są takie jak sortowanie sterty, szybkie sortowanie itp.

Jednak każdy algo sortujący, który nie jest stabilny, można zmodyfikować, aby był stabilny. Mogą istnieć algo specyficzne sposoby sortowania, aby uczynić go stabilnym, ale ogólnie każdy algorytm sortowania oparty na porównaniu, który nie jest stabilny z natury, można zmodyfikować, aby był stabilny, zmieniając operację porównywania kluczy, tak aby porównanie dwóch kluczy uwzględniało pozycję jako współczynnik dla obiektów z jednakowymi kluczami.

Odniesienia: http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_alameterm#Stability

— roottraveller
źródło

3

Wiem, że istnieje wiele odpowiedzi na to, ale dla mnie ta odpowiedź , przez Robert Harvey , podsumował to znacznie wyraźniej:

Sortowanie stabilne to takie, które zachowuje pierwotną kolejność zbioru wejściowego, przy czym algorytm [niestabilny] nie rozróżnia dwóch lub więcej elementów.

Źródło

— John R Perry
źródło

1

Jeśli założysz, że to, co sortujesz, to tylko liczby i tylko ich wartości identyfikują / rozróżniają je (np. Elementy o tej samej wartości są identyczne), to kwestia stabilności sortowania jest bez znaczenia.

Jednak obiekty o tym samym priorytecie w sortowaniu mogą być różne, a czasem ich względna kolejność jest znaczącą informacją. W takim przypadku niestabilne sortowanie powoduje problemy.

Na przykład masz listę danych, która zawiera koszt czasu [T] wszystkich graczy, aby oczyścić labirynt z poziomem [L] w grze. Załóżmy, że musimy uszeregować graczy według szybkości, z jaką czyszczą labirynt. Obowiązuje jednak dodatkowa zasada: gracze, którzy czyszczą labirynt wyższym poziomem, zawsze mają wyższą rangę, bez względu na to, ile kosztują czas.

Oczywiście możesz spróbować zmapować sparowaną wartość [T, L] na liczbę rzeczywistą [R] za pomocą algorytmu zgodnego z regułami, a następnie uszeregować wszystkich graczy o wartości [R].

Jeśli jednak możliwe jest stabilne sortowanie, możesz po prostu posortować całą listę według [T] (najpierw Szybsi gracze), a następnie według [L]. W takim przypadku względna kolejność graczy (według kosztu czasu) nie zmieni się po zgrupowaniu ich według poziomu oczyszczonego labiryntu.

PS: oczywiście podejście polegające na dwukrotnym sortowaniu nie jest najlepszym rozwiązaniem konkretnego problemu, ale wystarczy wyjaśnić kwestię plakatu.

— M. Ciel
źródło

0

Sortowanie stabilne zawsze zwróci to samo rozwiązanie (permutację) na tym samym wejściu.

Na przykład [2,1,2] będzie sortowane przy użyciu sortowania stabilnego jako permutacji [2,1,3] (najpierw jest indeks 2, następnie indeks 1, a następnie indeks 3 w posortowanym wyjściu) Oznacza to, że dane wyjściowe są zawsze tasowane w ten sam sposób. Inną niestabilną, ale wciąż prawidłową permutacją jest [2,3,1].

Szybkie sortowanie nie jest stabilnym sortowaniem, a różnice w permutacji między tymi samymi elementami zależą od algorytmu pobierania osi przestawnej. Niektóre implementacje pobierają losowo, co umożliwia szybkie sortowanie, dając różne kombinacje na tym samym wejściu przy użyciu tego samego algorytmu.

Algorytm stabilnego sortowania jest konieczny deterministyczny.

— Luka Rahne
źródło

2

Nie to oznacza stabilność. Zobacz en.wikipedia.org/wiki/Sorting_alameterm#Stability

— Luís Oliveira

Powinienem poprawić ostatnie zdanie, ponieważ sortowanie niestabilne może wypisywać inne rozwiązanie nawet w ramach tej samej implementacji, gdzie dowolny sortowanie stabilne daje to samo rozwiązanie.

— Luka Rahne

1

Dlaczego -1? Czy ktoś może wskazać, co jest tutaj nie tak? Nie jest to rodzaj stabilnego sortowania, ale to, co ma sort stabilny właściwości.

— Luka Rahne,

To, czy sortowanie jest deterministyczne, czy nie, nie określa, czy jest stabilne. Potrafię napisać niestabilny deterministyczny algorytm sortowania, definiując inne zachowanie zrywające powiązania (na przykład poprzez dzielenie części niekluczowych). Sortowanie stabilne w szczególności oznacza, że wstępnie posortowana względna kolejność elementów jest zachowywana podczas sortowania powiązań. Przykładem wyjściu stabilnego rodzaju: sort([(5,3),(1,5),(3,3),(1,3)], x) => [(1,5),(1,3),(3,3),(5,3)]. Potrafię dokonać deterministycznego sortowania, które zawsze (deterministycznie) generuje: [(1,3),(1,5),(3,3),(5,3)]ale to nie jest stabilny sort.

— cowbert

@cowbert Jest to bardziej stwierdzenie o miłej własności, jaką posiada każdy stabilny rodzaj. Nie ma znaczenia, czy używany jest stabilny algorytm sortowania lub implementacja, za każdym razem będzie taki sam wynik. Trudniej jest utrzymać taką właściwość wśród różnych niestabilnych implementacji sortowania.

— Luka Rahne

0

Więcej przykładów powodów, dla których chciałem mieć stabilne rodzaje. Bazy danych są częstym przykładem. Weźmy pod uwagę bazę danych transakcji, która zawiera | nazwisko, datę | czas zakupu, numer produktu, cenę. Powiedzmy, że baza danych jest zwykle sortowana według daty | godziny. Następnie powstaje zapytanie, aby utworzyć posortowaną kopię bazy danych według nazwiska |, ponieważ stabilny sort zachowuje pierwotną kolejność, mimo że porównanie zapytań dotyczy tylko nazwiska | transakcje dla każdego nazwiska | być w porządku czasowym danych.

Podobnym przykładem jest klasyczny Excel, który ogranicza sortowanie do 3 kolumn jednocześnie. Aby posortować 6 kolumn, sortowanie odbywa się przy użyciu najmniej znaczących 3 kolumn, a następnie sortowanie z najbardziej znaczącymi 3 kolumnami.

Klasycznym przykładem stabilnego sortowania według rzutu jest sorter kart, używany do sortowania według pola bazowych 10 kolumn numerycznych. Karty są posortowane od najmniej znaczącej cyfry do najbardziej znaczącej cyfry. Przy każdym przejściu odczytywana jest talia kart i rozdzielana na 10 różnych pojemników zgodnie z cyfrą w tej kolumnie. Następnie 10 pojemników kart umieszcza się z powrotem w zasobniku wejściowym w kolejności (karty „0” najpierw, karty „9” na końcu). Następnie następna kolumna jest wykonywana przez następną kolumnę, aż wszystkie kolumny zostaną posortowane. Rzeczywiste urządzenia do sortowania kart mają ponad 10 pojemników, ponieważ na karcie znajduje się 12 stref, kolumna może być pusta, a pojemnik zawiera błąd odczytu. Aby posortować litery, potrzebne są 2 przejścia na kolumnę, 1. przejście dla cyfry, 2. przejście dla strefy 12 11.

Później (1937) istniały maszyny do zestawiania kart (scalania), które mogły łączyć dwie talie kart przez porównywanie pól. Dane wejściowe stanowiły dwie już posortowane talie kart, talia główna i talia aktualizacji. Moduł zbierający połączył dwa pokłady w nowy pojemnik na materiały i pojemnik na archiwum, który był opcjonalnie używany do głównych duplikatów, tak aby nowy główny pojemnik miał karty aktualizacji tylko w przypadku duplikatów. Prawdopodobnie była to podstawa idei oryginalnego sortowania scalającego (od dołu do góry).

— rcgldr
źródło