Pracujesz w bibliotece uniwersyteckiej.
Jest środek spokojnego popołudnia,
kiedy nagle przybywa dostawa 1280 książek.
Książki zostały ułożone w jednym, długim rzędzie
w losowej kolejności,
a automatyczny system do segregacji jest zepsuty.
Co gorsza, jutro zaczynają się zajęcia,
co oznacza, że z samego rana
książek będą szukać tłumy studentów.
Jak posortować je na czas?
Jeden ze sposobów to rozpoczęcie od pierwszej pary książek z jednego końca.
Jeśli dwie pierwsze książki są dobrze ułożone, zostaw je bez zmian.
W przeciwnym razie zamień je miejscami.
Teraz spójrz na drugą i trzecią książkę,
powtórz proces
i kontynuuj, aż dotrzesz do końca linii.
W końcu natkniesz się na książkę, która powinna być ostatnia.
Zamieniaj ją z każdą kolejną książką,
przesuwając wzdłuż rzędu aż na koniec.
Następnie zacznij od początku i powtórz cały proces,
żeby umieścić przedostatnią książkę na swoim miejscu.
Kontynuuj, aż książki będą posortowane.
Ten sposób to sortowanie bąbelkowe.
Jest łatwe, ale powolne.
W pierwszej rundzie byłoby 1279 porównań,
w kolejnej 1278 i tak dalej,
co w sumie daje 818 560 porównań.
Gdyby każde zajęło tylko sekundę, proces potrwałby ponad dziewięć dni.
Inny sposób rozpoczyna się od ułożenia tylko dwóch pierwszych książek.
Następnie weź trzecią książkę i porównaj do tej stojącej na drugim miejscu.
Jeśli powinna znaleźć się przed nią, zamień je.
Potem porównaj ją do pierwszej książki
i jeśli trzeba, zamień miejscami.
Trzy pierwsze książki są już posortowane.
Dodawaj po jednej nowej książce do posortowanej grupy,
porównując ją i zamieniając z książką stojącą przed nią,
aż trafi na właściwe miejsce.
Ten sposób to sortowanie przez wstawianie.
W odróżnieniu od sortowania bąbelkowego nie trzeba porównywać każdej pary książek.
Każdą książkę będzie trzeba porównać średnio
tylko z połową tych, stojących przed nią.
W tym przypadku całkowita liczba porównań
wyniosłaby 409 280,
co zajęłoby prawie pięć dni.
To wciąż zbyt wiele porównań.
Oto lepszy pomysł.
Najpierw wybierz przypadkową książkę.
Nazwijmy ją przegrodą i porównajmy z pozostałymi książkami.
Następnie podzielmy rząd,
umieszczając wszystkie książki, które mają znaleźć się przed przegrodą po jej lewej,
a te, które powinny stanąć za nią, po jej prawej stronie.
Właśnie oszczędziliśmy mnóstwo czasu.
Już nie będzie trzeba porównywać żadnej z książek po lewej
do tych po prawej stronie.
Teraz patrząc tylko na książki po lewej stronie,
można wybrać przypadkową przegrodę
i oddzielić książki, mające stać przed, od tych, które powinny stanąć za nią.
Można dalej tworzyć takie przegrody,
aż uzyska się wiele małych grup,
z których każdą posortuje się, używając innej strategii.
Każde rozdzielenie wymaga około 1280 porównań.
Jeśli segmenty są w miarę równe,
podzielenie książek na 128 grup po 10 będzie wymagało około siedmiu rund
albo 8960 sekund.
Posortowanie każdej grupy zajmie wtedy około 22 sekund.
Tak czy inaczej ta metoda znana jako sortowanie szybkie
może posortować książki w mniej niż 3,5 godziny.
Ale jest haczyk.
Segmenty mogą okazać się niesymetryczne, co oznacza brak oszczędności czasu.
Na szczęście rzadko się to zdarza.
Dlatego sortowanie szybkie to jedna z najbardziej wydajnych strategii
używanych przez dzisiejszych programistów.
Korzysta się z niej do sortowania towarów w sklepie internetowym według ceny
albo tworzenia listy pobliskich stacji benzynowych,
ułożonych według odległości.
Właśnie udało się skończyć szybkie sortowanie przed czasem.
Za tobą kolejny pracowity dzień w bibliotece.