Dlaczego sortowanie nie jest stabilne?

Question

Może to być trywialne, ale nie rozumiem, dlaczego domyślna implementacja Selection Sort nie jest stabilna?

W każdej iteracji można znaleźć najmniejszy element w pozostałej tablicy. Po znalezieniu tego minimum możesz wybrać pierwsze minimum, które możesz znaleźć i zaktualizować tylko wtedy, gdy element jest faktycznie mniejszy od niego. Zatem wybrany element w każdej iteracji jest pierwszym minimum - znaczeniem, jest to pierwsze w poprzednim porządku sortowania. Tak więc, według mojego rozumienia, obecny rodzaj nie zniszczy porządku wygenerowanego przez poprzedni sort na równych elementach.

Czego mi brakuje?

Answer 1

mały przykład:

Niech B = B

< b> < b> < a>, < C> (z < b < c)

Po jednym cykl sekwencja jest sortowana, ale kolejność B i b uległa zmianie:

< a>, < b>, < B >, < c>

Ale można jednak wdrożyć Wybory Sortuj stabilny jeśli zamiast przełączania, wstawić wartość minimalną. Ale żeby to było wydajne, powinieneś mieć strukturę danych, która obsługuje wstawianie przy niskim koszcie lub w inny sposób kończy się kwadratową złożonością.

Answer 2

Problemem jest to, że wybór rodzaj zamienia elementy z przodu matrycy w miejscu zwolnionym przez minimum elementu, które mogą zepsuć się w uporządkowanej kolejności. Na przykład załóżmy, że mam sortowaniu

(4, 0), (4, 1), (1, 0) 

selekcji Sortuj najpierw zamienia (1, 0) do przodu:

(1, 0), (4, 1), (4, 0) 

A teraz (4, 0) i (4, 1) są nieczynne od miejsca, w którym zaczęły się w ten sposób. Uruchomienie tego do końca pozostawia elementy w tej kolejności, a 4 są nieczynne.

Mam nadzieję, że to pomoże!

Answer 3

Stabilne środki nie wylicza dalej, jeśli elementy są już posortowane, ale to obliczyć do końca dlatego nie jest stabilna.