Jak dobrać odpowiedni algorytm sortowania?

Od razu możemy odrzucić algorytmy:

• sortowania bąbelkowego,

• sortowania przez wstawianie,

• sortowania koktajlowego,

• sortowania przez wybieranie.

Algorytmy te stosowane są głównie do poznania zasad działania algorytmów sortowania. Są proste w zrozumieniu, jednak nie znajdują zastosowania w praktyce. Wynika to z faktu, że charakteryzują się one kwadratową złożonością obliczeniowązłożoność obliczeniowazłożonością obliczeniową, a przez to są zdecydowanie mniej efektywne od algorytmów sortowania, które posiadają złożoność $O(n\log n)$.

Przed wyborem algorytmu przyglądamy się danym, z jakimi mamy do czynienia.

• Jeżeli sortujemy słowa, daty lub niewielkie liczby, rozważmy użycie algorytmu sortowania pozycyjnego. Jest on idealny w takich sytuacjach, a dodatkowo charakteryzuje go złożoność obliczeniowa wynosząca $O(n+k)$, gdzie $n$ to liczba elementów do posortowania, a $k$ to liczba znaków w najdłuższym elemencie. Jest to złożoność liniowa, zatem algorytm ten jest jednym z najszybszych algorytmów sortowania.

• Jeśli mamy do czynienia ze zbiorem, w którym występuje niewiele różnych elementów, np. cyfry lub litery powtarzające się wielokrotnie, sortowanie przez zliczanie będzie bardzo dobrym wyborem. Musimy pamiętać, że algorytm ten wymaga użycia dodatkowej pamięci, ponieważ dane zapisywane są tymczasowo w tablicy pomocniczej.

Rozpatrując wybór najlepszej metody, powinniśmy wziąć pod uwagę organizację i strukturę danych, które sortujemy, oraz dostępne miejsce.

• Sortowanie szybkie będzie lepsze, jeżeli sortujemy tablice, a także jeżeli nie mamy do dyspozycji dużej ilości pamięci komputera. Algorytm jest mniej wydajny dla dużej liczby danych.

• Sortowanie przez scalanie działa lepiej dla list, ale wymaga dużej ilości dodatkowej pamięci. Nie zaobserwujemy jednak znacznego spadku wydajności dla dużej liczby danych do sortowania.

Istnieją również algorytmy hybrydowe, często wyspecjalizowane dla jednego konkretnego typu danych. Przykładem takiego algorytmu może być Timsort, używany w języku Python (algorytm Timsort implementuje metodę sort() w listach w języku Python). Tego typu algorytmy są bardzo skomplikowane i wieloetapowe, jednak sprowadzają się do omówionych tutaj algorytmów, użytych w niekonwencjonalny sposób.

Szczególny przypadek

Warto pamiętać o tym, że przedstawione tutaj sposoby użycia algorytmów są typowe i najczęściej spotykane. Możemy jednak znaleźć się w sytuacji, w której te zasady trzeba będzie zmienić. Wówczas nie bójmy się użyć innego niż podany tutaj algorytm, czy go zmodyfikować. Jeżeli czujemy się na siłach, możemy nawet spróbować zaprojektować swój własny algorytm sortowania.

Wyobraźmy sobie, że naszym zadaniem jest przygotowanie algorytmu sortowania zbioru liczb całkowitych. Zależy nam na tym, aby najpierw posortować w kolejności niemalejącej liczby parzyste, a następnie nieparzyste. Wynikiem działania algorytmu dla zbioru A = {5, 1, 2, 6, 4, 3, -3} byłby więc zbiór B = {2, 4, 6, -3, 1, 3, 5}.

Taki algorytm możemy zaprojektować na kilka sposobów. Jeden z najbardziej intuicyjnych polega na dzieleniu zbioru $A$ na dwa podzbiory: liczb parzystych i nieparzystych. Następnie sortujemy każdy ze zbiorów niezależnie, układając elementy w kolejności niemalejące i wreszcie łączymy oba zbiory.

Jaki algorytm wybrać?

Słownik