Sortowanie

Zdarza się, że czasem musimy coś ułożyć w zadanej kolejności. Mówiąc inaczej, musimy coś posortować. Powodów może być wiele. Być może potrzebujemy uporządkowanego ciągu danych, aby móc na nim wykonywać efektywne algorytmy, np. wyszukiwania? A może po chcemy ułatwić życie klientowi i zaprezentować mu posortowaną pod względem ceny listę produktów na stronie? A może po prostu lubimy z dumą patrzeć na naszą kolekcję książek uporządkowaną po nazwiskach autorów? Bez względu na to, jaki jest nasz powód, warto jest znać kilka algorytmów/metod sortowania, aby móc je zastosować, nie tylko na komputerze, ale także i w życiu codziennym.
Zapoznając się z algorytmami sortowania zawartymi w tej sekcji przekonasz się, że przynajmniej kilka z nich swoją intuicję ma silnie powiązaną z otaczającym nas światem. Zastanawiałeś się kiedyś, drogi czytelniku, jak poruszają się bąbelki w napojach gazowanych? A może zwróciłeś uwagę na to, jak układać sobie karty na ręce podczas rozgrywki w brydża? A może zdarzyło Ci się porządkować stos książek na półce? To wszystko, jak się przekonasz, ma swoje odzwierciedlenie w algorytmice.
Istnieje wiele algorytmów sortowania. Jedne prostsze, inne trudniejsze. Jedne wolniejsze, inne wydajniejsze. Omówimy tylko wybrane i, być może, popularniejsze z tych algorytmów. Poniższa animacja w ciekawy sposób pokazuje porównanie kilku algorytmów sortowania pod względem wydajności. Warto do niej zajrzeć i poświęcić chwilę, na prześledzenie przebiegu poszczególnych metod, zanim przejdziesz dalej.
Sorting Algorithms Animations
toptal
Porównanie algorytmów sortowania

Specyfikacja

W naszych algorytmach sortowania będziemy trzymać się poniższej specyfikacji danych wejściowych i wyniku. Niektóre algorytmy, np. ze względu na swoją rekurencyjną naturę, będą potrzebowały jeszcze dodatkowych parametrów, ale ogólny schemat pozostaje ten sam, nie będziemy więc go powielać przy omawianiu każdego algorytmu.

Dane

  • ​
    nn
    — liczba naturalna, ilość elementów w tablicy
  • ​
    A[1..n]A[1..n]
    — tablica
    nn
    wartości całkowitych

Wynik

  • Posortowana niemalejąco tablica
    AA
    ​