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.
Algorytmy sortowania można podzielić ze względu na:
Przykładowo algorytm Sortowania Szybkiego - złożoność oczekiwana to Θ(n·logn), ale pesymistyczna to Θ(n2). Niektóre algorytmy mają taką samą złożoność oczekiwaną i pesymistyczną jak Sortowanie Bąbelkowe Θ(n2).
Algorytmy sortujące za pomocą porównań mają dolną granicę złożoności Θ(n·logn).
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.
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.
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.
| Nazwa | Stabilny | W miejscu | Zł. oczekiwana | Zł. Pesymistyczna | Dodatkowa pamięć |
|---|---|---|---|---|---|
| Sortowanie Bąbelkowe | tak | tak | Θ(n2) | Θ(n2) | Θ(1) |
| Sortowanie przez Wstawianie | tak | tak | Θ(n2) | Θ(n2) | Θ(1) |
| Sortowanie przez Scalanie | tak | nie | Θ(n·logn) | Θ(n·logn) | Θ(n) |
| Sortowanie przez Zliczanie | tak | nie | Θ(n + k) | Θ(n + k) | Θ(k) |
| Sortowanie Kubełkowe | tak | nie | Θ(n) | Θ(n) | Θ(k) |
| Sortowanie Pozycyjne | tak | nie | Θ(d(n + k)) | Θ(d(n + k)) | Θ(n + k) |
| Sortowanie Gnoma | nie* | tak | Θ(n2) | Θ(n2) | Θ(1) |
| Sortowanie Biblioteczne | tak | nie | Θ(n·logn) | Θ(n2) | Θ(1) |
| Sortowanie przez Wybór | nie* | tak | Θ(n2) | Θ(n2) | Θ(1) |
| Sortowanie Shella | nie | - | - | - | - |
| Sortowanie Grzebieniowe | nie | - | Θ(n·logn)** | Θ(n·logn)** | - |
| Sortowanie Szybkie | nie | - | Θ(n·logn) | Θ(n2) | - |
| Sortowanie Introspektywne | nie | - | Θ(n·logn) | Θ(n·logn) | - |
| Sortowanie przez Kopcowanie | nie | - | Θ(n·logn) | Θ(n·logn) | - |
| Sortowanie Naleśnikowe | tak | tak | Θ(n2) | Θ(n2) | Θ(1) |
* można zmienić kod, aby sortował stabilnie
** złożoność prawdopodobna