1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Jingħaqdu Sort]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Università ta 'Harvard]

3
00:00:04,000 --> 00:00:07,000
[Dan huwa CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Ejja nitkellmu dwar it-tip jingħaqdu.

5
00:00:09,000 --> 00:00:14,000
S'issa inti stajt tidher tip bużżieqa, sort inserzjoni, u sort għażla.

6
00:00:14,000 --> 00:00:17,000
Għalkemm I ser tip ta 'mewġa idejn tiegħi fil dak I jfisser minn aħjar,

7
00:00:17,000 --> 00:00:21,000
jingħaqdu tip ġeneralment twettaq aħjar minn kwalunkwe minn dawn it-tipi 3.

8
00:00:22,000 --> 00:00:27,000
>> Iżda qabel ma jitkellem dwar it-tip jingħaqdu, ejja nitkellmu dwar amalgamazzjoni 2 jelenka magħżula.

9
00:00:27,000 --> 00:00:31,000
Aħna ser sejħa-proċess tat-teħid 2 jelenka magħżula, bħal dawn,

10
00:00:31,000 --> 00:00:35,000
u jagħmlu lista unika mifthiema minnhom - li qed jingħaqdu l-listi.

11
00:00:35,000 --> 00:00:37,750
Kif nistgħu nagħmlu dan?

12
00:00:37,750 --> 00:00:41,290
Ukoll, wieħed idea hija li biss stick lista waħda fuq it-tmiem tal-lista l-oħra

13
00:00:41,290 --> 00:00:43,830
u mbagħad sort l-lista li jirriżulta.

14
00:00:43,830 --> 00:00:47,220
>> Filwaqt li dan jaħdem, huwa ħafna xogħol bla bżonn.

15
00:00:47,220 --> 00:00:49,900
Nistgħu nagħmlu dan aktar malajr milli sempliċiment għażla.

16
00:00:49,900 --> 00:00:54,100
Avviż li wieħed idea ħażina hija li ħu tazzi jalternaw minn kull lista.

17
00:00:54,100 --> 00:00:56,460
Filwaqt li jista 'jidher li x-xogħlijiet fl-ewwel,

18
00:00:56,460 --> 00:01:05,760
tagħmel li aħna jispiċċaw ma 4, 8, 15, 23, 16 - avviż li 16 u 23 huma barra mill-post.

19
00:01:05,760 --> 00:01:09,380
Dan huwa minħabba 2 elementi li għandhom jidhru konsekuttiva fil-lista magħquda

20
00:01:09,380 --> 00:01:11,720
huma fil-lista inizjali istess.

21
00:01:11,720 --> 00:01:14,850
Kemm 15 u 16 huma fil-lista fuq ix-xellug.

22
00:01:14,850 --> 00:01:19,810
Il-trick huwa li jieħdu vantaġġ mill-fatt li ż-żewġ listi huma diġà magħżula.

23
00:01:19,810 --> 00:01:23,320
Dan ifisser li jekk aħna biss ħarsa lejn l-ewwel elementi taż-żewġ listi -

24
00:01:23,320 --> 00:01:29,580
hawn, 4 u 8 - wieħed minnhom għandhom ukoll ikunu l-ewwel element tal-lista magħquda.

25
00:01:29,580 --> 00:01:31,620
Ukoll, għaliex huwa li?

26
00:01:31,620 --> 00:01:33,520
Dawn iż-żewġ listi huma diġà magħżula,

27
00:01:33,520 --> 00:01:38,410
u dan jew 4 jew 8 irid ikun l-element iżgħar meta aħna ngħaqqdu l-listi 2.

28
00:01:38,410 --> 00:01:41,770
F'dan il-każ, l-iżgħar huwa 4,

29
00:01:41,770 --> 00:01:46,370
hekk nistgħu jieħdu out 4 u jagħmilha l-ewwel element tal-lista magħquda tagħna.

30
00:01:46,370 --> 00:01:50,710
Issa aħna nkomplu li qed jingħaqdu l-bqija 3 elementi tal-ewwel lista

31
00:01:50,710 --> 00:01:52,920
u 4 elementi tal-lista tat-tieni.

32
00:01:52,920 --> 00:01:57,150
>> Għal darb'oħra, aħna biss bżonn li nħarsu lejn l-ewwel element ta 'żewġ listi.

33
00:01:57,150 --> 00:02:01,060
L-iżgħar tal-2 għandha tkun it-tieni element tal-lista magħquda tagħna.

34
00:02:01,060 --> 00:02:05,440
Din id-darba, bejn 8 u 15-iżgħar huwa 8, u hekk aħna daħħal li

35
00:02:05,440 --> 00:02:09,240
bħala l-element tieni lista magħżula tagħna.

36
00:02:09,240 --> 00:02:12,180
Nistgħu tkompli tqabbel l-ewwel elementi taż-żewġ listi

37
00:02:12,180 --> 00:02:14,420
u tneħħi l-iżgħar ta 'l-2.

38
00:02:14,420 --> 00:02:19,460
Tqabbil 15 u 23, 15 hija iżgħar u għalhekk dan huwa tielet element tagħna.

39
00:02:21,000 --> 00:02:23,910
Issa jitqabblu 16 u 23, 16 hija iżgħar.

40
00:02:23,910 --> 00:02:26,820
Allura dak l-element 4.

41
00:02:26,820 --> 00:02:30,390
>> Avviż li 2 elementi ġew mill-istess lista fil-filliera.

42
00:02:30,390 --> 00:02:34,400
Dan huwa għaliex il-lista magħquda ma tistax biss elementi supplenti mil-listi 2.

43
00:02:34,400 --> 00:02:40,020
Tqabbil 50 u 23, 23 hija iżgħar, hekk aħna jagħżlu li.

44
00:02:40,770 --> 00:02:44,070
Bejn 50 u 42, 42 hija iżgħar.

45
00:02:44,070 --> 00:02:48,290
Bejn 50 u 108, 50 hija iżgħar.

46
00:02:48,290 --> 00:02:52,330
U, finalment, aħna biss ikollhom 108, u għalhekk għandha timxi fuq l-aħħar tal-lista tagħna.

47
00:02:53,750 --> 00:02:56,180
Avviż li għandna sbieħ, lista magħżula.

48
00:02:56,180 --> 00:02:59,040
Kull darba qabbilna l-ewwel 2 elementi tal-listi 2

49
00:02:59,040 --> 00:03:02,730
konna kapaċi li jiddeterminaw l-element li jmiss tal-lista magħquda.

50
00:03:02,730 --> 00:03:08,070
Dan ifisser li jekk il-lista finali fih in-numri n, fejn n hija hawnhekk 8,

51
00:03:08,070 --> 00:03:12,610
allura għandna bżonn fil-paraguni aktar n biex tikseb kollha ta 'dawn in-numri fil-post it-tajjeb.

52
00:03:13,230 --> 00:03:16,230
Tali algoritmu huwa qal li jimxu fil-ħin lineari,

53
00:03:16,230 --> 00:03:18,090
iżda ma joqogħdu jinkwetaw dwar li hawn.

54
00:03:18,570 --> 00:03:22,810
>> Bl-użu algoritmu tagħna għall jingħaqdu, nistgħu nagħmlu l-algoritmu mgħaġġel sort jingħaqdu.

55
00:03:22,810 --> 00:03:25,170
Allura, ejja reset listi tagħna.

56
00:03:35,210 --> 00:03:37,750
Hemm 2 passi kbar fil-proċess ta 'tip jingħaqdu.

57
00:03:37,750 --> 00:03:41,500
L-ewwel, kontinwament taqsam il-lista tal-cups fis nofsijiet

58
00:03:41,500 --> 00:03:44,860
sakemm għandna mazz ta 'listi mal biss 1 tazza fihom.

59
00:03:44,860 --> 00:03:47,350
Tinkwetax jekk lista fiha numru fard

60
00:03:47,350 --> 00:03:49,880
u inti ma tistax tagħmel qatgħa perfettament nadif bejniethom.

61
00:03:49,880 --> 00:03:53,750
Just pick arbitrarjament li lista biex tinkludi l-tazza żejda pulzieri

62
00:03:53,750 --> 00:03:56,240
Allura, ejja maqsuma dawn il-listi.

63
00:03:58,140 --> 00:04:01,310
Issa għandna 2 listi.

64
00:04:04,120 --> 00:04:06,570
Issa għandna 4 listi.

65
00:04:10,350 --> 00:04:13,870
>> U issa għandna 8 listi ma 'tazza waħda f'kull lista.

66
00:04:13,870 --> 00:04:16,630
Allura dak li għall-pass 1.

67
00:04:16,630 --> 00:04:22,230
Għal pass 2, aħna ripetutament jingħaqdu pari ta 'listi li jużaw l-algoritmu jingħaqdu aħna tgħallimna qabel.

68
00:04:22,230 --> 00:04:29,160
Twaħħid 108 u 15, aħna jispiċċaw mal-lista 15, 108.

69
00:04:30,330 --> 00:04:36,250
Twaħħid 50 u 4, aħna jispiċċaw ma '4, 50.

70
00:04:36,960 --> 00:04:41,400
Twaħħid 8 u 42, aħna jispiċċaw bi 8, 42.

71
00:04:42,790 --> 00:04:48,130
U qed jingħaqdu 23 u 16, aħna jispiċċaw ma 16, 23.

72
00:04:49,740 --> 00:04:52,450
Issa listi kollha tagħna huma ta 'daqs 2.

73
00:04:53,020 --> 00:04:56,180
Avviż li kull wieħed mill-listi 4 huwa magħżul.

74
00:04:56,180 --> 00:04:59,160
>> Allura aħna tista 'tibda amalgamazzjoni pari ta' listi ġdid.

75
00:04:59,160 --> 00:05:03,240
Twaħħid 15 u 108 u 4 u 50 -

76
00:05:03,240 --> 00:05:11,170
1 jieħdu l-4, allura l-15, allura l-50, allura l-108.

77
00:05:11,170 --> 00:05:15,120
Twaħħid 8, 42 u 16, 23,

78
00:05:15,120 --> 00:05:22,440
aħna l-ewwel jieħu l-8, allura l-16, allura l-23, allura l-42.

79
00:05:22,440 --> 00:05:27,370
Allura issa għandna biss 2 listi ta 'daqs 4, li kull wieħed minnhom huwa magħżul.

80
00:05:27,370 --> 00:05:30,980
Allura issa aħna jingħaqdu dawn il-listi 2.

81
00:05:30,980 --> 00:05:33,440
L-ewwel nieħdu l-4.

82
00:05:33,440 --> 00:05:36,580
Imbagħad aħna jieħdu l-8.

83
00:05:36,580 --> 00:05:50,700
Imbagħad nieħdu l-15 u 16, allura 23, imbagħad 42, imbagħad 50, imbagħad 108.

84
00:05:50,700 --> 00:05:52,220
U aħna qed isir.

85
00:05:52,220 --> 00:05:54,900
Issa għandna lista magħżula.

86
00:05:54,900 --> 00:05:57,890
Allura kif fast kien dan, eżattament?

87
00:05:57,890 --> 00:06:02,000
F'termini tekniċi, xorta jingħaqdu hija O (n log n),

88
00:06:02,000 --> 00:06:07,380
billi kollha ta 'tip bużżieqa, sort inserzjoni, u sort l-għażla huma O (n ²).

89
00:06:07,380 --> 00:06:11,120
Fil-fatt, kif inti ser jitgħallmu malajr, inti mhux se tkun kapaċi li toħroġ bi speċi

90
00:06:11,120 --> 00:06:14,820
li jwettaq aħjar minn O (n log n) fil-każ ġenerali.

91
00:06:14,820 --> 00:06:19,120
Għal darb'oħra, ma joqogħdu jinkwetaw dwar dan notazzjoni O kbir jekk inti ma bbenefikawx encore.

92
00:06:19,120 --> 00:06:23,490
>> Biss jafu li dan ifisser li jekk ridna li sort lista verament kbir

93
00:06:23,490 --> 00:06:26,820
sort bużżieqa, sort inserzjoni, u l-għażla sort potenzjalment jistgħu jieħdu

94
00:06:26,820 --> 00:06:29,500
wisq itwal minn jingħaqdu tip.

95
00:06:29,500 --> 00:06:33,210
Dan ma jfissirx li tip jingħaqdu se tkun iktar mgħaġġla għall-listi kollha

96
00:06:33,210 --> 00:06:36,220
jew saħansitra għal xi lista waħdanija taħt ċertu daqs.

97
00:06:36,220 --> 00:06:41,950
Per eżempju, it-tip inserzjoni tista 'tkun l-xorta aktar mgħaġġla għall-listi kollha iżgħar minn 5 elementi.

98
00:06:41,950 --> 00:06:47,360
Fil-prattika, xorta jingħaqdu huwa normalment aktar mgħaġġel għal listi żgħira kemm 50 elementi.

99
00:06:47,360 --> 00:06:51,120
>> Iżda din il-veloċità żejda ma jaqax mingħajr prezz.

100
00:06:51,120 --> 00:06:54,770
B'differenza tipi oħra tagħna, li jieħu lista u timmodifika l-lista fil-post

101
00:06:54,770 --> 00:06:58,740
sakemm aħna jiksbu lista magħżula, sort jingħaqdu teħtieġ xi spazju addizzjonali

102
00:06:58,740 --> 00:07:00,900
biex jingħaqdu 2 telenka flimkien.

103
00:07:00,900 --> 00:07:04,690
Aħna ma jistax immedjatament jużaw il-listi li qed jiġu amalgamati biex jaħżnu l-lista magħquda

104
00:07:04,690 --> 00:07:08,880
peress li aħna jista 'jwarrab l-elementi li għad iridu jiġu amalgamati.

105
00:07:08,880 --> 00:07:13,540
Dan l-ispazju huwa daqsxejn ta 'prezz, iżda normalment mhuwiex irraġonevoli.

106
00:07:13,540 --> 00:07:15,330
U li hija għal tip jingħaqdu.

107
00:07:15,330 --> 00:07:18,490
>> Jisimni Rob Bowden, u dan huwa CS50.

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

109
00:07:20,500 --> 00:07:24,000
- U l-għażla tip.

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

111
00:07:25,880 --> 00:07:31,480
Oh, ltqajna biex jieħdu dik fl wisq minħabba I switched kif I kien jippreżentah.

112
00:07:31,480 --> 00:07:35,680
Lista ix-xellug. Dan kien typo.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] I invitat up -

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

115
00:07:41,190 --> 00:07:44,190
I do not know dak -