1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Rendit futjes]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Universiteti i Harvardit]

3
00:00:04,240 --> 00:00:07,290
[Kjo është CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Le të marrin një vështrim në lloj futje, një algoritmi për të marrë një listë të numrave dhe zgjidhja e tyre.

5
00:00:13,060 --> 00:00:18,300
Një algoritëm, mbani mend, është thjesht një hap-pas-hapi procedurat për kryerjen e një detyre.

6
00:00:18,300 --> 00:00:23,640
Ideja themelore pas lloj futje, është që të ndajë listën tonë në dy pjesë,

7
00:00:23,640 --> 00:00:26,580
një pjesë të renditura dhe një pjesë unsorted.

8
00:00:26,580 --> 00:00:29,290
>> Në çdo hap të algorithm, një numër i është lëvizur

9
00:00:29,290 --> 00:00:32,439
nga pjesa Unsorted tek pjesën renditura

10
00:00:32,439 --> 00:00:35,680
deri në fund listën tërë renditura.

11
00:00:35,680 --> 00:00:43,340
Këtu është lista e gjashtë numrave klasifikuara - 23, 42, 4, 16, 8, dhe 15.

12
00:00:43,340 --> 00:00:47,680
Që këto shifra nuk janë të gjitha në ngjitje qëllim, ata janë Unsorted.

13
00:00:47,680 --> 00:00:53,890
Që ne nuk kemi filluar ende klasifikim, ne do të konsiderojnë të gjitha gjashtë elemente pjesën tonë Unsorted.

14
00:00:53,890 --> 00:00:59,270
>> Sapo ne fillojmë klasifikim, ne do të vënë këto numra të renditura në të majtë të tyre.

15
00:00:59,270 --> 00:01:03,600
Pra, le të fillojë me 23, elementi i parë në listën tonë.

16
00:01:03,600 --> 00:01:06,930
Ne nuk kemi ndonjë elemente në pjesën tonë të renditura ende,

17
00:01:06,930 --> 00:01:12,460
kështu që le të konsiderojmë thjesht 23 të jetë fillimi dhe fundi i pjesës tonë të renditura.

18
00:01:12,460 --> 00:01:16,510
Tani, pjesa jonë ka renditur një numër, 23,

19
00:01:16,510 --> 00:01:20,260
dhe pjesa jonë unsorted ka këto pesë numra.

20
00:01:20,260 --> 00:01:27,320
Le tani futni numrin e ardhshëm në pjesën tonë Unsorted, 42, në pjesën e renditura.

21
00:01:27,320 --> 00:01:35,930
>> Për ta bërë këtë, ne do të duhet të krahasojnë 42 për 23 - i vetmi element në pjesën tonë të renditura deri tani.

22
00:01:35,930 --> 00:01:41,980
Dyzet e dy është më i madh se 23, kështu që ne thjesht mund të append 42 deri në fund

23
00:01:41,980 --> 00:01:45,420
i pjesës renditura e lista. E madhe!

24
00:01:45,420 --> 00:01:51,850
Tani pjesa jonë renditura ka dy elemente, dhe pjesa jonë unsorted ka katër elemente.

25
00:01:51,850 --> 00:01:57,200
Pra, le të lëvizë tani në 4, elementi tjetër në pjesën Unsorted.

26
00:01:57,200 --> 00:02:00,230
Pra, ku kjo duhet të vendoset në pjesën e renditura?

27
00:02:00,230 --> 00:02:04,220
>> Mos harroni, ne duam të vendosni këtë numër, në mënyrë renditura

28
00:02:04,220 --> 00:02:08,680
kështu që pjesa jonë renditura mbetet renditura saktë në të gjitha kohët.

29
00:02:08,680 --> 00:02:14,380
Nëse ne vendin e 4 për të drejtën e 42, pastaj lista jonë do të jetë jashtë rendit.

30
00:02:14,380 --> 00:02:18,380
Pra, le të vazhdojë të lëvizur drejtë të majtë në pjesën tonë të renditjes.

31
00:02:18,380 --> 00:02:23,260
Si ne shkojmë, le të zhvendoset çdo numër poshtë një vend për të bërë vend për numrin e ri.

32
00:02:25,440 --> 00:02:31,740
Mirë, 4 është edhe më pak se 23, kështu që ne nuk mund të zhvillohet këtu ose.

33
00:02:31,740 --> 00:02:34,480
Le të lëvizë drejtë vendin e 23 një.

34
00:02:36,500 --> 00:02:43,120
>> Kjo do të thotë që ne do të donim për të vendosur 4 në slot parë në pjesën e renditura.

35
00:02:43,120 --> 00:02:46,300
Vini re se si kjo hapësirë ​​në listën tashmë ishte bosh,

36
00:02:46,300 --> 00:02:51,120
sepse ne kemi qenë duke lëvizur elementet e renditura poshtë si ne kemi hasur ato.

37
00:02:51,120 --> 00:02:52,740
Dakord. Pra, ne jemi në gjysmë të rrugës atje.

38
00:02:52,740 --> 00:02:57,990
Le të vazhdojmë algorithm tonë, duke futur 16 në pjesën e renditura.

39
00:02:59,260 --> 00:03:03,820
Gjashtëmbëdhjetë është më pak se 42, kështu që le të zhvendoset e 42 në të djathtë.

40
00:03:05,700 --> 00:03:10,190
Gjashtëmbëdhjetë është edhe më pak se 23, kështu që le të zhvendoset atë element.

41
00:03:11,790 --> 00:03:20,820
>> Tani, 16 është më i madh se 4. Pra, kjo duket si ne do të donim për të futur 16 mes 4 dhe 23.

42
00:03:20,820 --> 00:03:24,620
Ndërsa lëvizin nëpër pjesën e renditura të listës nga e djathta në të majtë,

43
00:03:24,620 --> 00:03:29,160
4 është numri i parë ne kemi parë se është më i vogël se numri i

44
00:03:29,160 --> 00:03:31,540
ne jemi duke u përpjekur për të futur.

45
00:03:31,540 --> 00:03:35,820
Pra, tani ne mund të futur 16 në këtë slot bosh,

46
00:03:35,820 --> 00:03:40,520
i cili, mos harroni, ne kemi krijuar nga elementet lëvizin në pjesën e renditjes gjatë

47
00:03:40,520 --> 00:03:43,340
si ne kemi hasur ato.

48
00:03:43,340 --> 00:03:47,900
>> Dakord. Tani, ne kemi katër elemente të renditura dhe Unsorted dy elemente.

49
00:03:47,900 --> 00:03:51,600
Pra, le të lëvizë 8 në pjesën e renditura.

50
00:03:51,600 --> 00:03:55,010
Tetë është më pak se 42.

51
00:03:55,010 --> 00:03:56,940
Tetë është më pak se 23.

52
00:03:56,940 --> 00:04:00,230
Dhe 8 është më pak se 16.

53
00:04:00,230 --> 00:04:03,110
Por është më i madh se 8 4.

54
00:04:03,110 --> 00:04:07,280
Pra, ne do të donim për të futur 8 mes 4 dhe 16.

55
00:04:09,070 --> 00:04:13,650
Dhe tani ne vetëm kemi lënë një element më shumë për të zgjidhur - e 15.

56
00:04:13,950 --> 00:04:16,589
Pesëmbëdhjetë është më pak se 42,

57
00:04:16,589 --> 00:04:19,130
Pesëmbëdhjetë është më pak se 23.

58
00:04:19,130 --> 00:04:21,750
Dhe 15 është më pak se 16.

59
00:04:21,750 --> 00:04:24,810
Por 15 është më e madhe se 8.

60
00:04:24,810 --> 00:04:27,440
>> Pra, këtu është vendi ku ne duam të bërë futjen tonë përfundimtar.

61
00:04:28,770 --> 00:04:30,330
Dhe ne jemi duke bërë.

62
00:04:30,330 --> 00:04:33,540
Ne nuk kemi elemente shumë në pjesën Unsorted,

63
00:04:33,540 --> 00:04:36,670
dhe pjesa jonë është të renditura në mënyrë korrekte.

64
00:04:36,670 --> 00:04:40,270
Numrat janë urdhëruar nga më i vogli tek më i madhi.

65
00:04:40,270 --> 00:04:44,330
Pra, le të marrin një vështrim në disa pseudokod që përshkruan hapat që sapo kryera.

66
00:04:46,760 --> 00:04:51,740
>> On line 1, ne mund të shohim se ne do të duhet të iterate mbi çdo element në listë

67
00:04:51,740 --> 00:04:57,060
përveç parë, pasi elementin e parë në pjesën Unsorted thjesht do të bëhet

68
00:04:57,060 --> 00:05:00,220
Elementi i parë në pjesën e renditura.

69
00:05:00,220 --> 00:05:06,320
Në linjat e 2 dhe 3, ne jemi mbajtja e vendit tonë aktuale në pjesën Unsorted.

70
00:05:06,320 --> 00:05:10,450
Element paraqet numrin ne jemi duke lëvizur në pjesën renditura,

71
00:05:10,450 --> 00:05:15,600
dhe j paraqet indeksin tonë në pjesën Unsorted.

72
00:05:15,600 --> 00:05:20,980
>> On line 4, ne jemi iterating përmes pjesës renditura nga e djathta në të majtë.

73
00:05:20,980 --> 00:05:26,010
Ne duam të ndaluar iterating herë elementin në të majtë të pozicionit tonë aktual

74
00:05:26,010 --> 00:05:30,050
është më pak se ne jemi duke u përpjekur element të futur.

75
00:05:30,050 --> 00:05:35,600
On line 5, ne jemi zhvendosur çdo element hasim një hapësirë ​​në të djathtë.

76
00:05:35,600 --> 00:05:40,950
Në këtë mënyrë, ne do të kemi një hapësirë ​​të qartë për të futur në kur kemi gjetur elementin e parë

77
00:05:40,950 --> 00:05:44,080
më pak se elementi që ne jemi duke shkuar.

78
00:05:44,080 --> 00:05:50,800
On line 6, ne jemi përditësimin counter tonë për të vazhduar për të lëvizur majtë nëpër pjesën e renditura.

79
00:05:50,800 --> 00:05:56,860
Së fundi, në përputhje 7, ne jemi duke futur elementin në pjesën e renditura të listës.

80
00:05:56,860 --> 00:06:00,020
>> Ne e dimë se kjo është në rregull për të futur në j pozicion,

81
00:06:00,020 --> 00:06:05,360
sepse ne kemi lëvizur tashmë element që përdoret për të jetë atje një hapësirë ​​në të djathtë.

82
00:06:05,360 --> 00:06:09,460
Mos harroni, ne jemi duke lëvizur nëpër pjesën e renditura nga djathta në të majtë,

83
00:06:09,460 --> 00:06:13,960
por ne jemi duke lëvizur nëpër pjesën Unsorted nga e majta në të djathtë.

84
00:06:13,960 --> 00:06:19,090
Dakord. Le të marrë tani një vështrim në sa kohë drejtimin që mori algorithm.

85
00:06:19,090 --> 00:06:25,300
Ne do të pari shtrohet pyetja se sa kohë do të marrë për këtë algoritëm për të kandiduar në rastin më të keq.

86
00:06:25,300 --> 00:06:29,040
Kujtojnë se ne përfaqësojmë këtë kohë running me simbol Big O.

87
00:06:32,530 --> 00:06:38,500
Në mënyrë për të zgjidhur listën tonë, ne kishim për të iterate mbi elementet në pjesën Unsorted,

88
00:06:38,500 --> 00:06:43,430
dhe për secilin nga këto elemente, potencialisht mbi të gjitha elementet në pjesën e renditura.

89
00:06:43,430 --> 00:06:47,950
Intuitive, kjo tingëllon si një operacion (n ^ 2) O.

90
00:06:47,950 --> 00:06:51,840
>> Kërkim në pseudokod tonë, ne kemi një lak mbivendosur brenda një tjetër lak,

91
00:06:51,840 --> 00:06:55,290
të cilat, në të vërtetë, tingëllon si një operacion (n ^ 2) O.

92
00:06:55,290 --> 00:07:01,590
Megjithatë, pjesa renditur i listës nuk përmbajnë të gjithë listën deri në fund.

93
00:07:01,590 --> 00:07:06,920
Megjithatë, ne mund të potencialisht të futur një element të ri në fillim të pjesës renditura

94
00:07:06,920 --> 00:07:09,320
në çdo ripërsëritje e algoritmi,

95
00:07:09,320 --> 00:07:14,500
që do të thotë se ne do të duhet të shikojmë në çdo element aktualisht në pjesën e renditura.

96
00:07:14,500 --> 00:07:20,090
Pra, kjo do të thotë që ne mund të potencialisht të bëjë një krahasim për elementin e dytë,

97
00:07:20,090 --> 00:07:24,660
dy krahasime për elementin e tretë, dhe kështu me radhë.

98
00:07:24,660 --> 00:07:32,480
Kështu, numri i përgjithshëm i hapave është shuma e numrave të plotë nga 1 deri në gjatësinë e listës minus 1.

99
00:07:32,480 --> 00:07:35,240
Ne mund të përfaqësojë këtë me një mbledhje.

100
00:07:41,170 --> 00:07:47,270
>> Ne nuk do të shkojë në summations këtu, por rezulton se kjo përmbledhje është e barabartë me

101
00:07:47,270 --> 00:07:57,900
N (n - 1) mbi 2, e cila është n ekuivalent ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Kur flasim për kohën e duhur asymptotic,

103
00:08:00,800 --> 00:08:05,170
kjo ^ n 2 Termi do të dominojë këtë term n.

104
00:08:05,170 --> 00:08:11,430
Pra, lloj futje është Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Çfarë ndodh nëse ne u lloj futje në një listë të renditura tashmë.

106
00:08:16,150 --> 00:08:20,960
Në këtë rast, ne do të thjesht të ndërtuar pjesën e renditura nga e majta në të djathtë.

107
00:08:20,960 --> 00:08:25,050
Pra, ne vetëm do të duhet në mënyrë të hapave n.

108
00:08:25,050 --> 00:08:29,740
>> Kjo do të thotë se lloj futje ka një performancë të mirë-rasti i n,

109
00:08:29,740 --> 00:08:34,130
që ne përfaqësojmë me Ω (n).

110
00:08:34,130 --> 00:08:36,190
Dhe kjo është ajo për lloj futje,

111
00:08:36,190 --> 00:08:40,429
vetëm një nga algoritme shumë ne mund të përdorim për të zgjidhur një listë.

112
00:08:40,429 --> 00:08:43,210
Emri im është Tommy, dhe kjo është CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, ju thjesht nuk mund të ndalet se sapo ajo fillon.

115
00:09:01,620 --> 00:09:04,760
Oh, ne e bëmë që - Boom >>!