0:00:06.671,0:00:09.067
Pracujesz w bibliotece uniwersyteckiej.

0:00:09.067,0:00:11.397
Jest środek spokojnego popołudnia,

0:00:11.397,0:00:17.741
kiedy nagle przybywa dostawa 1280 książek.

0:00:17.741,0:00:21.510
Książki zostały ułożone[br]w jednym, długim rzędzie

0:00:21.510,0:00:23.288
w losowej kolejności,

0:00:23.288,0:00:26.881
a automatyczny system[br]do segregacji jest zepsuty.

0:00:26.881,0:00:29.597
Co gorsza, jutro zaczynają się zajęcia,

0:00:29.597,0:00:32.005
co oznacza, że z samego rana

0:00:32.005,0:00:36.107
książek będą szukać tłumy studentów.

0:00:36.107,0:00:39.353
Jak posortować je na czas?

0:00:39.353,0:00:44.779
Jeden ze sposobów to rozpoczęcie [br]od pierwszej pary książek z jednego końca.

0:00:44.779,0:00:48.626
Jeśli dwie pierwsze książki[br]są dobrze ułożone, zostaw je bez zmian.

0:00:48.626,0:00:50.840
W przeciwnym razie zamień je miejscami.

0:00:50.840,0:00:53.216
Teraz spójrz na drugą i trzecią książkę,

0:00:53.216,0:00:54.879
powtórz proces

0:00:54.879,0:00:57.755
i kontynuuj, aż dotrzesz do końca linii.

0:00:57.755,0:01:01.185
W końcu natkniesz się na książkę,[br]która powinna być ostatnia.

0:01:01.185,0:01:04.710
Zamieniaj ją z każdą kolejną książką,

0:01:04.710,0:01:09.170
przesuwając wzdłuż rzędu aż na koniec.

0:01:09.170,0:01:12.225
Następnie zacznij od początku[br]i powtórz cały proces,

0:01:12.225,0:01:15.510
żeby umieścić przedostatnią[br]książkę na swoim miejscu.

0:01:15.510,0:01:18.821
Kontynuuj, aż książki będą posortowane.

0:01:18.821,0:01:21.862
Ten sposób to sortowanie bąbelkowe.

0:01:21.862,0:01:24.156
Jest łatwe, ale powolne.

0:01:24.156,0:01:29.331
W pierwszej rundzie[br]byłoby 1279 porównań,

0:01:29.331,0:01:33.623
w kolejnej 1278 i tak dalej,

0:01:33.623,0:01:38.542
co w sumie daje 818 560 porównań.

0:01:38.542,0:01:44.273
Gdyby każde zajęło tylko sekundę,[br]proces potrwałby ponad dziewięć dni.

0:01:44.273,0:01:48.569
Inny sposób rozpoczyna się od ułożenia[br]tylko dwóch pierwszych książek.

0:01:48.569,0:01:53.613
Następnie weź trzecią książkę i porównaj[br]do tej stojącej na drugim miejscu.

0:01:53.613,0:01:57.173
Jeśli powinna znaleźć się[br]przed nią, zamień je.

0:01:57.173,0:01:59.641
Potem porównaj ją do pierwszej książki

0:01:59.641,0:02:01.682
i jeśli trzeba, zamień miejscami.

0:02:01.682,0:02:03.880
Trzy pierwsze książki są już posortowane.

0:02:03.880,0:02:07.652
Dodawaj po jednej nowej książce [br]do posortowanej grupy,

0:02:07.652,0:02:11.809
porównując ją i zamieniając[br]z książką stojącą przed nią,

0:02:11.809,0:02:15.714
aż trafi na właściwe miejsce.

0:02:15.714,0:02:18.213
Ten sposób to sortowanie przez wstawianie.

0:02:18.213,0:02:22.744
W odróżnieniu od sortowania bąbelkowego[br]nie trzeba porównywać każdej pary książek.

0:02:22.744,0:02:26.754
Każdą książkę będzie trzeba[br]porównać średnio

0:02:26.754,0:02:29.464
tylko z połową tych, stojących przed nią.

0:02:29.464,0:02:32.123
W tym przypadku[br]całkowita liczba porównań

0:02:32.123,0:02:35.983
wyniosłaby 409 280,

0:02:35.983,0:02:37.985
co zajęłoby prawie pięć dni.

0:02:37.985,0:02:40.624
To wciąż zbyt wiele porównań.

0:02:40.624,0:02:42.515
Oto lepszy pomysł.

0:02:42.515,0:02:44.885
Najpierw wybierz przypadkową książkę.

0:02:44.885,0:02:49.336
Nazwijmy ją przegrodą[br]i porównajmy z pozostałymi książkami.

0:02:49.336,0:02:51.515
Następnie podzielmy rząd,

0:02:51.515,0:02:55.666
umieszczając wszystkie książki, które mają[br]znaleźć się przed przegrodą po jej lewej,

0:02:55.666,0:02:58.645
a te, które powinny stanąć za nią,[br]po jej prawej stronie.

0:02:58.645,0:03:00.415
Właśnie oszczędziliśmy mnóstwo czasu.

0:03:00.415,0:03:03.845
Już nie będzie trzeba porównywać[br]żadnej z książek po lewej

0:03:03.845,0:03:07.245
do tych po prawej stronie.

0:03:07.245,0:03:09.665
Teraz patrząc tylko na książki[br]po lewej stronie,

0:03:09.665,0:03:12.542
można wybrać przypadkową przegrodę

0:03:12.542,0:03:17.266
i oddzielić książki, mające stać przed,[br]od tych, które powinny stanąć za nią.

0:03:17.266,0:03:19.736
Można dalej tworzyć takie przegrody,

0:03:19.736,0:03:22.384
aż uzyska się wiele małych grup,

0:03:22.384,0:03:27.764
z których każdą posortuje się,[br]używając innej strategii.

0:03:27.764,0:03:32.896
Każde rozdzielenie wymaga[br]około 1280 porównań.

0:03:32.896,0:03:35.466
Jeśli segmenty są w miarę równe,

0:03:35.466,0:03:41.206
podzielenie książek na 128 grup po 10[br]będzie wymagało około siedmiu rund

0:03:41.206,0:03:43.817
albo 8960 sekund.

0:03:43.817,0:03:48.316
Posortowanie każdej grupy[br]zajmie wtedy około 22 sekund.

0:03:48.316,0:03:51.677
Tak czy inaczej ta metoda[br]znana jako sortowanie szybkie

0:03:51.677,0:03:54.423
może posortować książki[br]w mniej niż 3,5 godziny.

0:03:54.423,0:03:55.947
Ale jest haczyk.

0:03:55.947,0:03:59.605
Segmenty mogą okazać się niesymetryczne,[br]co oznacza brak oszczędności czasu.

0:03:59.605,0:04:01.477
Na szczęście rzadko się to zdarza.

0:04:01.477,0:04:04.910
Dlatego sortowanie szybkie[br]to jedna z najbardziej wydajnych strategii

0:04:04.910,0:04:06.916
używanych przez dzisiejszych programistów.

0:04:06.916,0:04:10.847
Korzysta się z niej do sortowania towarów[br]w sklepie internetowym według ceny

0:04:10.847,0:04:14.708
albo tworzenia listy[br]pobliskich stacji benzynowych,

0:04:14.708,0:04:16.379
ułożonych według odległości.

0:04:16.379,0:04:20.227
Właśnie udało się skończyć[br]szybkie sortowanie przed czasem.

0:04:20.227,0:04:22.668
Za tobą kolejny[br]pracowity dzień w bibliotece.