WEBVTT

00:00:06.671 --> 00:00:09.067
Pracujesz w bibliotece uniwersyteckiej.

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

00:00:11.397 --> 00:00:17.741
kiedy nagle przybywa dostawa 1280 książek.

00:00:17.741 --> 00:00:21.510
Książki zostały ułożone
w jednym, długim rzędzie

00:00:21.510 --> 00:00:23.288
w losowej kolejności,

00:00:23.288 --> 00:00:26.881
a automatyczny system
do segregacji jest zepsuty.

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

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

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

00:00:36.107 --> 00:00:39.353
Jak posortować je na czas?

00:00:39.353 --> 00:00:44.779
Jeden ze sposobów to rozpoczęcie 
od pierwszej pary książek z jednego końca.

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

00:00:48.626 --> 00:00:50.840
W przeciwnym razie zamień je miejscami.

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

00:00:53.216 --> 00:00:54.879
powtórz proces

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

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

00:01:01.185 --> 00:01:04.710
Zamieniaj ją z każdą kolejną książką,

00:01:04.710 --> 00:01:09.170
przesuwając wzdłuż rzędu aż na koniec.

00:01:09.170 --> 00:01:12.225
Następnie zacznij od początku
i powtórz cały proces,

00:01:12.225 --> 00:01:15.510
żeby umieścić przedostatnią
książkę na swoim miejscu.

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

00:01:18.821 --> 00:01:21.862
Ten sposób to sortowanie bąbelkowe.

00:01:21.862 --> 00:01:24.156
Jest łatwe, ale powolne.

00:01:24.156 --> 00:01:29.331
W pierwszej rundzie
byłoby 1279 porównań,

00:01:29.331 --> 00:01:33.623
w kolejnej 1278 i tak dalej,

00:01:33.623 --> 00:01:38.542
co w sumie daje 818 560 porównań.

00:01:38.542 --> 00:01:44.273
Gdyby każde zajęło tylko sekundę,
proces potrwałby ponad dziewięć dni.

00:01:44.273 --> 00:01:48.569
Inny sposób rozpoczyna się od ułożenia
tylko dwóch pierwszych książek.

00:01:48.569 --> 00:01:53.613
Następnie weź trzecią książkę i porównaj
do tej stojącej na drugim miejscu.

00:01:53.613 --> 00:01:57.173
Jeśli powinna znaleźć się
przed nią, zamień je.

00:01:57.173 --> 00:01:59.641
Potem porównaj ją do pierwszej książki

00:01:59.641 --> 00:02:01.682
i jeśli trzeba, zamień miejscami.

00:02:01.682 --> 00:02:03.880
Trzy pierwsze książki są już posortowane.

00:02:03.880 --> 00:02:07.652
Dodawaj po jednej nowej książce 
do posortowanej grupy,

00:02:07.652 --> 00:02:11.809
porównując ją i zamieniając
z książką stojącą przed nią,

00:02:11.809 --> 00:02:15.714
aż trafi na właściwe miejsce.

00:02:15.714 --> 00:02:18.213
Ten sposób to sortowanie przez wstawianie.

00:02:18.213 --> 00:02:22.744
W odróżnieniu od sortowania bąbelkowego
nie trzeba porównywać każdej pary książek.

00:02:22.744 --> 00:02:26.754
Każdą książkę będzie trzeba
porównać średnio

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

00:02:29.464 --> 00:02:32.123
W tym przypadku
całkowita liczba porównań

00:02:32.123 --> 00:02:35.983
wyniosłaby 409 280,

00:02:35.983 --> 00:02:37.985
co zajęłoby prawie pięć dni.

00:02:37.985 --> 00:02:40.624
To wciąż zbyt wiele porównań.

00:02:40.624 --> 00:02:42.515
Oto lepszy pomysł.

00:02:42.515 --> 00:02:44.885
Najpierw wybierz przypadkową książkę.

00:02:44.885 --> 00:02:49.336
Nazwijmy ją przegrodą
i porównajmy z pozostałymi książkami.

00:02:49.336 --> 00:02:51.515
Następnie podzielmy rząd,

00:02:51.515 --> 00:02:55.666
umieszczając wszystkie książki, które mają
znaleźć się przed przegrodą po jej lewej,

00:02:55.666 --> 00:02:58.645
a te, które powinny stanąć za nią,
po jej prawej stronie.

00:02:58.645 --> 00:03:00.415
Właśnie oszczędziliśmy mnóstwo czasu.

00:03:00.415 --> 00:03:03.845
Już nie będzie trzeba porównywać
żadnej z książek po lewej

00:03:03.845 --> 00:03:07.245
do tych po prawej stronie.

00:03:07.245 --> 00:03:09.665
Teraz patrząc tylko na książki
po lewej stronie,

00:03:09.665 --> 00:03:12.542
można wybrać przypadkową przegrodę

00:03:12.542 --> 00:03:17.266
i oddzielić książki, mające stać przed,
od tych, które powinny stanąć za nią.

00:03:17.266 --> 00:03:19.736
Można dalej tworzyć takie przegrody,

00:03:19.736 --> 00:03:22.384
aż uzyska się wiele małych grup,

00:03:22.384 --> 00:03:27.764
z których każdą posortuje się,
używając innej strategii.

00:03:27.764 --> 00:03:32.896
Każde rozdzielenie wymaga
około 1280 porównań.

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

00:03:35.466 --> 00:03:41.206
podzielenie książek na 128 grup po 10
będzie wymagało około siedmiu rund

00:03:41.206 --> 00:03:43.817
albo 8960 sekund.

00:03:43.817 --> 00:03:48.316
Posortowanie każdej grupy
zajmie wtedy około 22 sekund.

00:03:48.316 --> 00:03:51.677
Tak czy inaczej ta metoda
znana jako sortowanie szybkie

00:03:51.677 --> 00:03:54.423
może posortować książki
w mniej niż 3,5 godziny.

00:03:54.423 --> 00:03:55.947
Ale jest haczyk.

00:03:55.947 --> 00:03:59.605
Segmenty mogą okazać się niesymetryczne,
co oznacza brak oszczędności czasu.

00:03:59.605 --> 00:04:01.477
Na szczęście rzadko się to zdarza.

00:04:01.477 --> 00:04:04.910
Dlatego sortowanie szybkie
to jedna z najbardziej wydajnych strategii

00:04:04.910 --> 00:04:06.916
używanych przez dzisiejszych programistów.

00:04:06.916 --> 00:04:10.847
Korzysta się z niej do sortowania towarów
w sklepie internetowym według ceny

00:04:10.847 --> 00:04:14.708
albo tworzenia listy
pobliskich stacji benzynowych,

00:04:14.708 --> 00:04:16.379
ułożonych według odległości.

00:04:16.379 --> 00:04:20.227
Właśnie udało się skończyć
szybkie sortowanie przed czasem.

00:04:20.227 --> 00:04:22.668
Za tobą kolejny
pracowity dzień w bibliotece.