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

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

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.

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)

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.

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.

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

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

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

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.

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.

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