Wikireporter:Zeroos/Brudnopis7

Heap sort [sortowanie przez kopcowanie]:

NIESTABILNY

Wystarczy przeanalizować kopiec tego typu: [gdzie x to nieznane liczby, spełniające założenia kopca - w przykładzie nie mają ona znaczenia. Podane liczby są tylko przykładowe. Ważne, aby była zachowana między nimi odpowiednia relacja. Nigdy nie porównujemy takich samych liczb, więc nie ma różnicy, czy rozpatrujemy większe/mniejsze lub równe, czy większe/mniejsze]

                  x
          6                8
       5     x          3     5.
      x x   x x        x x   x  1
            

W najbliższej iteracji [podczas sortowania] x zostanie dodane do tablicy posortowanych liczb, a 1 zajmie jego miejsce. Następnie będziemy musieli przywrócić właściwości kopca, co poskutkuje przeniesieniem 5. w miejsce 8, a 8 w miejsce 1. Skutek tego jest taki, że 5. znalazło się w drzewie przed 5, czyli ich kolejność zmieniła się. Aby udowodnić, iż algorytm jest niestabilny wypadałoby jeszcze znaleźć przypadek, kiedy ta kolejność nie zmieni się. Może to być np. poprzedni przykład, tyle że z podmienioną prawą gałązią zamiast lewej:

                  x
             8              6
          5     3         x   5.
        x  x   x x       x x   1    

Teraz 5 zostanie dodana do posortowanej tablicy przed 5. .

Merge sort [sortowanie przez scalanie]:

STABILNY

Algorytm Mergesort jest stabilnym algorytmem sortowania, ponieważ każde dwa elementy w tablicy początkowej będą kiedyś musiały być ze sobą porównane. Dodatkowo, element, który był pierwszy w ciągu do posortowania będzie też pierwszym atrybutem dla funkcji porównującej, dzięki czemu istnieje możliwość zachowania ich kolejności w posortowanym ciągu.

Quick sort [szybkie sortowanie]:

NIESTABILNY

Przykładowy ciąg: 1 5 2 3 5. 2. 8 3.

Jeśli za element osiowy weźmiemy 3. to 5 już po pierwszej iteracji zostanie przeniesiona za 5., czyli ich kolejność się nie zmieni. Kolejność trójek jednak pozostanie taka sama, więc algorytm ten jest NIESTABILNY.

Counting sort [sortowanie przez zliczanie]

STABILNY LUB NIESTABILNY

Prostrza implementacja tego algorytmu jest niestabilna. Wynika to z faktu, że nie operujemy na żadnych wskaźnikach do obiektów, ani obiektach, tylko zliczamy je w taki sposób, że np. 3 i 3. są nierozróżnialne. Np. sortujmy tablicę intów: 3 3. Aby to zrobić tworzymy tablicę czteroelementową i zwiększamy wartość pod indeksem 3 dwukrotnie o jeden. W tym momencie obie trójki są nierozróżnialne, ponieważ stały się one 'tylko' trójką.

Można jednak zaimplementować ten algorytm tak, aby był stabilny. Wymaga to jednak o n [ilość elementów w tablicy] więcej pamięci. Łatwo sobie wyobrazić jak będzie teraz wyglądał ten algorytm: po prostu trzymamy referencje do obiektów, a nie ich 'odpowiedniki'.

Bucket sort [sortowanie kubełkowe]

STABILY

Algorytm sortowania kubełkowego jest stabilny, ponieważ dwa identyczne elementy na pewno trafią do tego samego kubełka. Trafią one doń w kolejności takiej, w jakiej były w ciągu do posortowania, więc można zachować ich kolejność w ciągu posortowanym.