1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Pagsamahin ang uri-uriin]

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

3
00:00:04,000 --> 00:00:07,000
[Ito ay CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Natin makipag-usap tungkol sa pagsasama-uuri.

5
00:00:09,000 --> 00:00:14,000
Sa ngayon nakita mo ang bubble-uri-uriin, pagpapasok ng uri, at pagpili-uuri.

6
00:00:14,000 --> 00:00:17,000
Kahit na bibigyan ko uri ng wave ang aking kamay sa kung ano ang ibig sabihin ko sa pamamagitan ng mas mahusay na,

7
00:00:17,000 --> 00:00:21,000
sumanib-uuri sa pangkalahatan ay mas mahusay na gumaganap kaysa sa anumang ng mga 3 uri.

8
00:00:22,000 --> 00:00:27,000
>> Ngunit bago ang pakikipag-usap tungkol sa pagsasama-uuri, sabihin makipag-usap tungkol sa pinagsasama ng 2 pinagsunod-sunod listahan.

9
00:00:27,000 --> 00:00:31,000
Susubukan naming tawagan ang proseso ng pagkuha ng 2 pinagsunod-sunod listahan, tulad ng mga ito,

10
00:00:31,000 --> 00:00:35,000
at gumagawa ng isang pinagsunod-sunod na listahan sa kanila - pinagsasama ang mga listahan.

11
00:00:35,000 --> 00:00:37,750
Paano namin gawin ito?

12
00:00:37,750 --> 00:00:41,290
Well, isang ideya lang dumikit ang isang listahan papunta sa dulo ng iba pang listahan

13
00:00:41,290 --> 00:00:43,830
at pagkatapos ay ayusin ang listahan na nagreresulta.

14
00:00:43,830 --> 00:00:47,220
>> Habang ito gumagana, ng maraming ng hindi kinakailangang trabaho.

15
00:00:47,220 --> 00:00:49,900
Maaari naming gawin ito mas mabilis pa sa pag-uuri-uri.

16
00:00:49,900 --> 00:00:54,100
Pansinin na ang isang maling ideya ay lamang tumagal ng alternating tasa mula sa bawat listahan.

17
00:00:54,100 --> 00:00:56,460
Habang na maaaring tila na gumagana sa unang,

18
00:00:56,460 --> 00:01:05,760
ginagawa na namin magtapos sa 4, 8, 15, 23, 16 - paunawa na 16 at 23 ay wala sa lugar.

19
00:01:05,760 --> 00:01:09,380
Ito ay dahil ang 2 elemento na dapat lumitaw magkakasunod sa merged na listahan

20
00:01:09,380 --> 00:01:11,720
sa parehong unang listahan.

21
00:01:11,720 --> 00:01:14,850
Parehong 15 at 16 sa listahan sa kaliwa.

22
00:01:14,850 --> 00:01:19,810
Nanlilinlang ay upang samantalahin ng katotohanan na ang parehong mga listahan ay pinagsunod-sunod.

23
00:01:19,810 --> 00:01:23,320
Nangangahulugan ito na kung lamang namin tumingin sa unang elemento ng parehong mga listahan -

24
00:01:23,320 --> 00:01:29,580
dito, 4 at 8 - isa sa mga ito ay dapat ding maging ang unang elemento ng naka-merge na listahan.

25
00:01:29,580 --> 00:01:31,620
Well, kung bakit ay na?

26
00:01:31,620 --> 00:01:33,520
Parehong ng mga listahan ay pinagsunod-sunod,

27
00:01:33,520 --> 00:01:38,410
at kaya alinman sa 4 o 8 dapat ang pinakamaliit na elemento kapag pagsamahin namin ang 2 listahan.

28
00:01:38,410 --> 00:01:41,770
Sa kasong ito, ang pinakamaliit ay 4,

29
00:01:41,770 --> 00:01:46,370
upang maaari naming kumuha ng 4 at gawin itong ang unang elemento ng aming mga naka-merge na listahan.

30
00:01:46,370 --> 00:01:50,710
Ngayon ay ipagpapatuloy namin ang pinagsasama ang natitirang 3 elemento ng ang unang listahan

31
00:01:50,710 --> 00:01:52,920
at 4 na elemento ng pangalawang listahan.

32
00:01:52,920 --> 00:01:57,150
>> Muli, kailangan lamang namin upang tumingin sa unang elemento ng parehong mga listahan.

33
00:01:57,150 --> 00:02:01,060
Ang mas maliit sa 2 ay dapat na ang pangalawang elemento ng aming mga naka-merge na listahan.

34
00:02:01,060 --> 00:02:05,440
Oras na ito, sa pagitan ng 8 at 15 ang pinakamaliit ay 8, at kaya namin isingit na

35
00:02:05,440 --> 00:02:09,240
bilang ang pangalawang elemento ng aming mga listahan ng pinagsunod-sunod.

36
00:02:09,240 --> 00:02:12,180
Maaari naming patuloy na naghahambing ng mga unang elemento ng parehong mga listahan

37
00:02:12,180 --> 00:02:14,420
at pag-alis ng mas maliit sa 2.

38
00:02:14,420 --> 00:02:19,460
Paghahambing ng 15 at 23, 15 ay mas maliit at sa gayon ay ang aming ikatlong elemento.

39
00:02:21,000 --> 00:02:23,910
Ngayon naghahambing ng 16 at 23, 16 ay mas maliit.

40
00:02:23,910 --> 00:02:26,820
Kaya, na ang ika-apat na elemento.

41
00:02:26,820 --> 00:02:30,390
>> Pansinin na ang 2 elemento ay nagmula mula sa parehong listahan sa isang hilera.

42
00:02:30,390 --> 00:02:34,400
Ito ay kung bakit ang naka-merge na listahan ay hindi lamang kahaliling elemento mula sa 2 listahan.

43
00:02:34,400 --> 00:02:40,020
Paghahambing ng 50 at 23, 23 ay mas maliit, kaya pinili namin na.

44
00:02:40,770 --> 00:02:44,070
Sa pagitan ng 50 at 42, 42 ay mas maliit.

45
00:02:44,070 --> 00:02:48,290
Sa pagitan ng 50 at 108, 50 ay mas maliit.

46
00:02:48,290 --> 00:02:52,330
At, sa wakas, kami na lang ay 108, kaya dapat itong pumunta sa dulo ng aming listahan.

47
00:02:53,750 --> 00:02:56,180
Pansinin na mayroon kaming gandang, pinagsunod-sunod listahan.

48
00:02:56,180 --> 00:02:59,040
Bawat oras na namin kumpara sa unang 2 elemento ng 2 listahan

49
00:02:59,040 --> 00:03:02,730
namin upang matukoy ang susunod na elemento ng naka-merge na listahan.

50
00:03:02,730 --> 00:03:08,070
Nangangahulugan ito na kung ang panghuling listahan ay naglalaman ng mga n numero, kung saan n dito ay 8,

51
00:03:08,070 --> 00:03:12,610
kailangan namin sa karamihan ng mga n paghahambing upang makuha ang lahat ng mga numero sa tamang lugar.

52
00:03:13,230 --> 00:03:16,230
Tulad ng isang algorithm ay sinabi upang tumakbo sa linear oras,

53
00:03:16,230 --> 00:03:18,090
ngunit huwag mag-alala tungkol na dito.

54
00:03:18,570 --> 00:03:22,810
>> Gamit ang aming algorithm para sa pinagsasama, maaari kaming magsagawa ng isang mabilis na pagsasama-uuri algorithm.

55
00:03:22,810 --> 00:03:25,170
Kaya, sabihin i-reset ang aming mga listahan.

56
00:03:35,210 --> 00:03:37,750
May 2 malaking hakbang sa proseso ng pagsasama-uuri.

57
00:03:37,750 --> 00:03:41,500
Una, patuloy na hatiin ang listahan ng mga tasa sa halves

58
00:03:41,500 --> 00:03:44,860
hanggang kami ay may isang bungkos ng mga listahan na may 1 tasa sa kanila.

59
00:03:44,860 --> 00:03:47,350
Huwag mag-alala kung ang isang listahan ay naglalaman ng isang kakaibang numero

60
00:03:47,350 --> 00:03:49,880
at hindi ka maaaring gumawa ng isang perpektong malinis na hiwa sa pagitan ng mga ito.

61
00:03:49,880 --> 00:03:53,750
Lang mang pick kung aling listahan upang isama ang dagdag na tasa.

62
00:03:53,750 --> 00:03:56,240
Kaya, sabihin hatiin ang mga listahang ito.

63
00:03:58,140 --> 00:04:01,310
Ngayon ay mayroon kaming 2 listahan.

64
00:04:04,120 --> 00:04:06,570
Ngayon ay mayroon kaming 4 na listahan.

65
00:04:10,350 --> 00:04:13,870
>> At ngayon kami ay may 8 mga listahan na may isang tasa sa bawat listahan.

66
00:04:13,870 --> 00:04:16,630
Kaya na ito para sa hakbang 1.

67
00:04:16,630 --> 00:04:22,230
Para sa hakbang 2, paulit-ulit kaming magsama ng mga pares ng mga listahan gamit ang sumanib algorithm na namin natutunan bago.

68
00:04:22,230 --> 00:04:29,160
Pagsasama sa 108 at 15, magtapos namin sa listahan sa 15, 108.

69
00:04:30,330 --> 00:04:36,250
Pinagsasama ang 50 at 4, magtapos namin na may 4, 50.

70
00:04:36,960 --> 00:04:41,400
Pagsasama sa 8 at 42, magtapos namin na may 8, 42.

71
00:04:42,790 --> 00:04:48,130
At pinagsasama ng 23 at 16, kami magtapos na may 16, 23.

72
00:04:49,740 --> 00:04:52,450
Ngayon ang lahat ng aming mga listahan ng laki 2.

73
00:04:53,020 --> 00:04:56,180
Pansinin na ang bawat isa sa 4 na listahan ay pinagsunod-sunod.

74
00:04:56,180 --> 00:04:59,160
>> Upang maaari naming simulan ang pinagsasama ng mga pares ng mga listahan muli.

75
00:04:59,160 --> 00:05:03,240
Pagsasama sa 15 at 108 at 4 at 50 -

76
00:05:03,240 --> 00:05:11,170
tumagal muna ang 4, pagkatapos ang 15, pagkatapos ay ang 50, pagkatapos ang 108.

77
00:05:11,170 --> 00:05:15,120
Pagsasama sa 8, 42 at 16, 23,

78
00:05:15,120 --> 00:05:22,440
muna namin ang 8, pagkatapos ang 16, pagkatapos ay ang 23, pagkatapos ay ang 42.

79
00:05:22,440 --> 00:05:27,370
Kaya ngayon mayroon kaming may 2 listahan ng mga laki 4, ang bawat isa ay pinagsunod-sunod.

80
00:05:27,370 --> 00:05:30,980
Kaya ngayon bumaybay namin mga 2 listahan.

81
00:05:30,980 --> 00:05:33,440
Una namin ang 4.

82
00:05:33,440 --> 00:05:36,580
Pagkatapos naming gawin ang 8.

83
00:05:36,580 --> 00:05:50,700
Pagkatapos namin tumagal ng 15 at 16, pagkatapos 23, pagkatapos 42, pagkatapos 50, pagkatapos 108.

84
00:05:50,700 --> 00:05:52,220
At tapos na kami.

85
00:05:52,220 --> 00:05:54,900
Namin ngayon ay may pinagsunod-sunod listahan.

86
00:05:54,900 --> 00:05:57,890
Kaya kung gaano kabilis ang ito, eksakto?

87
00:05:57,890 --> 00:06:02,000
Sa teknikal na termino, pagsasama-uuri ay O (n log n),

88
00:06:02,000 --> 00:06:07,380
kung saan ang lahat ng bubble-uri-uriin, pagpapasok ng uri, at pagpili-uuri ay O (n ²).

89
00:06:07,380 --> 00:06:11,120
Sa katunayan, tulad ng makikita mo malaman sa lalong madaling panahon, hindi mo upang makabuo ng isang uri

90
00:06:11,120 --> 00:06:14,820
na mas mahusay na gumaganap kaysa sa O (n log n) sa pangkalahatang kaso.

91
00:06:14,820 --> 00:06:19,120
Muli, huwag mag-alala tungkol sa malaking O pagtatanda kung hindi mo pa nakikita ko pa ito.

92
00:06:19,120 --> 00:06:23,490
>> Lamang malaman na ang ibig sabihin nito ay kung gusto namin upang pag-uri-uriin ang isang talagang malaking listahan

93
00:06:23,490 --> 00:06:26,820
bubble-uri-uriin, pagpapasok ng uri, at pagpili-uuri ay maaaring potensyal na tumagal

94
00:06:26,820 --> 00:06:29,500
makabuluhang mas mahaba kaysa sa sumanib-uuri.

95
00:06:29,500 --> 00:06:33,210
Hindi ito nangangahulugan na ang pagsasama-uuri ay mas mabilis na para sa lahat ng mga listahan

96
00:06:33,210 --> 00:06:36,220
o kahit na para sa anumang solong listahan sa ilalim ng isang tiyak na laki.

97
00:06:36,220 --> 00:06:41,950
Halimbawa, ang pagpapasok ng-uuri ay maaaring ang pinakamabilis na uri para sa lahat ng mga listahan na mas maliit sa 5 elemento.

98
00:06:41,950 --> 00:06:47,360
Sa pagsasagawa, ang pagsasama-uuri ay karaniwang mas mabilis para sa listahan bilang maliit na bilang 50 mga elemento.

99
00:06:47,360 --> 00:06:51,120
>> Ngunit ang dagdag na bilis na ito ay hindi ay walang presyo.

100
00:06:51,120 --> 00:06:54,770
Hindi tulad ng aming iba pang mga uri, na gumawa ng isang listahan at baguhin ang listahan sa lugar

101
00:06:54,770 --> 00:06:58,740
hanggang sa makuha namin pinagsunod-sunod listahan, pagsasama-uuri ay nangangailangan ng ilang dagdag na espasyo

102
00:06:58,740 --> 00:07:00,900
upang sumanib 2 listahan.

103
00:07:00,900 --> 00:07:04,690
Hindi agad namin maaaring gamitin ang mga listahan na ay Pinagsama upang mag-imbak ang mga naka-merge na listahan

104
00:07:04,690 --> 00:07:08,880
dahil maaari naming i-override ang mga elemento na kailangan pa rin na Pinagsama.

105
00:07:08,880 --> 00:07:13,540
Espasyo na ito ay isang bit ng isang presyo, ngunit karaniwang ay hindi walang katwiran.

106
00:07:13,540 --> 00:07:15,330
At na ito para sa pagsasama-uuri.

107
00:07:15,330 --> 00:07:18,490
>> Ang pangalan ko ay Rob Bowden, at ito ay CS50.

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

109
00:07:20,500 --> 00:07:24,000
- At pagpili-uuri.

110
00:07:24,000 --> 00:07:25,880
[Laughs]

111
00:07:25,880 --> 00:07:31,480
Oh, nakuha ko na kumuha na ang masyadong dahil lumipat ako kung paano ko ay nagtatanghal ito.

112
00:07:31,480 --> 00:07:35,680
Listahan sa kaliwa. Na ay isang typo.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] ko screwed up -

114
00:07:39,290 --> 00:07:41,190
[Laughs]

115
00:07:41,190 --> 00:07:44,190
Hindi ko alam kung ano -