[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:06.67,0:00:09.07,Default,,0000,0000,0000,,Pracujesz w bibliotece uniwersyteckiej.
Dialogue: 0,0:00:09.07,0:00:11.40,Default,,0000,0000,0000,,Jest środek spokojnego popołudnia,
Dialogue: 0,0:00:11.40,0:00:17.74,Default,,0000,0000,0000,,kiedy nagle przybywa dostawa 1280 książek.
Dialogue: 0,0:00:17.74,0:00:21.51,Default,,0000,0000,0000,,Książki zostały ułożone\Nw jednym, długim rzędzie
Dialogue: 0,0:00:21.51,0:00:23.29,Default,,0000,0000,0000,,w losowej kolejności,
Dialogue: 0,0:00:23.29,0:00:26.88,Default,,0000,0000,0000,,a automatyczny system\Ndo segregacji jest zepsuty.
Dialogue: 0,0:00:26.88,0:00:29.60,Default,,0000,0000,0000,,Co gorsza, jutro zaczynają się zajęcia,
Dialogue: 0,0:00:29.60,0:00:32.00,Default,,0000,0000,0000,,co oznacza, że z samego rana
Dialogue: 0,0:00:32.00,0:00:36.11,Default,,0000,0000,0000,,książek będą szukać tłumy studentów.
Dialogue: 0,0:00:36.11,0:00:39.35,Default,,0000,0000,0000,,Jak posortować je na czas?
Dialogue: 0,0:00:39.35,0:00:44.78,Default,,0000,0000,0000,,Jeden ze sposobów to rozpoczęcie \Nod pierwszej pary książek z jednego końca.
Dialogue: 0,0:00:44.78,0:00:48.63,Default,,0000,0000,0000,,Jeśli dwie pierwsze książki\Nsą dobrze ułożone, zostaw je bez zmian.
Dialogue: 0,0:00:48.63,0:00:50.84,Default,,0000,0000,0000,,W przeciwnym razie zamień je miejscami.
Dialogue: 0,0:00:50.84,0:00:53.22,Default,,0000,0000,0000,,Teraz spójrz na drugą i trzecią książkę,
Dialogue: 0,0:00:53.22,0:00:54.88,Default,,0000,0000,0000,,powtórz proces
Dialogue: 0,0:00:54.88,0:00:57.76,Default,,0000,0000,0000,,i kontynuuj, aż dotrzesz do końca linii.
Dialogue: 0,0:00:57.76,0:01:01.18,Default,,0000,0000,0000,,W końcu natkniesz się na książkę,\Nktóra powinna być ostatnia.
Dialogue: 0,0:01:01.18,0:01:04.71,Default,,0000,0000,0000,,Zamieniaj ją z każdą kolejną książką,
Dialogue: 0,0:01:04.71,0:01:09.17,Default,,0000,0000,0000,,przesuwając wzdłuż rzędu aż na koniec.
Dialogue: 0,0:01:09.17,0:01:12.22,Default,,0000,0000,0000,,Następnie zacznij od początku\Ni powtórz cały proces,
Dialogue: 0,0:01:12.22,0:01:15.51,Default,,0000,0000,0000,,żeby umieścić przedostatnią\Nksiążkę na swoim miejscu.
Dialogue: 0,0:01:15.51,0:01:18.82,Default,,0000,0000,0000,,Kontynuuj, aż książki będą posortowane.
Dialogue: 0,0:01:18.82,0:01:21.86,Default,,0000,0000,0000,,Ten sposób to sortowanie bąbelkowe.
Dialogue: 0,0:01:21.86,0:01:24.16,Default,,0000,0000,0000,,Jest łatwe, ale powolne.
Dialogue: 0,0:01:24.16,0:01:29.33,Default,,0000,0000,0000,,W pierwszej rundzie\Nbyłoby 1279 porównań,
Dialogue: 0,0:01:29.33,0:01:33.62,Default,,0000,0000,0000,,w kolejnej 1278 i tak dalej,
Dialogue: 0,0:01:33.62,0:01:38.54,Default,,0000,0000,0000,,co w sumie daje 818 560 porównań.
Dialogue: 0,0:01:38.54,0:01:44.27,Default,,0000,0000,0000,,Gdyby każde zajęło tylko sekundę,\Nproces potrwałby ponad dziewięć dni.
Dialogue: 0,0:01:44.27,0:01:48.57,Default,,0000,0000,0000,,Inny sposób rozpoczyna się od ułożenia\Ntylko dwóch pierwszych książek.
Dialogue: 0,0:01:48.57,0:01:53.61,Default,,0000,0000,0000,,Następnie weź trzecią książkę i porównaj\Ndo tej stojącej na drugim miejscu.
Dialogue: 0,0:01:53.61,0:01:57.17,Default,,0000,0000,0000,,Jeśli powinna znaleźć się\Nprzed nią, zamień je.
Dialogue: 0,0:01:57.17,0:01:59.64,Default,,0000,0000,0000,,Potem porównaj ją do pierwszej książki
Dialogue: 0,0:01:59.64,0:02:01.68,Default,,0000,0000,0000,,i jeśli trzeba, zamień miejscami.
Dialogue: 0,0:02:01.68,0:02:03.88,Default,,0000,0000,0000,,Trzy pierwsze książki są już posortowane.
Dialogue: 0,0:02:03.88,0:02:07.65,Default,,0000,0000,0000,,Dodawaj po jednej nowej książce \Ndo posortowanej grupy,
Dialogue: 0,0:02:07.65,0:02:11.81,Default,,0000,0000,0000,,porównując ją i zamieniając\Nz książką stojącą przed nią,
Dialogue: 0,0:02:11.81,0:02:15.71,Default,,0000,0000,0000,,aż trafi na właściwe miejsce.
Dialogue: 0,0:02:15.71,0:02:18.21,Default,,0000,0000,0000,,Ten sposób to sortowanie przez wstawianie.
Dialogue: 0,0:02:18.21,0:02:22.74,Default,,0000,0000,0000,,W odróżnieniu od sortowania bąbelkowego\Nnie trzeba porównywać każdej pary książek.
Dialogue: 0,0:02:22.74,0:02:26.75,Default,,0000,0000,0000,,Każdą książkę będzie trzeba\Nporównać średnio
Dialogue: 0,0:02:26.75,0:02:29.46,Default,,0000,0000,0000,,tylko z połową tych, stojących przed nią.
Dialogue: 0,0:02:29.46,0:02:32.12,Default,,0000,0000,0000,,W tym przypadku\Ncałkowita liczba porównań
Dialogue: 0,0:02:32.12,0:02:35.98,Default,,0000,0000,0000,,wyniosłaby 409 280,
Dialogue: 0,0:02:35.98,0:02:37.98,Default,,0000,0000,0000,,co zajęłoby prawie pięć dni.
Dialogue: 0,0:02:37.98,0:02:40.62,Default,,0000,0000,0000,,To wciąż zbyt wiele porównań.
Dialogue: 0,0:02:40.62,0:02:42.52,Default,,0000,0000,0000,,Oto lepszy pomysł.
Dialogue: 0,0:02:42.52,0:02:44.88,Default,,0000,0000,0000,,Najpierw wybierz przypadkową książkę.
Dialogue: 0,0:02:44.88,0:02:49.34,Default,,0000,0000,0000,,Nazwijmy ją przegrodą\Ni porównajmy z pozostałymi książkami.
Dialogue: 0,0:02:49.34,0:02:51.52,Default,,0000,0000,0000,,Następnie podzielmy rząd,
Dialogue: 0,0:02:51.52,0:02:55.67,Default,,0000,0000,0000,,umieszczając wszystkie książki, które mają\Nznaleźć się przed przegrodą po jej lewej,
Dialogue: 0,0:02:55.67,0:02:58.64,Default,,0000,0000,0000,,a te, które powinny stanąć za nią,\Npo jej prawej stronie.
Dialogue: 0,0:02:58.64,0:03:00.42,Default,,0000,0000,0000,,Właśnie oszczędziliśmy mnóstwo czasu.
Dialogue: 0,0:03:00.42,0:03:03.84,Default,,0000,0000,0000,,Już nie będzie trzeba porównywać\Nżadnej z książek po lewej
Dialogue: 0,0:03:03.84,0:03:07.24,Default,,0000,0000,0000,,do tych po prawej stronie.
Dialogue: 0,0:03:07.24,0:03:09.66,Default,,0000,0000,0000,,Teraz patrząc tylko na książki\Npo lewej stronie,
Dialogue: 0,0:03:09.66,0:03:12.54,Default,,0000,0000,0000,,można wybrać przypadkową przegrodę
Dialogue: 0,0:03:12.54,0:03:17.27,Default,,0000,0000,0000,,i oddzielić książki, mające stać przed,\Nod tych, które powinny stanąć za nią.
Dialogue: 0,0:03:17.27,0:03:19.74,Default,,0000,0000,0000,,Można dalej tworzyć takie przegrody,
Dialogue: 0,0:03:19.74,0:03:22.38,Default,,0000,0000,0000,,aż uzyska się wiele małych grup,
Dialogue: 0,0:03:22.38,0:03:27.76,Default,,0000,0000,0000,,z których każdą posortuje się,\Nużywając innej strategii.
Dialogue: 0,0:03:27.76,0:03:32.90,Default,,0000,0000,0000,,Każde rozdzielenie wymaga\Nokoło 1280 porównań.
Dialogue: 0,0:03:32.90,0:03:35.47,Default,,0000,0000,0000,,Jeśli segmenty są w miarę równe,
Dialogue: 0,0:03:35.47,0:03:41.21,Default,,0000,0000,0000,,podzielenie książek na 128 grup po 10\Nbędzie wymagało około siedmiu rund
Dialogue: 0,0:03:41.21,0:03:43.82,Default,,0000,0000,0000,,albo 8960 sekund.
Dialogue: 0,0:03:43.82,0:03:48.32,Default,,0000,0000,0000,,Posortowanie każdej grupy\Nzajmie wtedy około 22 sekund.
Dialogue: 0,0:03:48.32,0:03:51.68,Default,,0000,0000,0000,,Tak czy inaczej ta metoda\Nznana jako sortowanie szybkie
Dialogue: 0,0:03:51.68,0:03:54.42,Default,,0000,0000,0000,,może posortować książki\Nw mniej niż 3,5 godziny.
Dialogue: 0,0:03:54.42,0:03:55.95,Default,,0000,0000,0000,,Ale jest haczyk.
Dialogue: 0,0:03:55.95,0:03:59.60,Default,,0000,0000,0000,,Segmenty mogą okazać się niesymetryczne,\Nco oznacza brak oszczędności czasu.
Dialogue: 0,0:03:59.60,0:04:01.48,Default,,0000,0000,0000,,Na szczęście rzadko się to zdarza.
Dialogue: 0,0:04:01.48,0:04:04.91,Default,,0000,0000,0000,,Dlatego sortowanie szybkie\Nto jedna z najbardziej wydajnych strategii
Dialogue: 0,0:04:04.91,0:04:06.92,Default,,0000,0000,0000,,używanych przez dzisiejszych programistów.
Dialogue: 0,0:04:06.92,0:04:10.85,Default,,0000,0000,0000,,Korzysta się z niej do sortowania towarów\Nw sklepie internetowym według ceny
Dialogue: 0,0:04:10.85,0:04:14.71,Default,,0000,0000,0000,,albo tworzenia listy\Npobliskich stacji benzynowych,
Dialogue: 0,0:04:14.71,0:04:16.38,Default,,0000,0000,0000,,ułożonych według odległości.
Dialogue: 0,0:04:16.38,0:04:20.23,Default,,0000,0000,0000,,Właśnie udało się skończyć\Nszybkie sortowanie przed czasem.
Dialogue: 0,0:04:20.23,0:04:22.67,Default,,0000,0000,0000,,Za tobą kolejny\Npracowity dzień w bibliotece.