1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Vstavi Razvrsti]

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

3
00:00:04,240 --> 00:00:07,290
[To je CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Oglejmo si uredi vstavljanja, algoritem za sprejemanje seznam številk in njihovo razvrščanje.

5
00:00:13,060 --> 00:00:18,300
Algoritem, se spomnite, je le korak-po-korak, postopek za dokončanje opravila.

6
00:00:18,300 --> 00:00:23,640
Osnovna ideja neke vstavljanja, je razdeliti naš seznam na dva dela,

7
00:00:23,640 --> 00:00:26,580
razporejene del in del razvrščeni.

8
00:00:26,580 --> 00:00:29,290
>> Na vsakem koraku algoritma je preselil številka

9
00:00:29,290 --> 00:00:32,439
od nesortiranih dela na razvrščeni del

10
00:00:32,439 --> 00:00:35,680
dokler na koncu je urejen celoten seznam.

11
00:00:35,680 --> 00:00:43,340
Tu je seznam šestih nesortiranih številkami - 23, 42, 4, 16, 8, in 15.

12
00:00:43,340 --> 00:00:47,680
Ker so te številke niso vsi v naraščajočem vrstnem redu, oni so nesortirani.

13
00:00:47,680 --> 00:00:53,890
Ker še nismo začeli sortiranje še, bomo upoštevali vseh šestih prvin našega neurejen del.

14
00:00:53,890 --> 00:00:59,270
>> Ko smo začeli sortiranje, bomo dal te številke razporejeni na levi strani teh.

15
00:00:59,270 --> 00:01:03,600
Torej, začnimo z 23, prvi element v našem seznamu.

16
00:01:03,600 --> 00:01:06,930
Nimamo nobenih elementov, razvrščenih v našem delu še

17
00:01:06,930 --> 00:01:12,460
tako da je le 23 menijo, da je začetek in konec našega razvrščene dela.

18
00:01:12,460 --> 00:01:16,510
Zdaj je naša razporejene del ima eno številko, 23,

19
00:01:16,510 --> 00:01:20,260
in naša neprebrani del je teh pet številk.

20
00:01:20,260 --> 00:01:27,320
Pojdimo zdaj vstavite naslednjo številko v naši nesortiranih del, 42, razvrščenih v delu.

21
00:01:27,320 --> 00:01:35,930
>> To storite tako, bomo morali primerjati od 42 do 23 - edini element našega dela razvrščenih doslej.

22
00:01:35,930 --> 00:01:41,980
Dvainštirideset je večja od 23, tako da lahko preprosto dodate 42 do konca

23
00:01:41,980 --> 00:01:45,420
na izločen del seznama. Čudovito!

24
00:01:45,420 --> 00:01:51,850
Sedaj naš razporejene del ima dva elementa, in naš razvrščeni del ima štiri elemente.

25
00:01:51,850 --> 00:01:57,200
Torej, kaj je zdaj premakniti na 4, naslednji element v nesortiranih dela.

26
00:01:57,200 --> 00:02:00,230
Zato je treba, kadar je to postaviti v razvrščenih dela?

27
00:02:00,230 --> 00:02:04,220
>> Ne pozabite, da želimo, da se to število v urejenih da

28
00:02:04,220 --> 00:02:08,680
tako da naše razporejene delež ostaja pravilno razporejene v vsakem trenutku.

29
00:02:08,680 --> 00:02:14,380
Če želimo postaviti na 4 na desni strani 42, potem bo naš seznam lahko v okvari.

30
00:02:14,380 --> 00:02:18,380
Torej, kaj je še premika od desne proti levi v naši razvrščanja dela.

31
00:02:18,380 --> 00:02:23,260
Kot smo se, kaj je premik navzdol vsako številko, kjer bi naredili prostor za novo številko.

32
00:02:25,440 --> 00:02:31,740
Ok, 4 je prav tako manj kot 23, tako da ga ne moremo postaviti niti tukaj.

33
00:02:31,740 --> 00:02:34,480
Naj premakniti 23 pravi eno mesto.

34
00:02:36,500 --> 00:02:43,120
>> To pomeni, da bi radi, da se da 4 v prvo režo na razvrščeni dela.

35
00:02:43,120 --> 00:02:46,300
Obvestilo o tem, kako ta prostor na seznamu je bil že prazen,

36
00:02:46,300 --> 00:02:51,120
ker smo bili razporejeni elementi gibljejo tako, kot smo jih srečal.

37
00:02:51,120 --> 00:02:52,740
V redu. Torej smo na pol poti.

38
00:02:52,740 --> 00:02:57,990
Naj nadaljujemo algoritem, ki ga vstavite v 16 razvrščenih dela.

39
00:02:59,260 --> 00:03:03,820
Šestnajst je manj kot 42, tako da je prehod 42-desno.

40
00:03:05,700 --> 00:03:10,190
Šestnajst je manj kot 23, tako da je tudi ta element premika.

41
00:03:11,790 --> 00:03:20,820
>> Zdaj, 16 je več kot 4. Torej, izgleda, da bi radi, da vstavite 16 med 4 in 23 let.

42
00:03:20,820 --> 00:03:24,620
Medtem ko se skozi izločen del seznama, od desne proti levi,

43
00:03:24,620 --> 00:03:29,160
4 je prva številka, ki smo jih videli, da je manjši od števila

44
00:03:29,160 --> 00:03:31,540
poskušamo vstaviti.

45
00:03:31,540 --> 00:03:35,820
Torej, zdaj bomo lahko vstavite 16 v to prazno režo,

46
00:03:35,820 --> 00:03:40,520
ki Zapomnite si, da smo ustvarili s premikanjem elementov v razvrščanja dela v

47
00:03:40,520 --> 00:03:43,340
kot smo jih srečal.

48
00:03:43,340 --> 00:03:47,900
>> V redu. Zdaj imamo štiri razporejeni elementi in 2 nesortirane elemente.

49
00:03:47,900 --> 00:03:51,600
Torej, kaj je premakniti 8 v razvrščenih dela.

50
00:03:51,600 --> 00:03:55,010
Osem je manj kot 42.

51
00:03:55,010 --> 00:03:56,940
Osem je manj kot 23.

52
00:03:56,940 --> 00:04:00,230
In 8 je manj kot 16.

53
00:04:00,230 --> 00:04:03,110
Ampak 8 je večja od 4.

54
00:04:03,110 --> 00:04:07,280
Torej, bi radi, da vstavite 8 med 4 in 16 let.

55
00:04:09,070 --> 00:04:13,650
In zdaj imamo samo eno levo element za razvrščanje - 15.

56
00:04:13,950 --> 00:04:16,589
Petnajst je manj kot 42,

57
00:04:16,589 --> 00:04:19,130
Petnajst manj kot 23.

58
00:04:19,130 --> 00:04:21,750
In 15 je manj kot 16.

59
00:04:21,750 --> 00:04:24,810
Ampak 15 je več kot 8.

60
00:04:24,810 --> 00:04:27,440
>> Torej, tukaj je, če želimo, da bo naš končni namestitev.

61
00:04:28,770 --> 00:04:30,330
In končamo.

62
00:04:30,330 --> 00:04:33,540
Nimamo več elementov v nesortiranih dela,

63
00:04:33,540 --> 00:04:36,670
in naš razporejene del je v pravilnem vrstnem redu.

64
00:04:36,670 --> 00:04:40,270
Številke so razvrščena od najmanjšega do največjega.

65
00:04:40,270 --> 00:04:44,330
Torej, vzemimo si nekaj psevdokod, ki opisuje ukrepe, sva izvedli.

66
00:04:46,760 --> 00:04:51,740
>> Na linijo 1, lahko vidimo, da bomo morali ponoviti čez vsak element na seznamu

67
00:04:51,740 --> 00:04:57,060
razen prvega, saj je prvi element v nesortiranih dela bodo preprosto postali

68
00:04:57,060 --> 00:05:00,220
Prvi element v razvrščenih dela.

69
00:05:00,220 --> 00:05:06,320
Na progah 2 in 3, smo sledenja naše sedanje mesto v nesortiranih dela.

70
00:05:06,320 --> 00:05:10,450
Element predstavlja število se trenutno gibljejo v razvrščeni dela,

71
00:05:10,450 --> 00:05:15,600
in j predstavlja naš indeks v nesortiranih dela.

72
00:05:15,600 --> 00:05:20,980
>> Na vrsti 4, smo ponavljanjem preko razvrščenih del od desne proti levi.

73
00:05:20,980 --> 00:05:26,010
Želimo ustaviti ponavljanjem, ko element na levi strani našega trenutnega položaja

74
00:05:26,010 --> 00:05:30,050
manj kot elementa, bomo poskušali vstaviti.

75
00:05:30,050 --> 00:05:35,600
V skladu 5, mi premikajo vsak element se srečamo eno mesto v desno.

76
00:05:35,600 --> 00:05:40,950
Na ta način bomo imeli prazen prostor za vstavitev v ko smo ugotovili, prvi del

77
00:05:40,950 --> 00:05:44,080
manj kot element selimo.

78
00:05:44,080 --> 00:05:50,800
Na vrsti 6, bomo posodobiti naš števec, bi se še naprej levo skozi razvrščene del.

79
00:05:50,800 --> 00:05:56,860
Končno na liniji 7, bomo vstavite element v izločen del seznama.

80
00:05:56,860 --> 00:06:00,020
>> Vemo, da je v redu, da vstavite j lega,

81
00:06:00,020 --> 00:06:05,360
ker smo se že preselili element, ki se uporablja za obstajal en prostor na desni.

82
00:06:05,360 --> 00:06:09,460
Ne pozabite, da smo se skozi izločen del od desne proti levi,

83
00:06:09,460 --> 00:06:13,960
vendar smo se skozi nesortiranih del leve proti desni.

84
00:06:13,960 --> 00:06:19,090
V redu. Pojdimo zdaj si oglejte, kako dolgo vožnjo, da je algoritem.

85
00:06:19,090 --> 00:06:25,300
Mi bomo najprej vprašati vprašanje, kako dolgo traja, da ta algoritem, da delujejo v najslabšem primeru.

86
00:06:25,300 --> 00:06:29,040
Spomnimo se, da smo predstavljajo ta čas delovanja z Big O zapisu.

87
00:06:32,530 --> 00:06:38,500
Za razvrščanje naš seznam, smo morali ponoviti čez elementov v nesortiranih dela,

88
00:06:38,500 --> 00:06:43,430
in za vsakega od teh elementov, lahko na vseh elementov razvrščenih dela.

89
00:06:43,430 --> 00:06:47,950
Intuitivno, to zveni kot O (n ^ 2) operacije.

90
00:06:47,950 --> 00:06:51,840
>> Če pogledamo na našem psevdokod, imamo zanko ugnezdena znotraj druge zanke,

91
00:06:51,840 --> 00:06:55,290
ki dejansko zveni kot O (n ^ 2) operacije.

92
00:06:55,290 --> 00:07:01,590
Vendar pa je razvrščenih del seznama ne vsebuje celoten seznam do konca.

93
00:07:01,590 --> 00:07:06,920
Kljub temu pa bi lahko potencialno vstaviti nov element na samem začetku razvrščeni dela

94
00:07:06,920 --> 00:07:09,320
na vsaki ponovitvi algoritem,

95
00:07:09,320 --> 00:07:14,500
kar pomeni, da bomo morali gledati na vsak element, ki je trenutno v razvrščenih dela.

96
00:07:14,500 --> 00:07:20,090
Torej, to pomeni, da bi lahko naredili eno primerjavo za drugi element,

97
00:07:20,090 --> 00:07:24,660
2 primerjave za tretji element, in tako naprej.

98
00:07:24,660 --> 00:07:32,480
Tako se je skupno število korakov, je vsota števil od 1 do dolžine seznama minus 1.

99
00:07:32,480 --> 00:07:35,240
Mi lahko predstavlja to s seštevanjem.

100
00:07:41,170 --> 00:07:47,270
>> Mi ne bo šel v summations tukaj, vendar se je izkazalo, da je ta vsota enaka

101
00:07:47,270 --> 00:07:57,900
n (n - 1) več kot 2, kar je enako n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Ko govorimo o asimptotične runtime,

103
00:08:00,800 --> 00:08:05,170
To n ^ 2 Izraz se bo prevladovala ta izraz n.

104
00:08:05,170 --> 00:08:11,430
Torej, vstavljanje vrsta je Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Kaj, če bi tekel za vstavljanje vrste na že sortirane seznama.

106
00:08:16,150 --> 00:08:20,960
V tem primeru, bi enostavno vzpostaviti urejen del od leve proti desni.

107
00:08:20,960 --> 00:08:25,050
Torej se bomo morali le na vrstni red korakov n.

108
00:08:25,050 --> 00:08:29,740
>> To pomeni, da je vključitev vrsta ima najboljšem primeru uspešnosti n,

109
00:08:29,740 --> 00:08:34,130
ki jih zastopa v Ω (n).

110
00:08:34,130 --> 00:08:36,190
In to je to za razvrščanje vstavljanja,

111
00:08:36,190 --> 00:08:40,429
Samo lahko eden od mnogih algoritmov, ki jih uporabljamo za razvrščanje seznama.

112
00:08:40,429 --> 00:08:43,210
Moje ime je Tommy, in to je CS50.

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

114
00:08:46,110 --> 00:08:49,230
Oh, si ne more ustaviti, da, ko se začne.

115
00:09:01,620 --> 00:09:04,760
Oh, res je, da je - >> Boom!