1
00:00:00,000 --> 00:00:02,826
>> [Predvaja glasba]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> Doug LLOYD: Torej vstavljanje vrsta je še ena
Algoritem lahko uporabimo za razvrščanje array.

4
00:00:09,370 --> 00:00:12,350
Ideja tega algoritma
je, da zgraditi vaš urejen niz

5
00:00:12,350 --> 00:00:19,670
V mestu, ki preusmerja elemente iz
tako kot greš, da bi naredili prostor.

6
00:00:19,670 --> 00:00:22,240
To je nekoliko drugačen
od izbora vrste ali mehurček

7
00:00:22,240 --> 00:00:25,460
sortiranje, na primer, kadar
smo prilagoditvi lokacije,

8
00:00:25,460 --> 00:00:26,910
kjer smo kar zamenjavami.

9
00:00:26,910 --> 00:00:29,760
>> V tem primeru, kaj smo pravzaprav
šel je drsni elementi

10
00:00:29,760 --> 00:00:31,390
konec, iz poti.

11
00:00:31,390 --> 00:00:34,030
Kako ta algoritem
delo v psevdokoda?

12
00:00:34,030 --> 00:00:37,646
No, kaj je samo arbitrarno pravijo, da je
Prvi element matrike je razvrščen.

13
00:00:37,646 --> 00:00:38,770
Mi smo jo gradi na mestu.

14
00:00:38,770 --> 00:00:42,660
>> Mi boš šel en element naenkrat in
graditi, zato je prva stvar, ki jo vidim

15
00:00:42,660 --> 00:00:43,890
je matrika ena element.

16
00:00:43,890 --> 00:00:47,720
In po definiciji, eno
element matrike je razvrščen.

17
00:00:47,720 --> 00:00:50,850
>> Potem bomo ta postopek ponovite until--
bomo ponovili naslednji postopek

18
00:00:50,850 --> 00:00:52,900
dokler so razporejene vse elemente.

19
00:00:52,900 --> 00:00:57,770
Poglej naslednjo nesortirani elementa in
ga vstavite v urejenem delu,

20
00:00:57,770 --> 00:01:01,209
s premikom zahtevanega števila
elementov iz poti.

21
00:01:01,209 --> 00:01:03,750
Upajmo, da to vizualizacija
vam bo pomagal videti, kaj je

22
00:01:03,750 --> 00:01:05,980
dogaja z vstavljanja vrste.

23
00:01:05,980 --> 00:01:08,010
>> Torej še enkrat, tu je naš
Celotna nesortirani matrika,

24
00:01:08,010 --> 00:01:10,970
vse elemente, navedene v rdeči barvi.

25
00:01:10,970 --> 00:01:13,320
In naj sledijo
koraki našega psevdokoda.

26
00:01:13,320 --> 00:01:16,970
Prva stvar, ki jo storite, se pravimo
Prvi element matrike, razporejene.

27
00:01:16,970 --> 00:01:20,920
Tako smo si samo hotel reči
pet, ste zdaj razporejene.

28
00:01:20,920 --> 00:01:24,570
>> Potem gledamo na naslednji
neprebrani element matrike

29
00:01:24,570 --> 00:01:27,610
in želimo, da vstavite da
v razvrščenih obrok,

30
00:01:27,610 --> 00:01:29,750
s premikanjem elementov konec.

31
00:01:29,750 --> 00:01:33,470
Torej, dva je naslednji neprebrani
element matrike.

32
00:01:33,470 --> 00:01:36,250
Jasno je, da pripada pred
pet, kaj bomo storili

33
00:01:36,250 --> 00:01:41,580
je nekako držite dve rezerviran za sekundo,
premik pet čez, in nato vstavite dva

34
00:01:41,580 --> 00:01:43,210
pred petimi, kjer bi morala iti.

35
00:01:43,210 --> 00:01:45,280
In zdaj lahko rečemo, da je dva razporejene.

36
00:01:45,280 --> 00:01:48,400
>> Torej, kot lahko vidite, smo samo tako daleč
pogledal na dveh elementih matrike.

37
00:01:48,400 --> 00:01:50,600
Nismo pogledal na
počitek na vse, vendar smo

38
00:01:50,600 --> 00:01:54,582
dobil ta dva elementa razporejene po
Tako mehanizma spreminjajočo.

39
00:01:54,582 --> 00:01:56,410
>> Tako smo še enkrat ponoviti postopek.

40
00:01:56,410 --> 00:01:58,850
Poglej naslednjo nerazvrščenih
element, ki je ena.

41
00:01:58,850 --> 00:02:04,010
Oglejmo presodilo, da na stran za sekundo,
premik vse več, in dal eno

42
00:02:04,010 --> 00:02:05,570
kjer bi morala iti.

43
00:02:05,570 --> 00:02:08,110
>> Again, vedno, smo jih le kdaj
pogledal na eno, dve, pet.

44
00:02:08,110 --> 00:02:12,480
Ne vemo, kaj prihaja,
vendar smo razporejene te tri elemente.

45
00:02:12,480 --> 00:02:16,030
>> Naslednji neprebrani element
tri, tako da bomo ga razveljavi.

46
00:02:16,030 --> 00:02:18,200
Bomo premik nad tem, kaj smo
morali ki tokrat

47
00:02:18,200 --> 00:02:21,820
ni vse tako kot v prejšnji
dva primera, to je samo pet.

48
00:02:21,820 --> 00:02:25,440
In potem bomo držijo tri v,
med dvema in petimi.

49
00:02:25,440 --> 00:02:27,849
>> Šest je naslednji neprebrani
element v matriki.

50
00:02:27,849 --> 00:02:31,140
In v resnici je šest večja od pet, tako
mi sploh ne potrebujete storiti vse swapping.

51
00:02:31,140 --> 00:02:35,710
Mi lahko samo prečenje šest desno na
Konec razvrščeni odseka.

52
00:02:35,710 --> 00:02:38,270
>> Končno, štiri je
zadnji neprebrani element.

53
00:02:38,270 --> 00:02:42,060
Torej ga bomo v prahi, premik preko
elemente moramo premik več,

54
00:02:42,060 --> 00:02:43,780
in nato dal štiri, kamor spada.

55
00:02:43,780 --> 00:02:46,400
In zdaj poglej, ki smo jih nekako
vseh elementov.

56
00:02:46,400 --> 00:02:48,150
Opazili z vstavljanjem
razvrščanje, nismo imeli

57
00:02:48,150 --> 00:02:50,240
iti naprej in nazaj po matriki.

58
00:02:50,240 --> 00:02:54,720
Smo šli samo čez polja
en čas, in smo premaknilo stvari

59
00:02:54,720 --> 00:02:59,870
da sva že srečali, da bi
da bi naredili prostor za nove elemente.

60
00:02:59,870 --> 00:03:02,820
>> Torej, kaj je v najslabšem primeru
Scenarij z vstavljanja vrste?

61
00:03:02,820 --> 00:03:05,090
V najslabšem primeru je
Niz je v obratnem vrstnem redu.

62
00:03:05,090 --> 00:03:11,180
Moraš premik vsakega izmed n elementov
do n položaje, vsak čas smo

63
00:03:11,180 --> 00:03:12,880
narediti vstavljanje.

64
00:03:12,880 --> 00:03:15,720
To je veliko premikajo.

65
00:03:15,720 --> 00:03:18,014
>> V najboljšem primeru
Niz je popolnoma urejeno.

66
00:03:18,014 --> 00:03:20,680
In nekaj podobnega kar se je zgodilo
s pet in šest ur na primer,

67
00:03:20,680 --> 00:03:23,779
kjer smo lahko samo prečenje
ne da bi morali storiti vse prestavljanje,

68
00:03:23,779 --> 00:03:24,820
sva v bistvu to.

69
00:03:24,820 --> 00:03:27,560
>> Če si predstavljate, da je naš
Niz je bil eden skozi šest,

70
00:03:27,560 --> 00:03:29,900
sva začnete z
razglasitvi eno je razvrščen.

71
00:03:29,900 --> 00:03:33,300
Dva pride po enega, tako da lahko samo
reči, OK, tudi ena in dve so razporejene.

72
00:03:33,300 --> 00:03:36,190
Tri pride po dveh tako, OK,
ena in dva in tri so razporejene.

73
00:03:36,190 --> 00:03:39,590
>> Mi ne podaja nobenih zamenjav, smo
Pravkar se gibljejo to samovoljno črto

74
00:03:39,590 --> 00:03:42,460
med razporejene in razvrščen kot gremo.

75
00:03:42,460 --> 00:03:46,646
Tako učinkovito, kot smo to storili v primeru,
obrača elemente, modra, saj bomo nadaljevali.

76
00:03:46,646 --> 00:03:48,270
Torej, kaj je v najslabšem primeru runtime, potem?

77
00:03:48,270 --> 00:03:51,854
Ne pozabite, če bomo morali preusmeriti vsako
je n elementov, ki bi n stališča,

78
00:03:51,854 --> 00:03:54,020
upajmo, da vam daje
ideja, ki v najslabšem primeru

79
00:03:54,020 --> 00:03:57,770
runtime je Big O n kvadrat.

80
00:03:57,770 --> 00:04:00,220
>> Če array je popolnoma
razporejene, vse, kar moramo storiti

81
00:04:00,220 --> 00:04:04,480
je pogled na vsak element
enkrat, nato pa smo končali.

82
00:04:04,480 --> 00:04:08,440
Torej v najboljšem primeru, da je omega n.

83
00:04:08,440 --> 00:04:09,490
>> Sem Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
To je CS50.

85
00:04:11,760 --> 00:04:13,119