Strona główna » Algorytmy » Sortowanie » Wstęp do Sortowania

Wstęp do Sortowania

Cel

Zazwyczaj do posortowania mamy listę n liczb. Ich uporządkowanie polega na otrzymaniu permutacji w której każdy kolejny elementy spełnia określone kryteria. W przypadku sortowania rosnąco będzie to , a w przypadku sortowania malejącego . Spójrzmy na przykładową listę trzech elementów L:={2, 3, 1}. Posortowana lista rosnąco L' to {1, 2, 3}. Możemy to stwierdzić sprawdzające, że 1 ≤ 2 ≤ 3.

Klasyfikacja

Algorytmy sortowania można podzielić ze względu na:

Algorytmy sortujące za pomocą porównań mają dolną granicę złożoności Θ(n·logn).

Inne sortowania

Nie zawsze danymi do posortowania są liczby. Czasami jest to obiekt, którego nie potrafimy porównać. Wtedy ustalamy reguły według którego sortujemy dane. W przypadku wyrazów o kolejności decyduje alfabet. Otrzymujemy wtedy, że a ≤ b ≤ .. ≤ z. Jednak obiekt to może być para liczb, przykładowo punkt (x, y). Wtedy możemy sortować najpierw według wartości x, a potem wartości y.

Bez porównywania

Istnieją algorytmy, które nie porównują elementów. Przykładem takiego algorytmu jest Sortowanie przez Zliczanie. W wymienionej metodzie zliczamy ile razy występuje jaki obiekt, a później odpowiedni wyrzucamy elementy z listy. W ten sposób pomijamy porównania i zamiany elementów kosztem pamięci.

Algorytmy sortujące w miejscu

Dla tego typu algorytmie nie deklarujemy, ani dodatkowej listy pomocniczej, ani listy wynikowej. Taki algorytm operuje bezpośrednio na tablicy zamieniając elementy miejscami. W ten sposób otrzymujemy posortowany ciąg danych. Do takiego algorytmu można zaliczyć sortowanie bąbelkowe.

Porównanie algorytmów

NazwaStabilnyW miejscuZł. oczekiwanaZł. PesymistycznaDodatkowa pamięć
Sortowanie BąbelkowetaktakΘ(n2)Θ(n2)Θ(1)
Sortowanie przez WstawianietaktakΘ(n2)Θ(n2)Θ(1)
Sortowanie przez ScalanietaknieΘ(n·logn)Θ(n·logn)Θ(n)
Sortowanie przez ZliczanietaknieΘ(n + k)Θ(n + k)Θ(k)
Sortowanie KubełkowetaknieΘ(n)Θ(n)Θ(k)
Sortowanie PozycyjnetaknieΘ(d(n + k))Θ(d(n + k))Θ(n + k)
Sortowanie Gnomanie*takΘ(n2)Θ(n2)Θ(1)
Sortowanie BibliotecznetaknieΘ(n·logn)Θ(n2)Θ(1)
Sortowanie przez Wybórnie*takΘ(n2)Θ(n2)Θ(1)
Sortowanie Shellanie----
Sortowanie Grzebieniowenie-Θ(n·logn)**Θ(n·logn)**-
Sortowanie Szybkienie-Θ(n·logn)Θ(n2)-
Sortowanie Introspektywnenie-Θ(n·logn)Θ(n·logn)-
Sortowanie przez Kopcowanienie-Θ(n·logn)Θ(n·logn)-
Sortowanie NaleśnikowetaktakΘ(n2)Θ(n2)Θ(1)

można zmienić kod, aby sortował stabilnie
** złożoność prawdopodobna