1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Innskot Raða]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvard University]

3
00:00:04,240 --> 00:00:07,290
[Þetta er CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Við skulum taka a líta á Innsetningarröðun, algrím til að taka lista yfir númer og flokkun þeirra.

5
00:00:13,060 --> 00:00:18,300
Reiknirit, muna, er einfaldlega skref-fyrir-skref aðferð til að ljúka verkefni.

6
00:00:18,300 --> 00:00:23,640
Grunnhugmyndin á bak við Innsetningarröðun, er að skipta lista okkar í tvo hluta,

7
00:00:23,640 --> 00:00:26,580
a raðað hluti og unsorted hluta.

8
00:00:26,580 --> 00:00:29,290
>> Í hvert skref reiknirit, er fjöldi flutt

9
00:00:29,290 --> 00:00:32,439
frá óflokkuðu hluta til raðað hluta

10
00:00:32,439 --> 00:00:35,680
þar til að lokum alla lista er raðað.

11
00:00:35,680 --> 00:00:43,340
Hér er listi af sex unsorted tölur - 23, 42, 4, 16, 8, og 15.

12
00:00:43,340 --> 00:00:47,680
Þar sem þessar tölur eru ekki allt í réttri röð, þá eru þeir Unsorted.

13
00:00:47,680 --> 00:00:53,890
Þar sem við höfum ekki byrjað flokkun enn, munum við íhuga öllum sex Elements óflokkuðu hluta okkar.

14
00:00:53,890 --> 00:00:59,270
>> Þegar við byrjum að flokkun, munum við setja þessar flokkuð númer vinstra megin við þá.

15
00:00:59,270 --> 00:01:03,600
Svo, við skulum byrja með 23, fyrsti þáttur í lista okkar.

16
00:01:03,600 --> 00:01:06,930
Við höfum engar þætti í raðaða hluta okkar enn,

17
00:01:06,930 --> 00:01:12,460
þannig að við skulum bara íhuga 23 til að byrja og enda á raðaða hluta okkar.

18
00:01:12,460 --> 00:01:16,510
Nú, raðað hluti okkar hefur eitt númer, 23,

19
00:01:16,510 --> 00:01:20,260
og Unsorted hluti okkar hefur þessar fimm tölur.

20
00:01:20,260 --> 00:01:27,320
Við skulum nú setja næsta númer í óflokkuðum hluta okkar, 42, í raðaða hluta.

21
00:01:27,320 --> 00:01:35,930
>> Til að gera það, munum við þurfa að bera 42 til 23 - eina þáttur í raðaða hluta okkar svo langt.

22
00:01:35,930 --> 00:01:41,980
Fjörutíu og tveir eru stærri en 23, svo við getum einfaldlega auka 42 til enda

23
00:01:41,980 --> 00:01:45,420
á raðaða hluta á listanum. Great!

24
00:01:45,420 --> 00:01:51,850
Nú hefur raðað hluti okkar tvo þætti, og unsorted hluti okkar hefur fjóra þætti.

25
00:01:51,850 --> 00:01:57,200
Svo skulum við nú fara á 4, næsti þáttur í óflokkuðu hluta.

26
00:01:57,200 --> 00:02:00,230
Svo, þar ætti þetta að vera sett í raðaða hluta?

27
00:02:00,230 --> 00:02:04,220
>> Mundu, við viljum að setja þessa tölu í raðað röð

28
00:02:04,220 --> 00:02:08,680
svo er raðað hluti okkar rétt raðað á öllum tímum.

29
00:02:08,680 --> 00:02:14,380
Ef við setja 4 til hægri um 42, þá lista okkar mun vera út af röð.

30
00:02:14,380 --> 00:02:18,380
Svo skulum við halda áfram að færa hægri til vinstri í hluta röðun okkar.

31
00:02:18,380 --> 00:02:23,260
Eins og við flutt, við skulum færa hvern tala niður stað til að gera pláss fyrir nýja númerið.

32
00:02:25,440 --> 00:02:31,740
Jæja, 4 er einnig minna en 23, svo við getum ekki sett það hér heldur.

33
00:02:31,740 --> 00:02:34,480
Við skulum færa 23 rétta stað.

34
00:02:36,500 --> 00:02:43,120
>> Það þýðir að við viljum að setja 4 í fyrsta rifa í raðaða hluta.

35
00:02:43,120 --> 00:02:46,300
Taktu eftir hvernig þetta rúm á listanum var þegar tóm,

36
00:02:46,300 --> 00:02:51,120
vegna þess að við höfum verið að færa flokkuð þætti niður eins og við höfum upp þá.

37
00:02:51,120 --> 00:02:52,740
Allt í lagi. Svo erum við komin með það.

38
00:02:52,740 --> 00:02:57,990
Við skulum halda áfram reiknirit okkar með því að setja 16 í raðaða hluta.

39
00:02:59,260 --> 00:03:03,820
Sextán er minna en 42, þannig að við skulum færa 42 til hægri.

40
00:03:05,700 --> 00:03:10,190
Sextán er einnig minna en 23, þannig að við skulum einnig skipta þessi þáttur.

41
00:03:11,790 --> 00:03:20,820
>> Nú, 16 er meira en 4. Svo lítur það eins og við viljum að setja 16 milli 4 og 23.

42
00:03:20,820 --> 00:03:24,620
Þó að fara í gegnum raðaða hluta lista frá hægri til vinstri,

43
00:03:24,620 --> 00:03:29,160
4 er fyrsta númerið sem við höfum séð að er minni en fjöldi

44
00:03:29,160 --> 00:03:31,540
við erum að reyna að setja inn.

45
00:03:31,540 --> 00:03:35,820
Svo nú getum við sett inn 16 í þessu tóma rifa,

46
00:03:35,820 --> 00:03:40,520
sem muna, höfum við búið til með því að færa atriði á röðun hluta yfir

47
00:03:40,520 --> 00:03:43,340
sem við höfum upp þá.

48
00:03:43,340 --> 00:03:47,900
>> Allt í lagi. Nú höfum við fjóra flokkuð þætti og tvo unsorted þætti.

49
00:03:47,900 --> 00:03:51,600
Svo skulum við færa 8 í raðaða hluta.

50
00:03:51,600 --> 00:03:55,010
Átta er minna en 42.

51
00:03:55,010 --> 00:03:56,940
Átta er minna en 23.

52
00:03:56,940 --> 00:04:00,230
Og 8 er minna en 16 ára.

53
00:04:00,230 --> 00:04:03,110
En 8 er meiri en 4.

54
00:04:03,110 --> 00:04:07,280
Svo viljum við gjarnan setja 8 milli 4 og 16 ára.

55
00:04:09,070 --> 00:04:13,650
Og nú höfum við bara einn þáttur til vinstri til að flokka - the 15.

56
00:04:13,950 --> 00:04:16,589
Fimmtán er minna en 42,

57
00:04:16,589 --> 00:04:19,130
Fimmtán er minna en 23.

58
00:04:19,130 --> 00:04:21,750
Og 15 er minna en 16 ára.

59
00:04:21,750 --> 00:04:24,810
En 15 er meiri en 8.

60
00:04:24,810 --> 00:04:27,440
>> Svo, hér er þar sem við viljum gera endanlega innsetningu okkar.

61
00:04:28,770 --> 00:04:30,330
Og við erum að gera.

62
00:04:30,330 --> 00:04:33,540
Við höfum ekki fleiri þætti í óflokkuðu hluta,

63
00:04:33,540 --> 00:04:36,670
og raðað hluti okkar er í réttri röð.

64
00:04:36,670 --> 00:04:40,270
Tölurnar eru pöntuð frá smæstu til stærstu.

65
00:04:40,270 --> 00:04:44,330
Svo skulum við taka a líta á sumir sauðakóðanum sem lýsir skref sem við gerðar rétt.

66
00:04:46,760 --> 00:04:51,740
>> Í línu 1, getum við séð að við munum þurfa að iterate yfir hvert frumefni á listanum

67
00:04:51,740 --> 00:04:57,060
nema fyrst, þar sem fyrsti þáttur í óflokkuðu hluta mun einfaldlega verða

68
00:04:57,060 --> 00:05:00,220
Fyrsti þátturinn í raðaða hluta.

69
00:05:00,220 --> 00:05:06,320
Á línum 2 og 3, erum við að halda utan um núverandi stað okkar í óflokkuðu hluta.

70
00:05:06,320 --> 00:05:10,450
Element táknar fjölda við erum nú að flytja inn í raðaða hluta,

71
00:05:10,450 --> 00:05:15,600
og j táknar vísitölu okkar í óflokkuðu hluta.

72
00:05:15,600 --> 00:05:20,980
>> Á línu 4, við erum iterating gegnum raðaða hluta frá hægri til vinstri.

73
00:05:20,980 --> 00:05:26,010
Við viljum hætta iterating einu frumefni til vinstri á núverandi stöðu okkar

74
00:05:26,010 --> 00:05:30,050
er minna en frumefni sem við erum að reyna að setja inn.

75
00:05:30,050 --> 00:05:35,600
Á línu 5, erum við að breytast í hvert frumefni við lendum eitt pláss til hægri.

76
00:05:35,600 --> 00:05:40,950
Þannig munum við hafa skýra pláss til að setja inn þegar við finnum í fyrsta frumefnið

77
00:05:40,950 --> 00:05:44,080
minna en frumefni sem við erum að flytja.

78
00:05:44,080 --> 00:05:50,800
On Line 6, við erum að uppfæra gegn okkar að halda áfram að færa til vinstri gegnum raðaða hluta.

79
00:05:50,800 --> 00:05:56,860
Að lokum, í línu 7, við erum að setja hluti inn í raðaða hluta á listanum.

80
00:05:56,860 --> 00:06:00,020
>> Við vitum að það er í lagi að setja inn j stöðu,

81
00:06:00,020 --> 00:06:05,360
vegna þess að við höfum nú þegar flutt þáttur sem er notað til að vera þar einn pláss til hægri.

82
00:06:05,360 --> 00:06:09,460
Mundu, við erum að fara í gegnum raðaða hluta frá hægri til vinstri,

83
00:06:09,460 --> 00:06:13,960
en við erum að fara í gegnum óflokkuðu hluta frá vinstri til hægri.

84
00:06:13,960 --> 00:06:19,090
Allt í lagi. Við skulum nú kíkja á hversu lengi í gangi að reiknirit tók.

85
00:06:19,090 --> 00:06:25,300
Við munum fyrst spyrja hversu langan tíma tekur það fyrir þetta reiknirit til að keyra í versta tilfelli.

86
00:06:25,300 --> 00:06:29,040
Muna að við komum þetta gangi tíma með Big O merki.

87
00:06:32,530 --> 00:06:38,500
Til að raða listanum okkar, áttum við að iterate yfir þá þætti í óflokkuðu hluta,

88
00:06:38,500 --> 00:06:43,430
og fyrir hvert af þessum þætti, hugsanlega yfir alla þætti í raðaða hluta.

89
00:06:43,430 --> 00:06:47,950
Innsæi, þetta hljómar eins og O (n ^ 2) starfsemi.

90
00:06:47,950 --> 00:06:51,840
>> Þegar litið er á sauðakóðanum höfum við lykkju hreiður inni annað lykkju,

91
00:06:51,840 --> 00:06:55,290
sem reyndar hljómar, eins og O (n ^ 2) starfsemi.

92
00:06:55,290 --> 00:07:01,590
Hins vegar raðað hluti lista ekki innihalda alla lista þar til enda.

93
00:07:01,590 --> 00:07:06,920
Samt gætum við hugsanlega setja inn nýja hluti í upphafi raðaða hluta

94
00:07:06,920 --> 00:07:09,320
á hverjum endurtekning á reiknirit,

95
00:07:09,320 --> 00:07:14,500
sem þýðir að við myndum þurfa að líta á hvert frumefni sem nú eru í raðaða hluta.

96
00:07:14,500 --> 00:07:20,090
Svo, sem þýðir að við gætum hugsanlega gera einn samanburð í annað frumefni,

97
00:07:20,090 --> 00:07:24,660
tveir samanburð þriðja frumefni, og svo framvegis.

98
00:07:24,660 --> 00:07:32,480
Svo heildarfjölda skref er summan af heiltölur frá 1 til lengd listanum mínus 1.

99
00:07:32,480 --> 00:07:35,240
Við getum táknað þetta með samantekt.

100
00:07:41,170 --> 00:07:47,270
>> Við munum ekki fara inn summations hér, en það kemur í ljós að þessi samantekt er jafnt

101
00:07:47,270 --> 00:07:57,900
n (n - 1) yfir 2, sem jafngildir N ^ 2/2 - N / 2.

102
00:07:57,900 --> 00:08:00,800
Þegar rætt er um asymptotic afturkreistingur,

103
00:08:00,800 --> 00:08:05,170
This N ^ 2 tíma er að fara að ráða þessa n tíma.

104
00:08:05,170 --> 00:08:11,430
Svo insertion sort er Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Hvað ef við hljóp insertion sort á þegar raðað lista.

106
00:08:16,150 --> 00:08:20,960
Í því tilviki, myndi við einfaldlega að byggja upp raðað hluta frá vinstri til hægri.

107
00:08:20,960 --> 00:08:25,050
Svo munum við bara þurfa á röð n skrefum.

108
00:08:25,050 --> 00:08:29,740
>> Það þýðir að insertion sort hefur best í frammistöðu n,

109
00:08:29,740 --> 00:08:34,130
sem við tákna með Ω (n).

110
00:08:34,130 --> 00:08:36,190
Og það er það fyrir Innsetningarröðun,

111
00:08:36,190 --> 00:08:40,429
bara einn af mörgum reiknirit sem við getum notað til að raða listanum.

112
00:08:40,429 --> 00:08:43,210
Mitt nafn er Tommy, og þetta er CS50.

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

114
00:08:46,110 --> 00:08:49,230
Ó, að þú getur ekki hætt að einu sinni byrjar það.

115
00:09:01,620 --> 00:09:04,760
Oh, gerði við það - >> Boom!