1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Merge Sort]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Harvard University]

3
00:00:04,000 --> 00:00:07,000
[To jest CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Porozmawiajmy o sortowanie korespondencji seryjnej.

5
00:00:09,000 --> 00:00:14,000
Dotychczas widzieliśmy sortowania bąbelkowego, sortowanie wstawiania i sortować wyboru.

6
00:00:14,000 --> 00:00:17,000
Chociaż ja w rodzaj fali moją rękę na to, co mam na myśli, lepiej,

7
00:00:17,000 --> 00:00:21,000
scalić sort ogólnie działa lepiej niż którykolwiek z tych 3 rodzajów.

8
00:00:22,000 --> 00:00:27,000
>> Ale zanim mówić o rodzaju łączenia, pomówmy o łączenie 2 sortowanie listy.

9
00:00:27,000 --> 00:00:31,000
Zadzwonimy proces podejmowania 2 sortowanie listy, jak te,

10
00:00:31,000 --> 00:00:35,000
i co jeden posortowanej listy z nich - łączenie list.

11
00:00:35,000 --> 00:00:37,750
W jaki sposób możemy to zrobić?

12
00:00:37,750 --> 00:00:41,290
Cóż, jeden pomysł jest po prostu trzymać jedną listę na końcu drugiej listy

13
00:00:41,290 --> 00:00:43,830
a następnie posortować listę wynikową.

14
00:00:43,830 --> 00:00:47,220
>> Mimo to działa, to jest dużo niepotrzebnej pracy.

15
00:00:47,220 --> 00:00:49,900
Możemy to zrobić szybciej, niż tylko sortowanie.

16
00:00:49,900 --> 00:00:54,100
Zauważ, że jeden zły pomysł jest po prostu wziąć filiżanek przemian z każdej listy.

17
00:00:54,100 --> 00:00:56,460
Mimo, że może wydawać się, że prace w pierwszym,

18
00:00:56,460 --> 00:01:05,760
robi, że skończymy z 4, 8, 15, 23, 16 - zauważ, że 16 i 23 są nie na miejscu.

19
00:01:05,760 --> 00:01:09,380
To dlatego, że 2 elementy, które powinny pojawić kolejny w połączonej listy

20
00:01:09,380 --> 00:01:11,720
w tej samej pierwszej listy.

21
00:01:11,720 --> 00:01:14,850
15 i 16, zarówno w liście są po lewej stronie.

22
00:01:14,850 --> 00:01:19,810
Sztuką jest, aby skorzystać z faktu, że obie listy są już posortowane.

23
00:01:19,810 --> 00:01:23,320
Oznacza to, że jeśli tylko patrzeć pierwszych elementów obu listach -

24
00:01:23,320 --> 00:01:29,580
o, 4 i 8 - jeden z nich musi być pierwszym elementem połączonego listy.

25
00:01:29,580 --> 00:01:31,620
Cóż, to dlaczego?

26
00:01:31,620 --> 00:01:33,520
Obydwa z tych list już posortowane,

27
00:01:33,520 --> 00:01:38,410
i tak 4 lub 8 może być najmniejszy element, kiedy łączymy 2 list.

28
00:01:38,410 --> 00:01:41,770
W tym przypadku, jest najmniejsza 4

29
00:01:41,770 --> 00:01:46,370
więc możemy wziąć 4 i sprawiają, że pierwszy element naszej połączonej listy.

30
00:01:46,370 --> 00:01:50,710
Teraz możemy kontynuować łączenie pozostałe 3 elementy pierwszej listy

31
00:01:50,710 --> 00:01:52,920
i 4 elementy drugiej listy.

32
00:01:52,920 --> 00:01:57,150
>> Po raz kolejny, tylko trzeba spojrzeć na pierwszy element obu listach.

33
00:01:57,150 --> 00:02:01,060
Mniejsza z 2 musi być drugi element naszej połączonej listy.

34
00:02:01,060 --> 00:02:05,440
Tym razem, od 8 do 15 jest najmniejsza 8, a więc, że wprowadzić

35
00:02:05,440 --> 00:02:09,240
jako drugi element naszego sortowanej listy.

36
00:02:09,240 --> 00:02:12,180
Możemy kontynuować porównywanie pierwszych elementów obu list

37
00:02:12,180 --> 00:02:14,420
i usunięcie z 2 mniejsze.

38
00:02:14,420 --> 00:02:19,460
Porównując 15 i 23, 15 jest mniejsza, i tak, że to nasz trzeci element.

39
00:02:21,000 --> 00:02:23,910
Teraz porównanie 16 i 23, 16 jest mniejszy.

40
00:02:23,910 --> 00:02:26,820
Więc to czwarty element.

41
00:02:26,820 --> 00:02:30,390
>> Zauważ, że 2 elementy pochodziły z tej samej listy w wierszu.

42
00:02:30,390 --> 00:02:34,400
Dlatego lista powstała w wyniku połączenia nie można po prostu alternatywne elementy z 2 list.

43
00:02:34,400 --> 00:02:40,020
Porównując 50 i 23, 23 jest mniejszy, więc wybraliśmy to.

44
00:02:40,770 --> 00:02:44,070
Pomiędzy 50 i 42, 42 jest mniejszy.

45
00:02:44,070 --> 00:02:48,290
Pomiędzy 50 i 108, 50 jest mniejszy.

46
00:02:48,290 --> 00:02:52,330
I wreszcie, musimy tylko 108, więc musi iść na końcu naszej listy.

47
00:02:53,750 --> 00:02:56,180
Zauważ, że mamy ładne, posortowaną listę.

48
00:02:56,180 --> 00:02:59,040
Za każdym razem, w porównaniu pierwsze 2 elementy 2 list

49
00:02:59,040 --> 00:03:02,730
udało się ustalić, kolejnym elementem połączonego listy.

50
00:03:02,730 --> 00:03:08,070
Oznacza to, że jeżeli ostateczna lista zawiera n liczb, gdzie n tutaj jest 8,

51
00:03:08,070 --> 00:03:12,610
to musimy co najwyżej n porównań, aby wszystkie te numery w odpowiednim miejscu.

52
00:03:13,230 --> 00:03:16,230
Taki algorytm jest powiedziane, aby uruchomić w czasie liniowym,

53
00:03:16,230 --> 00:03:18,090
ale nie martw się o tym tutaj.

54
00:03:18,570 --> 00:03:22,810
>> Korzystanie z naszego algorytmu scalania, możemy szybki algorytm sortowania korespondencji seryjnej.

55
00:03:22,810 --> 00:03:25,170
No to zresetować nasze listy.

56
00:03:35,210 --> 00:03:37,750
Istnieją 2 duże kroki w procesie sortowania korespondencji seryjnej.

57
00:03:37,750 --> 00:03:41,500
Po pierwsze, stale podzielić listę na pół filiżanki

58
00:03:41,500 --> 00:03:44,860
dopóki mamy kilka list z tylko 1 filiżankę w nich.

59
00:03:44,860 --> 00:03:47,350
Nie martw się, jeśli lista zawiera nieparzystą liczbę

60
00:03:47,350 --> 00:03:49,880
i nie można zrobić idealnie czyste cięcie między nimi.

61
00:03:49,880 --> 00:03:53,750
Wystarczy dowolnie wybrać, które lista zawierać dodatkową filiżankę w.

62
00:03:53,750 --> 00:03:56,240
No to podzielić tych list.

63
00:03:58,140 --> 00:04:01,310
Teraz mamy 2 list.

64
00:04:04,120 --> 00:04:06,570
Teraz mamy 4 list.

65
00:04:10,350 --> 00:04:13,870
>> A teraz mamy 8 list z jednego kubka w każdym liście.

66
00:04:13,870 --> 00:04:16,630
Więc to jest to dla kroku 1.

67
00:04:16,630 --> 00:04:22,230
Dla kroku 2, to wielokrotnie łączy pary list algorytmem scalania dowiedzieliśmy wcześniej.

68
00:04:22,230 --> 00:04:29,160
Połączenie 108 i 15, ale kończy się z listy 15, 108.

69
00:04:30,330 --> 00:04:36,250
Scalanie 50 i 4, ale kończy się z 4, 50.

70
00:04:36,960 --> 00:04:41,400
Połączenie 8 i 42, ale kończy się z 8, 42.

71
00:04:42,790 --> 00:04:48,130
I połączenie 23 i 16, ale kończy się z 16, 23.

72
00:04:49,740 --> 00:04:52,450
Teraz wszystkie nasze listy są wielkości 2.

73
00:04:53,020 --> 00:04:56,180
Zauważ, że każdy z 4 listy są sortowane.

74
00:04:56,180 --> 00:04:59,160
>> Więc możemy zacząć łączenie par list ponownie.

75
00:04:59,160 --> 00:05:03,240
Scalanie 15 i 108 oraz 4 i 50 -

76
00:05:03,240 --> 00:05:11,170
najpierw wziąć do 4, a następnie 15, a następnie 50, a następnie 108.

77
00:05:11,170 --> 00:05:15,120
Połączenie 8, 42 i 16, 23,

78
00:05:15,120 --> 00:05:22,440
najpierw się 8, a następnie 16, a następnie 23, a następnie 42.

79
00:05:22,440 --> 00:05:27,370
Więc teraz mamy tylko 2 listy rozmiar 4, z których każdy jest posortowane.

80
00:05:27,370 --> 00:05:30,980
Więc teraz połączyć te 2 list.

81
00:05:30,980 --> 00:05:33,440
Najpierw bierzemy 4.

82
00:05:33,440 --> 00:05:36,580
Następnie bierzemy 8.

83
00:05:36,580 --> 00:05:50,700
Następnie bierzemy 15 i 16, potem 23, potem 42, potem 50, potem 108.

84
00:05:50,700 --> 00:05:52,220
I gotowe.

85
00:05:52,220 --> 00:05:54,900
Mamy teraz posortowana lista.

86
00:05:54,900 --> 00:05:57,890
Tak jak szybko to było dokładnie?

87
00:05:57,890 --> 00:06:02,000
Z technicznego punktu widzenia, sort merge jest O (n log n),

88
00:06:02,000 --> 00:06:07,380
natomiast wszystkie sortowanie bąbelkowe, sortowanie wstawiania, i rodzaju selekcji O (n ²).

89
00:06:07,380 --> 00:06:11,120
W rzeczywistości, jak można dowiedzieć się wkrótce, że nie będzie w stanie wymyślić coś w rodzaju

90
00:06:11,120 --> 00:06:14,820
że działa lepiej niż O (n log n) w przypadku ogólnym.

91
00:06:14,820 --> 00:06:19,120
Ponownie, nie martw się o tym wielkim notacji O, jeśli nie widziałeś jeszcze.

92
00:06:19,120 --> 00:06:23,490
>> Po prostu wiem, że to oznacza, że ​​jeśli chcemy, aby posortować listę naprawdę duży

93
00:06:23,490 --> 00:06:26,820
sort sortowanie bąbelkowe, sortowanie wstawiania i wybór może potencjalnie wziąć

94
00:06:26,820 --> 00:06:29,500
znacznie dłużej niż seryjnej sortowania.

95
00:06:29,500 --> 00:06:33,210
To nie znaczy, że sort merge będzie szybciej dla wszystkich list

96
00:06:33,210 --> 00:06:36,220
lub nawet dla pojedynczej listy w określonej wielkości.

97
00:06:36,220 --> 00:06:41,950
Na przykład, może być swego rodzaju wprowadzenie najszybciej sortowania wszystkich list mniejszych niż 5 elementów.

98
00:06:41,950 --> 00:06:47,360
W praktyce, sort merge jest zazwyczaj szybsza dla list tak małych jak 50 elementów.

99
00:06:47,360 --> 00:06:51,120
>> Ale ta dodatkowa prędkość nie przychodzi bez ceny.

100
00:06:51,120 --> 00:06:54,770
W przeciwieństwie do naszych innych rodzajów, które mają listę i zmodyfikować listę w lokalu

101
00:06:54,770 --> 00:06:58,740
aż dojdziemy posortowaną listę, sort merge potrzebuje dodatkowego miejsca

102
00:06:58,740 --> 00:07:00,900
scalić 2 list razem.

103
00:07:00,900 --> 00:07:04,690
Nie możemy od razu korzystać z list, które są scalane do przechowywania scaloną listę

104
00:07:04,690 --> 00:07:08,880
gdyż moglibyśmy zastąpić elementy, które wciąż muszą zostać połączone.

105
00:07:08,880 --> 00:07:13,540
Ta przestrzeń jest trochę cena, ale to zazwyczaj nie jest bezzasadne.

106
00:07:13,540 --> 00:07:15,330
I to na sortowanie korespondencji seryjnej.

107
00:07:15,330 --> 00:07:18,490
>> Nazywam się Rob Bowden, a to CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- I wybór rodzaju.

110
00:07:24,000 --> 00:07:25,880
[Śmieje się]

111
00:07:25,880 --> 00:07:31,480
Och, muszę wziąć to zbyt bo przeszedłem jak byłem przedstawianie go.

112
00:07:31,480 --> 00:07:35,680
Lista po lewej stronie. To była literówka.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] spieprzyłem -

114
00:07:39,290 --> 00:07:41,190
[Śmieje się]

115
00:07:41,190 --> 00:07:44,190
Nie wiem, co -