Porównanie algorytmów sortowania

Nie ma jednego najszybszego algorytmu sortowania. Niektóre są proste, ale wolne, inne są szybkie na losowych danych, ale potykają się na posortowanych, a jeszcze inne w ogóle nie sortują przez porównania. Wyścig wszystkich ośmiu na tej samej liście pokazuje różnice na pierwszy rzut oka.

Osiem torów słupków, po jednym na algorytm sortowania; niektóre są już posortowane i zielone, a inne wciąż nieposortowane
Osiem torów słupków, po jednym na algorytm sortowania; niektóre są już posortowane i zielone, a inne wciąż nieposortowane

Trzy rodziny

Sortowanie bąbelkowe, przez wybieranie i przez wstawianie to proste sortowania. Porównują i zamieniają wartości leżące blisko siebie i na losowej liście potrzebują czasu proporcjonalnego do n². Sortowanie przez scalanie, szybkie i przez kopcowanie sprytnie dzielą pracę i potrzebują czasu proporcjonalnego do n log n, a to najlepsze, co może osiągnąć sortowanie, które może tylko pytać, która z dwóch wartości jest większa. Sortowanie pozycyjne i przez zliczanie w ogóle pomijają to pytanie: korzystają z samych cyfr lub wartości, co działa tylko dla kluczy takich jak małe liczby całkowite.

Mierzenie pracy

Wyścig sortowań liczy jedną operację za każde porównanie, każdą odczytaną cyfrę lub wartość i każdą zamianę lub przesunięcie. Przy 40 losowych wartościach daje to około 120 dla sortowania przez zliczanie, 240 dla pozycyjnego, 260 dla szybkiego, 380 dla sortowania przez scalanie, 490 dla sortowania przez kopcowanie, po około 820 dla sortowania przez wybieranie i przez wstawianie oraz ponad 1100 dla bąbelkowego. Prawdziwe komputery zwracają też uwagę na pamięć: sortowanie szybkie jest w praktyce zwykle szybsze, niż sugeruje jego licznik, a sortowanie przez kopcowanie wolniejsze, z powodu tego, jak poruszają się po liście.

Dane wejściowe mają znaczenie

Na prawie posortowanej liście sortowanie przez wstawianie potrzebuje tylko około 50 operacji dla 40 wartości, a bąbelkowe około 90, bo każda wartość jest blisko swojego miejsca. Na odwróconej liście te same dwa potrzebują 1560, to ich najgorszy przypadek. Sortowaniu przez wybieranie, przez kopcowanie, przez scalanie, pozycyjnemu i przez zliczanie kolejność prawie nie robi różnicy. Sortowanie szybkie z medianą z trzech dobrze radzi sobie z listami posortowanymi i odwróconymi, ale przy naiwnym wyborze elementu osiowego posortowana lista jest jego najgorszym przypadkiem. Mało różnych wartości spowalnia sortowanie szybkie, bo równe wartości trafiają na jedną stronę.

Pamięć i stabilność

Sortowanie bąbelkowe, przez wybieranie, przez wstawianie, szybkie i przez kopcowanie działają w miejscu, z niewielką dodatkową pamięcią albo bez niej. Sortowanie przez scalanie, pozycyjne i przez zliczanie potrzebują bufora tak długiego jak lista. Sortowanie stabilne zachowuje pierwotną kolejność równych wartości: bąbelkowe, przez wstawianie, przez scalanie, pozycyjne i przez zliczanie są stabilne, a przez wybieranie, szybkie i przez kopcowanie nie. Stabilność ma znaczenie, gdy sortujesz rekordy według jednego pola, a potem kolejnego.

Którego użyć

W praktyce używasz sortowania wbudowanego w twój język programowania. Zwykle jest to Timsort, sortowanie przez scalanie, które dla krótkich fragmentów używa sortowania przez wstawianie i jest szybkie na częściowo posortowanych danych, albo introsort, sortowanie szybkie, które w razie potrzeby przechodzi na sortowanie przez kopcowanie, a dla małych części używa sortowania przez wstawianie. Przy wielu małych kluczach całkowitych sortowanie przez zliczanie lub pozycyjne może pokonać oba. Sortowanie bąbelkowe i przez wybieranie służą głównie do nauki.

Wypróbuj

Otwórz wyścig sortowań i naciśnij Odtwórz. Każdy tor to jedno sortowanie na tej samej liście; liczba po prawej liczy jego operacje, a tor robi się zielony, gdy sortowanie się zakończy. Wypróbuj listę prawie posortowaną, odwróconą i z kilkoma różnymi wartościami i zobacz, jak zmienia się kolejność na mecie. Każde sortowanie ma też własną aplikację, w której możesz dokładnie prześledzić je krok po kroku.

Często zadawane pytania

Jaki jest najszybszy algorytm sortowania?

Dla ogólnych danych średnio najszybsze są sortowanie szybkie i przez scalanie (oraz zbudowane na nich hybrydy, jak introsort i Timsort), z n log n. Dla małych kluczy całkowitych sortowanie przez zliczanie i pozycyjne są jeszcze szybsze. Dla krótkich lub prawie posortowanych list wygrywa sortowanie przez wstawianie.

Dlaczego żadne sortowanie przez porównania nie pokona n log n?

Lista n wartości może być ułożona na n! sposobów, a każde porównanie ma dwa wyniki, więc w najgorszym przypadku potrzeba co najmniej log₂(n!) porównań, aby je wszystkie rozróżnić. To około n log₂ n. Sortowanie pozycyjne i przez zliczanie omijają to ograniczenie, bo nie porównują.

Które algorytmy sortowania są stabilne?

Sortowanie bąbelkowe, przez wstawianie, przez scalanie, pozycyjne i przez zliczanie są stabilne w swoich zwykłych wersjach. Sortowanie przez wybieranie, szybkie i przez kopcowanie nie są, bo przenoszą wartości na duże odległości.

Które sortowania potrzebują dodatkowej pamięci?

Sortowanie przez scalanie, pozycyjne i przez zliczanie potrzebują bufora mniej więcej tak długiego jak lista. Bąbelkowe, przez wybieranie, przez wstawianie i przez kopcowanie nie potrzebują jej prawie wcale, a szybkie tylko trochę na rekurencję.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Uruchom wyścig sortowań