QuickSort stabilność algorytm

Question

Quicksort nie jest stabilna, ponieważ wymiana to elementy nieprzylegające.

Proszę, pomóżcie mi zrozumieć to stwierdzenie.

Wiem, jak działa partycjonowanie i jaka jest stabilność. Ale nie mogę dojść do tego, co sprawia, że ​​powyższy powód nie jest stabilny? Następnie sądzę, że to samo można powiedzieć o sortowaniu scalonym - chociaż jest cytowany jako stabilny algorytm.

Answer 1

Rozważmy, co dzieje się w trakcie podziału na następującej tablicy par, w przypadku gdy wykorzystuje się całkowitą komparator (tylko). Ciąg jest właśnie tam, więc mamy dwa elementy, które porównują, jakby były równe, ale w rzeczywistości są odróżnialne.

(4, "first"), (2, ""), (3, ""), (4, "second"), (1, "") 

definicji rodzajem jest stabilny jeżeli po rodzaju, dwa elementy, które porównują jak gdyby równe (dwie 4 S) pojawiają się w tej samej kolejności, potem jak to miało miejsce wcześniej.

Załóżmy zdecydujemy 3 jako pivot. Dwa elementy 4 zakończą się po nim i przed nim 1 i 2 (jest trochę więcej niż to, ignorowałem przesuwanie osi obrotu, ponieważ jest już we właściwej pozycji, ale mówisz, że rozumiesz partycjonowanie).

Quicksorts w ogóle nie daje żadnej szczególnej gwarancji gdzie po partycji będą dwa 4 s i myślę, że większość implementacji odwróci je. Na przykład, jeśli stosujemy Hoare's classic partitioning algorithm tablica jest podzielona w następujący sposób:

(1, ""), (2, ""), (3, ""), (4, "second"), (4, "first") 

co narusza stabilności sortowania.

Ponieważ każda partycja nie jest stabilna, ogólny sort nie jest prawdopodobny.

Jak zauważa Steve314 w komentarzu, sortowanie scalone jest stabilne pod warunkiem, że przy łączeniu, jeśli napotkasz takie same elementy, zawsze wyprowadzasz najpierw ten, który pochodzi z "dolnej części" dwóch połówek, które łączysz razem . Oznacza to, że każde scalenie musi wyglądać tak, gdzie "lewa" jest stroną, która pochodzi z niższego poziomu w oryginalnej tablicy.

while (left not empty and right not empty): 
    if first_item_on_left <= first_item_on_right: 
     move one item from left to output 
    else: 
     move one item from right to output 
move everything from left to output 
move everything from right to output 

Jeżeli <= były < następnie scalanie nie będzie stabilne.

Answer 2

To tak, jak użytkownik ma posortowaną tablicę i sortuje według innej kolumny, czy algorytm sortowania zawsze zachowuje względną kolejność elementów, które różnią się dla poprzedniego klucza sortowania, ale mają taką samą wartość w nowym kluczu sortowania ? Tak więc w algorytmie sortowania, który zawsze zachowuje kolejność elementów (które nie różnią się w nowym kluczu sortowania) jest nazywany "sortowaniem stabilnym".

Answer 3

Rozważmy następującą tablicę parach

{(4,'first');(2,'');(1,'');(4,'second');(3,'')}

Rozważmy 3 jako osi.Podczas biegu szybkiego sortowania, tablica podlega następujące zmiany:

1. {(4,'first');(2,'');(1,'');(4,'second');(3,'')}
2. {(2,'');(4,'first');(1,'');(4,'second');(3,'')}
3. {(2,'');(1,'');(4,'first');(4,'second');(3,'')}
4. {(2,'');(1,'');(3,'');(4,'second');(4,'first')}
5. {(1,'');(2,'');(3,'');(4,'second');(4,'first')}

jasno z powyższego, względna kolejność jest zmieniony. Dlatego mówi się, że szybkie sortowanie nie zapewnia stabilności.