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 - Universitatea Harvard]

3
00:00:04,000 --> 00:00:07,000
[Acest lucru este CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Să vorbim despre un fel de îmbinare.

5
00:00:09,000 --> 00:00:14,000
Până acum ați văzut sortare cu bule, sortare inserție, și un fel de selecție.

6
00:00:14,000 --> 00:00:17,000
Deși voi un fel de val mâna mea la ceea ce vreau să spun cu mai bine,

7
00:00:17,000 --> 00:00:21,000
îmbinare de sortare, în general, se comportă mai bine decât oricare dintre aceste 3 tipuri.

8
00:00:22,000 --> 00:00:27,000
>> Dar, înainte de a vorbi despre un fel de îmbinare, hai sa vorbim despre fuzionarea 2 liste sortate.

9
00:00:27,000 --> 00:00:31,000
Vom numi procesul de luare a 2 liste sortate, cum ar fi acestea,

10
00:00:31,000 --> 00:00:35,000
și de a face o singură listă sortată de la ei - comasarea listele.

11
00:00:35,000 --> 00:00:37,750
Cum putem face acest lucru?

12
00:00:37,750 --> 00:00:41,290
Ei bine, o idee este să rămânem doar o listă pe finalul altă listă

13
00:00:41,290 --> 00:00:43,830
și apoi sortați lista de rezultate.

14
00:00:43,830 --> 00:00:47,220
>> În timp ce acest lucru functioneaza, e mult de lucru inutile.

15
00:00:47,220 --> 00:00:49,900
Putem să o facem mai repede decât doar de sortare.

16
00:00:49,900 --> 00:00:54,100
Observați că o idee greșită este de a lua doar cupe alternative din fiecare listă.

17
00:00:54,100 --> 00:00:56,460
Cu toate că poate părea că lucrările la prima,

18
00:00:56,460 --> 00:01:05,760
face acest lucru vom ajunge cu 4, 8, 15, 23, 16 - observați că 16 și 23 sunt din loc.

19
00:01:05,760 --> 00:01:09,380
Acest lucru se datorează faptului că 2 elemente care ar trebui să apară consecutiv în lista de îmbinat

20
00:01:09,380 --> 00:01:11,720
sunt în lista inițială aceeași.

21
00:01:11,720 --> 00:01:14,850
Atât 15 și 16 sunt în lista de pe partea stângă.

22
00:01:14,850 --> 00:01:19,810
Trucul este de a profita de faptul că ambele liste sunt deja sortate.

23
00:01:19,810 --> 00:01:23,320
Acest lucru înseamnă că, dacă ne uităm doar la primele elemente ale ambelor Lista de preturi -

24
00:01:23,320 --> 00:01:29,580
aici, 4 și 8 - una dintre ele trebuie să fie, de asemenea, primul element al listei rezultate din concentrare.

25
00:01:29,580 --> 00:01:31,620
Ei bine, de ce este asta?

26
00:01:31,620 --> 00:01:33,520
Ambele aceste liste sunt deja sortate,

27
00:01:33,520 --> 00:01:38,410
și așa mai departe, fie 4 sau 8 trebuie să fie mai mic element atunci când vom combina cele 2 liste.

28
00:01:38,410 --> 00:01:41,770
În acest caz, cel mai mic este de 4,

29
00:01:41,770 --> 00:01:46,370
astfel încât să putem scoate 4 și face primul element al listei noastre rezultate din concentrare.

30
00:01:46,370 --> 00:01:50,710
Acum vom continua fuziunea restul de 3 elemente ale prima listă

31
00:01:50,710 --> 00:01:52,920
și 4 elemente de doua listă.

32
00:01:52,920 --> 00:01:57,150
>> Încă o dată, avem nevoie doar să se uite la primul element al ambele liste.

33
00:01:57,150 --> 00:02:01,060
Mai mic de 2 trebuie să fie al doilea element al listei noastre rezultate din concentrare.

34
00:02:01,060 --> 00:02:05,440
De data aceasta, între 8 și 15 mai mic este de 8, și astfel vom introduce ca

35
00:02:05,440 --> 00:02:09,240
ca al doilea element al listei noastre sortate.

36
00:02:09,240 --> 00:02:12,180
Putem continua compararea primele elemente ale ambelor liste

37
00:02:12,180 --> 00:02:14,420
și eliminarea mai mic de 2.

38
00:02:14,420 --> 00:02:19,460
Compararea 15 și 23, 15 și este mai mic, astfel încât a noastră de al treilea element.

39
00:02:21,000 --> 00:02:23,910
Compararea acum 16 și 23, 16 este mai mică.

40
00:02:23,910 --> 00:02:26,820
Așa că e al patrulea element.

41
00:02:26,820 --> 00:02:30,390
>> Observați că 2 elemente venit de la aceeași listă într-un rând.

42
00:02:30,390 --> 00:02:34,400
Acesta este motivul pentru lista rezultată în urma concentrării nu poate doar elemente de supleanți din cele 2 liste.

43
00:02:34,400 --> 00:02:40,020
Compararea 50 și 23, 23 este mai mic, asa ca am ales asta.

44
00:02:40,770 --> 00:02:44,070
Între 50 și 42, 42 este mai mică.

45
00:02:44,070 --> 00:02:48,290
Între 50 și 108, 50 este mai mică.

46
00:02:48,290 --> 00:02:52,330
Și, în sfârșit, avem doar 108, așa că trebuie să meargă la sfarsitul listei noastre.

47
00:02:53,750 --> 00:02:56,180
Observați că avem o listă frumos, sortate.

48
00:02:56,180 --> 00:02:59,040
De fiecare dată când am comparat primele 2 elemente ale celor 2 liste

49
00:02:59,040 --> 00:03:02,730
noi am fost capabil de a determina urmatorul element al listei rezultate din concentrare.

50
00:03:02,730 --> 00:03:08,070
Acest lucru înseamnă că, în cazul în lista finală conține numere n, unde n este aici 8,

51
00:03:08,070 --> 00:03:12,610
atunci avem nevoie de cele mai multe comparații la n pentru a obține toate aceste numere în locul potrivit.

52
00:03:13,230 --> 00:03:16,230
O astfel de algoritm se spune pentru a rula în timp liniar,

53
00:03:16,230 --> 00:03:18,090
dar nu vă faceți griji despre asta aici.

54
00:03:18,570 --> 00:03:22,810
>> Folosind algoritmul nostru pentru fuzionarea, putem face un algoritm rapid de îmbinare de sortare.

55
00:03:22,810 --> 00:03:25,170
Deci, hai să resetați listele noastre.

56
00:03:35,210 --> 00:03:37,750
Există 2 pași mari în procesul de sortare de îmbinare.

57
00:03:37,750 --> 00:03:41,500
În primul rând, divizat continuu lista de cupe în jumatati

58
00:03:41,500 --> 00:03:44,860
până când vom avea o grămadă de liste cu doar 1 ceașcă în ele.

59
00:03:44,860 --> 00:03:47,350
Nu vă faceți griji în cazul în care o listă conține un număr impar

60
00:03:47,350 --> 00:03:49,880
si nu poti face o tăietură perfect curată între ele.

61
00:03:49,880 --> 00:03:53,750
Doar alege arbitrar, care să includă lista cupa suplimentar inch

62
00:03:53,750 --> 00:03:56,240
Deci, hai sa împărțit aceste liste.

63
00:03:58,140 --> 00:04:01,310
Acum avem 2 liste.

64
00:04:04,120 --> 00:04:06,570
Acum avem 4 liste.

65
00:04:10,350 --> 00:04:13,870
>> Și acum avem 8 Lista de preturi cu o singură ceașcă în fiecare listă.

66
00:04:13,870 --> 00:04:16,630
Deci asta e tot pentru pasul 1.

67
00:04:16,630 --> 00:04:22,230
Pentru pasul 2, ne uni în mod repetat perechi de liste utilizând algoritmul de îmbinare am învățat înainte.

68
00:04:22,230 --> 00:04:29,160
Fuzionarea 108 și 15, vom ajunge cu lista de 15, 108.

69
00:04:30,330 --> 00:04:36,250
Fuzionarea 50 și 4, vom ajunge cu 4, 50.

70
00:04:36,960 --> 00:04:41,400
Fuzionarea 8 și 42, vom ajunge cu 8, 42.

71
00:04:42,790 --> 00:04:48,130
Și fuzionează 23 și 16, vom ajunge cu 16, 23.

72
00:04:49,740 --> 00:04:52,450
Acum, toate listele noastre sunt de dimensiuni 2.

73
00:04:53,020 --> 00:04:56,180
Observați că fiecare dintre cele 4 liste este sortat.

74
00:04:56,180 --> 00:04:59,160
>> Astfel încât să putem începe fuzionarea perechi de liste din nou.

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

76
00:05:03,240 --> 00:05:11,170
ia primul 4, apoi 15, apoi 50, apoi 108.

77
00:05:11,170 --> 00:05:15,120
Fuzionarea 8, 42 și 16, 23,

78
00:05:15,120 --> 00:05:22,440
vom lua prima 8, apoi 16, apoi 23, apoi 42.

79
00:05:22,440 --> 00:05:27,370
Deci, acum avem doar 2 liste de marimea 4, fiecare dintre care este sortat.

80
00:05:27,370 --> 00:05:30,980
Deci, acum am îmbina aceste două liste.

81
00:05:30,980 --> 00:05:33,440
În primul rând vom lua 4.

82
00:05:33,440 --> 00:05:36,580
Apoi luăm 8.

83
00:05:36,580 --> 00:05:50,700
Apoi luăm 15 și 16, apoi 23, apoi 42, apoi 50, apoi 108.

84
00:05:50,700 --> 00:05:52,220
Și am terminat.

85
00:05:52,220 --> 00:05:54,900
Avem acum o listă sortată.

86
00:05:54,900 --> 00:05:57,890
Deci, cât de repede a fost asta, mai exact?

87
00:05:57,890 --> 00:06:02,000
În termeni tehnici, sortare îmbinare este O (n log n),

88
00:06:02,000 --> 00:06:07,380
întrucât toate de sortare cu bule, sortare inserție, și un fel de selecție sunt O (n ²).

89
00:06:07,380 --> 00:06:11,120
De fapt, după cum veți afla în curând, nu va fi capabil de a veni cu un fel de

90
00:06:11,120 --> 00:06:14,820
care se comporta mai bine decat O (n log n) în cazul general.

91
00:06:14,820 --> 00:06:19,120
Din nou, nu vă faceți griji cu privire la această notație Big O, dacă nu l-ați văzut încă.

92
00:06:19,120 --> 00:06:23,490
>> Doar știu că acest lucru înseamnă, dacă ne-am dorit pentru a sorta o listă foarte mare

93
00:06:23,490 --> 00:06:26,820
sortare sortare cu bule, sortare inserție, și de selecție ar putea avea potential

94
00:06:26,820 --> 00:06:29,500
semnificativ mai mare decât îmbinare de sortare.

95
00:06:29,500 --> 00:06:33,210
Aceasta nu înseamnă că un fel de îmbinare va fi mai rapidă pentru toate listele de

96
00:06:33,210 --> 00:06:36,220
sau chiar pentru orice listă unică sub un anumită dimensiune.

97
00:06:36,220 --> 00:06:41,950
De exemplu, ar putea fi un fel inserție mai rapidă de sortare pentru toate listele de mai mici decat 5 elemente.

98
00:06:41,950 --> 00:06:47,360
În practică, un fel de îmbinare este de obicei mai rapid pentru Lista de preturi la fel de mici ca 50 de elemente.

99
00:06:47,360 --> 00:06:51,120
>> Dar aceasta viteza in plus nu vine fără un preț.

100
00:06:51,120 --> 00:06:54,770
Spre deosebire de felul de alte noastre, care să ia o listă și să modifice lista de la locul de

101
00:06:54,770 --> 00:06:58,740
până când vom obține o listă sortată, sortare îmbinare are nevoie de unele spațiu suplimentar

102
00:06:58,740 --> 00:07:00,900
să fuzioneze 2 liste împreună.

103
00:07:00,900 --> 00:07:04,690
Noi nu putem folosi imediat listele care sunt îmbinate pentru a stoca lista rezultată în urma concentrării

104
00:07:04,690 --> 00:07:08,880
din moment ce s-ar putea înlocui elementele care încă trebuie să fie îmbinate.

105
00:07:08,880 --> 00:07:13,540
Acest spațiu este un pic de un preț, dar, de obicei, nu este nerezonabil.

106
00:07:13,540 --> 00:07:15,330
Și asta e tot un fel de îmbinare.

107
00:07:15,330 --> 00:07:18,490
>> Numele meu este Rob Bowden, iar acest lucru este CS50.

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

109
00:07:20,500 --> 00:07:24,000
- Sortare și selecție.

110
00:07:24,000 --> 00:07:25,880
[Râde]

111
00:07:25,880 --> 00:07:31,480
Oh, trebuie să iau asta prea pentru că am schimbat modul în care am fost o prezenta.

112
00:07:31,480 --> 00:07:35,680
Lista din partea stângă. Asta a fost o greseala de tipar.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] Am dat-on bară -

114
00:07:39,290 --> 00:07:41,190
[Râde]

115
00:07:41,190 --> 00:07:44,190
Nu știu ce -