Czy ktoś może wyjaśnić, co znaczy "stabilny" i "niestabilny" w odniesieniu do różnych algorytmów sortowania> W jaki sposób można ustalić, czy algorytm jest stabilny, czy nie, i jakie aplikacje zwykle mają niestabilne algorytmy sortowania (skoro są niestabilne)?Co oznacza "stabilny" i "niestabilny" dla różnych algorytmów sortowania?
Jeśli algorytm sortowania jest określany jako "niestabilny", oznacza to, że w przypadku elementów o takim samym połoŜeniu kolejność elementów powiązanych nie ma takiego samego znaczenia w przypadku kolejnych rodzajów tego zbioru. W przypadku sortowania "stabilnego", powiązane pozycje zawsze kończą się w tej samej kolejności po posortowaniu.
Dla przykładu aplikacji algorytm szybkiego sortowania nie jest stabilny. To działałoby dobrze dla czegoś takiego jak sortowanie akcji według priorytetu (jeśli dwie akcje mają równy priorytet, nie będziesz prawdopodobnie dbał o to, które elementy remisu są wykonywane jako pierwsze).
Z drugiej strony stabilny algorytm sortowania sprawdza się w przypadku gier typu leaderboard. Jeśli użyjesz sortowania niestabilnego, sortując według punktów (na przykład), użytkownik przeglądający posortowane wyniki na stronie internetowej może doświadczać różnych wyników na odświeżeniach strony, a operacje takie jak stronicowanie przez wyniki nie będą działać poprawnie.
, która została dodana w celu objaśnienia, dlaczego różnica ma znaczenie. –
Nieużywalne rodzaje zwykle dają przewidywalne wyniki, tzn. Nie dają różnych odpowiedzi przy tych samych danych. W związku z tym odświeżanie strony będzie pokazywać inną kolejność równą zmianie wartości innych. Przyczyną niestabilności jest wykorzystanie drzew lub niektórych podobnych struktur danych podczas organizowania danych. –
Warto zauważyć, że częstsze korzystanie ze stabilnych sortowań jest sortowane według wielu kluczy. Na przykład, jeśli masz tablicę obiektów reprezentujących ludzi i chcesz ją posortować według wieku, z powiązaniami podzielonymi przez nazwy (alfabetycznie), możesz sortować najpierw według nazwy, a następnie według wieku, a sortowanie stabilne będzie miało to w stanie, którego szukasz. –
Trwałe sortowanie zachowuje kolejność identycznych elementów. Każdy rodzaj może być stabilny poprzez dodanie indeksu wiersza do klucza. Niestabilne sortowania, takie jak sortowanie sterty i szybkie sortowanie, nie mają z natury tej właściwości, ale są używane, ponieważ zazwyczaj są szybsze i łatwiejsze do kodowania niż stabilne. O ile mi wiadomo, nie ma innych powodów, aby używać niestabilnych rodzajów.
Przechodzenie do punktu powyżej, który Azron wykonał (poniżej twojego punktu) i przykład, który zrobił, oznacza, że sortowanie siatki, które robimy w oknach, jest realizowane w jednym ze stabilnego sortowania? Sortowanie siatki oznacza sortowanie plików w folderze według daty i typu. –
sortowania wykonane w takich obiektach jak menedżer plików i program Excel są stabilne, albo używają stabilnego sortowania, albo stabilizowanej wersji jednego z niestabilnych sortowań. –
Być może byłoby to bardziej odpowiednie na stronie http://programmers.stackexchange.com/ –