Algorytmy sortujące stanowią jedne z najpopularniejszych algorytmów wykorzystywanych w językach programowania. Z uwagi na fakt, że sortowanie stanowi bardzo istotne zagadnienie dotyczące oprogramowania, powstało bardzo wiele algorytmów, które w lepszy lub gorszy sposób radzą sobie z tym problemem. Sortowane mogą być nie tylko zmienne tablicowe, ale również inne struktury, jak na przykład listy.

Cechą charakterystyczną dla niektórych algorytmów sortujących jest to, iż pracują one w miejscu. Oznacza to, że podczas procesu sortowania jedynie stała ilość elementów tablicy wejściowej przechowywana jest poza nią, więc algorytmy, niedziałające w miejscu potrzebują dodatkowej pamięci.

Najważniejszym parametrem, określającym algorytm sortowania jest jego złożoność. Można udowodnić, iż dolna granica złożoności algorytmu, który porównuje elementy tablicy wejściowej to n*lg n. Bariera ta może zostać przekroczona przez algorytmy niewykonujące porównań. Przykładami takich algorytmów są: sortowanie przez zliczanie, sortowanie pozycyjne oraz kubełkowe. Uniwersalnym i jednocześnie najszybszym w ogromnej większości przypadków jest algorytm zwany QuickSort. Do innych jego zalet należą prostota oraz zwięzłość.

Sortowanie kubełkowe, zwane też koszykowym (ang. bucket sort)

To sortowanie, gdzie przedział liczb podlegających sortowaniu (założeniem jest, że posiadają rozkład jednostajny) podzielony jest na n przedziałów jednakowej długości (tzw. kubełków). Następuje posortowanie zawartości kubełków, następnie ich analiza i prezentacja uporządkowanego ciągu liczb.

Sortowanie kubełkowe jest algorytmem, działającym w czasie liniowym (O(n)). Liczby, które mają być nim posortowane muszą zawierać się w przedziale [0;1) oraz powinny być w nim dość równo rozłożone. Działanie algorytmu polega na podzieleniu przedziału [0;1) na określoną liczbę równych podprzedziałów (kubełków). W kolejnym kroku każda liczba przeznaczona do posortowania jest umieszczana w odpowiednim kubełku. W celu otrzymania posortowanych liczb wpierw dokonuje się sortowania liczb w każdym kubełku, a później łączy się je po kolei. Do reprezentowania kubełków najłatwiej użyć jest struktur danych nazywanych listami. Algorytmem służącym posortowaniu kubełków może być sortowanie przez wstawianie. Pomimo, że jego złożoność wynosi O(n2) to ogólnie sortowanie kubełkowe posiada złożoność rzędu O(n). Bierze się to z faktu, iż dane wejściowe są rozłożone równomiernie w przedziale [0;1).W sytuacji, gdy trzeba posortować liczby znajdujące się poza przedziałem [0;1), należy każdą z tych liczb podzielić przez sumę największej liczby z danych ciągu oraz liczby 1. Spowoduje to, że wszystkie liczby znajdą się w zadanym przedziale. W tym przypadku do największej liczby należy dodać 1, gdyż w przypadku dzielenia właśnie tej liczby jako wynik otrzymamy 1, a liczba ta nie należy do podanego wyżej przedziału.

Sortowanie bąbelkowe (ang. bubble sort)

To sortowanie, które polega na przeglądaniu w kolejności elementów sortowanego ciągu i zamianę miejscami elementów ze sobą sąsiadujących w taki sposób, aby zachowywały relację porządkującą. Dzięki temu elementy mniejsze wędrują na początek ciągu. Dla n elementów rozpatrywanego ciągu złożoność algorytmu wynosi O(n2). Algorytm sortowania bąbelkowego jest algorytmem stabilnym.

Często podczas pisania programu, można spotkać się z sytuacją wystąpienia nieposortowanych liczb. Przykładowo, istniej tablica wypełniona liczbami, ułożonymi w różnej kolejności i powstaje potrzeba posortowania jej tak, aby najmniejsze elementy znalazły się na jej początku, a największe na końcu. W takiej sytuacji możemy zastosować chyba najprostszy sposób sortowania, a mianowicie sortowanie bąbelkowe. Jego nazwa pochodzi stąd,, że podczas tego sortowani większe elementy ("cięższe bąbelki") przesuwa się na koniec, tak jak gdyby spadały.

Napisanie programu, który sortuje kilkuelementową tablicę jest bardzo łatwe. Oprócz samej tablicy potrzebne są dodatkowo trzy zmienne: dwie liczbowe (jedna do tymczasowego przechowywania elementów a drugą jest licznik pętli) oraz jedna logiczna (jeżeli algorytm napotka, dwie sąsiadujące ze sobą liczby ułożone w niewłaściwej kolejności, ustawi wartość tej zmiennej na fałsz). Na początku należy napisać pętlę typu repeat, którą ma się skończyć, gdy zmienna logiczna przyjmie wartość prawda. Następnie, w kolejności, od pierwszego do przedostatniego elementu iterujemy tablicę. Jeżeli napotkamy sytuację, gdzie następny (w stosunku do aktualnie ustalonego) element jest mniejszy od aktualnego, ustawiamy wartość zmiennej logicznej na fałsz (tablica nie będzie jeszcze posortowana) zamieniając te dwa elementy miejscami. Przed rozpoczęciem iteracji tablicy, na początku głównej pętli należy koniecznie ustawić wartość zmiennej logicznej na prawda i dopiero w sytuacji, gdy okaże się, iż tablica nie jest posortowana, wartość tej zmiennej zostanie zmieniona na fałsz. Jeżeli tablica zostanie posortowana, wartością zmiennej zostanie prawda i pętla zakończy swoje działanie.

Sortowanie bąbelkowe z kresem górnym

Może zaistnieć sytuacja, gdzie tablica będzie już posortowana, zanim dokonamy n-1 przebiegów bądź po k krokach, więcej niż k elementów od końca znajdować się będzie na właściwym miejscu. Taki problem również można ominąć. Należy do programu dołożyć zmienną, która będzie reprezentowała pozycję, w której miała miejsce ostatnia zamiana elementów z tablicy. Zmienna ta jest kresem kolejnego przebiegu. Taki wariant sortowania nosi nazwę sortowania bąbelkowego z kresem górnym.

Sortowanie poprzez wybór (ang. selectsort)

To sortowanie, gdzie przy każdym kroku algorytm znajduje najmniejszy element sortowanego ciągu, następnie przenosi ten element do kolejnej pozycji ciągu wynikowego (poprzez zmianę elementów miejscami).

Sortowanie poprzez wstawianie (ang. insertion sort)

Sortowanie poprzez wstawienie jest algorytmem, którego złożoność wynosi O(n2). Algorytm ten jest skuteczny w przypadku niewielkiej ilości danych. Sortowanie przez wstawianie jest jednym z najprostszych i najbardziej znanych algorytmów sortujących. Jest on stabilny oraz działa w miejscu więc nie wymaga dodatkowo pamięci. W praktyce ten algorytm często stosowany jest nieświadomie podczas zabierania kart do gry ze stołu. Gracze biorąc po jednej karcie wstawiają ją w określone miejsce względem kart trzymanych w dłoni.

Sortowanie poprzez zliczanie (ang. counting sort)

Sortowanie poprzez zliczanie to jeden z najszybciej działających algorytmów sortowania, będąc przy tym łatwym do wytłumaczenia. Sortowanie to charakteryzuje się złożonością O(n), tak więc działa ono w czasie liniowym. Pomimo swych zalet, sortowanie to posiada dwie zasadnicze wady. Pierwszą wadą jest to, że w przypadku tego sortowania wykorzystywana jest dodatkowa pamięć (więc nie jest sortowaniem w miejscu), drugą natomiast fakt, że tym sposobem sortować można tylko liczby całkowite i to z pewnego przedziału. Niewiadomo do końca dlaczego, lecz algorytm ten pomimo swej prostoty nie jest ani powszechnie znany, ani używany.

Sortowanie pozycyjne (ang. radix sort)

Sortowanie to wykorzystuje się do porządkowania elementów, składających się z szeregu pozycji (elementami mogą być liczby, w których pozycjami są kolejne cyfry, wyrazy - gdzie elementami są litery bądź inne dane, jak np. daty). Podczas stosowania tego algorytmu wymagane jest użycie innego (koniecznie stabilnego) algorytmu sortującego. Jeżeli jako dodatkowego sortowania zastosuje się sortowanie przez zliczanie, algorytm sortowania pozycyjnego będzie działał w czasie O(n). Sortowanie to stosowane jest nie tylko w przypadku liczb lub wyrazów. Algorytmem tym z powodzeniem można sortować także inne dane, np. daty. Należy jednak pamiętać, by sortować je poczynając od pozycji mniej znaczących. Jeżeli chodzi o daty to najpierw sortuje się je według dni, następnie według miesięcy i na samym końcu według roku. Sortowanie pozycyjne można również zastosować do posortowania rekordów w bazie danych. Przykładowo chcemy uporządkować książkę telefoniczną gdzie kluczem są nazwiska, a w sytuacji gdyby się powtarzały to imiona, a w sytuacji identyczności nazwisk i imion kolejnym kluczem ma być numer telefonu. W celu otrzymania takiego wyniku należy książkę telefoniczną ułożyć początkowo według numeru telefonu, następnie według imion i na końcu po nazwiskach. Złożoność obliczeniowa tego sortowania z pewnością będzie dużo większa niż O(n), co wynika z faktu, iż do posortowania takich elementów jak nazwiska trudno jest zastosować sortowanie przez zliczanie.

Jeżeli chodzi o sortowanie wyrazów, to sytuacja jest podobna jak w przypadku sortowania liczb. W przypadku wyrazów pozycje stanowią poszczególne litery. Istnieje jednak pewna różnica, jeżeli chodzi o porządkowanie wyrazów o różnej długości. W takich sytuacjach odpowiednią liczbę znaków dopisuje się za wyrazem, inaczej niż miało to miejsce w przypadku liczb. Znak ten traktowany musi znajdować się wyżej w danym alfabecie, aniżeli wszystkie inne znaki (np. spacja).

Sortowanie QuickSort

To chyba najbardziej popularny algorytm sortowania. Wpływają na to dwa istotne fakty. Po pierwsze, sortowanie to jest bardzo szybkie (wskazuje już na to sama nazwa), po drugie jest proste do implementacji oraz wytłumaczenia. Najgorszy możliwy czas działania algorytmu wynosi O(n2) (ma to miejsce w przypadku, kiedy tablica wejściowa posortowana jest odwrotnie, tzn. że jej wyrazy tworzą ciąg nierosnący), natomiast średni O(n*lg(n)). Pomimo tego jest to w praktyce najszybszy algorytm wykorzystywany w sortowaniu bardzo dużych tablic.

Sortowanie szybkie oparte jest na technice zwanej "dziel i zwyciężaj". Tablica wejściowa dzielona jest (po przestawieniu pewnych jej elementów) na dwie mniejsze tablice. Dowolny element tablicy pierwszej nie może być większy od dowolnego elementu tablicy drugiej. Liczbą, w oparciu, o którą dokonuje się podziału stanowi najczęściej pierwszy element tablicy. W następnym kroku dla dwóch utworzonych podtablic wykonywany jest w rekurencyjny sposób ten sam algorytm. Wywołania te kończą się w momencie, gdy któraś z podtablic zawierała będzie tylko jeden element. Algorytm QuickSort działa w miejscu.