1
00:00:06,671 --> 00:00:09,067
Pracujesz w bibliotece uniwersyteckiej.

2
00:00:09,067 --> 00:00:11,397
Jest środek spokojnego popołudnia,

3
00:00:11,397 --> 00:00:17,741
kiedy nagle przybywa dostawa 1280 książek.

4
00:00:17,741 --> 00:00:21,510
Książki zostały ułożone
w jednym, długim rzędzie

5
00:00:21,510 --> 00:00:23,288
w losowej kolejności,

6
00:00:23,288 --> 00:00:26,881
a automatyczny system
do segregacji jest zepsuty.

7
00:00:26,881 --> 00:00:29,597
Co gorsza, jutro zaczynają się zajęcia,

8
00:00:29,597 --> 00:00:32,005
co oznacza, że z samego rana

9
00:00:32,005 --> 00:00:36,107
książek będą szukać tłumy studentów.

10
00:00:36,107 --> 00:00:39,353
Jak posortować je na czas?

11
00:00:39,353 --> 00:00:44,779
Jeden ze sposobów to rozpoczęcie 
od pierwszej pary książek z jednego końca.

12
00:00:44,779 --> 00:00:48,626
Jeśli dwie pierwsze książki
są dobrze ułożone, zostaw je bez zmian.

13
00:00:48,626 --> 00:00:50,840
W przeciwnym razie zamień je miejscami.

14
00:00:50,840 --> 00:00:53,216
Teraz spójrz na drugą i trzecią książkę,

15
00:00:53,216 --> 00:00:54,879
powtórz proces

16
00:00:54,879 --> 00:00:57,755
i kontynuuj, aż dotrzesz do końca linii.

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

18
00:01:01,185 --> 00:01:04,710
Zamieniaj ją z każdą kolejną książką,

19
00:01:04,710 --> 00:01:09,170
przesuwając wzdłuż rzędu aż na koniec.

20
00:01:09,170 --> 00:01:12,225
Następnie zacznij od początku
i powtórz cały proces,

21
00:01:12,225 --> 00:01:15,510
żeby umieścić przedostatnią
książkę na swoim miejscu.

22
00:01:15,510 --> 00:01:18,821
Kontynuuj, aż książki będą posortowane.

23
00:01:18,821 --> 00:01:21,862
Ten sposób to sortowanie bąbelkowe.

24
00:01:21,862 --> 00:01:24,156
Jest łatwe, ale powolne.

25
00:01:24,156 --> 00:01:29,331
W pierwszej rundzie
byłoby 1279 porównań,

26
00:01:29,331 --> 00:01:33,623
w kolejnej 1278 i tak dalej,

27
00:01:33,623 --> 00:01:38,542
co w sumie daje 818 560 porównań.

28
00:01:38,542 --> 00:01:44,273
Gdyby każde zajęło tylko sekundę,
proces potrwałby ponad dziewięć dni.

29
00:01:44,273 --> 00:01:48,569
Inny sposób rozpoczyna się od ułożenia
tylko dwóch pierwszych książek.

30
00:01:48,569 --> 00:01:53,613
Następnie weź trzecią książkę i porównaj
do tej stojącej na drugim miejscu.

31
00:01:53,613 --> 00:01:57,173
Jeśli powinna znaleźć się
przed nią, zamień je.

32
00:01:57,173 --> 00:01:59,641
Potem porównaj ją do pierwszej książki

33
00:01:59,641 --> 00:02:01,682
i jeśli trzeba, zamień miejscami.

34
00:02:01,682 --> 00:02:03,880
Trzy pierwsze książki są już posortowane.

35
00:02:03,880 --> 00:02:07,652
Dodawaj po jednej nowej książce 
do posortowanej grupy,

36
00:02:07,652 --> 00:02:11,809
porównując ją i zamieniając
z książką stojącą przed nią,

37
00:02:11,809 --> 00:02:15,714
aż trafi na właściwe miejsce.

38
00:02:15,714 --> 00:02:18,213
Ten sposób to sortowanie przez wstawianie.

39
00:02:18,213 --> 00:02:22,744
W odróżnieniu od sortowania bąbelkowego
nie trzeba porównywać każdej pary książek.

40
00:02:22,744 --> 00:02:26,754
Każdą książkę będzie trzeba
porównać średnio

41
00:02:26,754 --> 00:02:29,464
tylko z połową tych, stojących przed nią.

42
00:02:29,464 --> 00:02:32,123
W tym przypadku
całkowita liczba porównań

43
00:02:32,123 --> 00:02:35,983
wyniosłaby 409 280,

44
00:02:35,983 --> 00:02:37,985
co zajęłoby prawie pięć dni.

45
00:02:37,985 --> 00:02:40,624
To wciąż zbyt wiele porównań.

46
00:02:40,624 --> 00:02:42,515
Oto lepszy pomysł.

47
00:02:42,515 --> 00:02:44,885
Najpierw wybierz przypadkową książkę.

48
00:02:44,885 --> 00:02:49,336
Nazwijmy ją przegrodą
i porównajmy z pozostałymi książkami.

49
00:02:49,336 --> 00:02:51,515
Następnie podzielmy rząd,

50
00:02:51,515 --> 00:02:55,666
umieszczając wszystkie książki, które mają
znaleźć się przed przegrodą po jej lewej,

51
00:02:55,666 --> 00:02:58,645
a te, które powinny stanąć za nią,
po jej prawej stronie.

52
00:02:58,645 --> 00:03:00,415
Właśnie oszczędziliśmy mnóstwo czasu.

53
00:03:00,415 --> 00:03:03,845
Już nie będzie trzeba porównywać
żadnej z książek po lewej

54
00:03:03,845 --> 00:03:07,245
do tych po prawej stronie.

55
00:03:07,245 --> 00:03:09,665
Teraz patrząc tylko na książki
po lewej stronie,

56
00:03:09,665 --> 00:03:12,542
można wybrać przypadkową przegrodę

57
00:03:12,542 --> 00:03:17,266
i oddzielić książki, mające stać przed,
od tych, które powinny stanąć za nią.

58
00:03:17,266 --> 00:03:19,736
Można dalej tworzyć takie przegrody,

59
00:03:19,736 --> 00:03:22,384
aż uzyska się wiele małych grup,

60
00:03:22,384 --> 00:03:27,764
z których każdą posortuje się,
używając innej strategii.

61
00:03:27,764 --> 00:03:32,896
Każde rozdzielenie wymaga
około 1280 porównań.

62
00:03:32,896 --> 00:03:35,466
Jeśli segmenty są w miarę równe,

63
00:03:35,466 --> 00:03:41,206
podzielenie książek na 128 grup po 10
będzie wymagało około siedmiu rund

64
00:03:41,206 --> 00:03:43,817
albo 8960 sekund.

65
00:03:43,817 --> 00:03:48,316
Posortowanie każdej grupy
zajmie wtedy około 22 sekund.

66
00:03:48,316 --> 00:03:51,677
Tak czy inaczej ta metoda
znana jako sortowanie szybkie

67
00:03:51,677 --> 00:03:54,423
może posortować książki
w mniej niż 3,5 godziny.

68
00:03:54,423 --> 00:03:55,947
Ale jest haczyk.

69
00:03:55,947 --> 00:03:59,605
Segmenty mogą okazać się niesymetryczne,
co oznacza brak oszczędności czasu.

70
00:03:59,605 --> 00:04:01,477
Na szczęście rzadko się to zdarza.

71
00:04:01,477 --> 00:04:04,910
Dlatego sortowanie szybkie
to jedna z najbardziej wydajnych strategii

72
00:04:04,910 --> 00:04:06,916
używanych przez dzisiejszych programistów.

73
00:04:06,916 --> 00:04:10,847
Korzysta się z niej do sortowania towarów
w sklepie internetowym według ceny

74
00:04:10,847 --> 00:04:14,708
albo tworzenia listy
pobliskich stacji benzynowych,

75
00:04:14,708 --> 00:04:16,379
ułożonych według odległości.

76
00:04:16,379 --> 00:04:20,227
Właśnie udało się skończyć
szybkie sortowanie przed czasem.

77
00:04:20,227 --> 00:04:22,668
Za tobą kolejny
pracowity dzień w bibliotece.