1
00:00:00,000 --> 00:00:02,826
>> [Muusika mängib]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Nii sisestamise sorteerida on teise
algoritmi saame kasutada sortida massiivi.

4
00:00:09,370 --> 00:00:12,350
Mõte algoritm
on ehitada oma sorteeritud massiiv

5
00:00:12,350 --> 00:00:19,670
kohale, minnes elemendid välja
Muide, kui sa lähed, et teha ruumi.

6
00:00:19,670 --> 00:00:22,240
See on mõnevõrra erinev
valikust omamoodi või mull

7
00:00:22,240 --> 00:00:25,460
sorteerida, näiteks siis, kui
me reguleerides kohtades,

8
00:00:25,460 --> 00:00:26,910
kus me teeme vahetustehinguid.

9
00:00:26,910 --> 00:00:29,760
>> Sel juhul, mida me tegelikult
tehes on liugelemendid

10
00:00:29,760 --> 00:00:31,390
üle, välja viis.

11
00:00:31,390 --> 00:00:34,030
Kuidas see algoritm
töötada pseudokoodi?

12
00:00:34,030 --> 00:00:37,646
Noh olgem lihtsalt suvaliselt öelda, et
Esimene osa massiiv on järjestatud.

13
00:00:37,646 --> 00:00:38,770
Me arendame oma kohale.

14
00:00:38,770 --> 00:00:42,660
>> Me läheme ühe elemendi korraga ja
ehitada, ja nii esimene asi, mida me näha

15
00:00:42,660 --> 00:00:43,890
on üks element massiivi.

16
00:00:43,890 --> 00:00:47,720
Ja definitsiooni järgi üks
element massiivi on järjestatud.

17
00:00:47,720 --> 00:00:50,850
>> Siis me korrata seda protsessi until--
me korrata järgmise protsessi

18
00:00:50,850 --> 00:00:52,900
kuni kõik elemendid on järjestatud.

19
00:00:52,900 --> 00:00:57,770
Vaata järgmise sorteerimata element ja
pistke see sorteeritud osa,

20
00:00:57,770 --> 00:01:01,209
minnes vajalik arv
elementide välja viis.

21
00:01:01,209 --> 00:01:03,750
Loodetavasti see visualiseerimine
aitab teil näha, millised täpselt on

22
00:01:03,750 --> 00:01:05,980
toimub koos sisestamise omamoodi.

23
00:01:05,980 --> 00:01:08,010
>> Nii jälle, siin on meie
Kogu sorteerimata massiiv,

24
00:01:08,010 --> 00:01:10,970
kõik elemendid punasega märgitud.

25
00:01:10,970 --> 00:01:13,320
Ja olgem järgi
etappe meie pseudokoodi.

26
00:01:13,320 --> 00:01:16,970
Esimene asi, mida me teeme, on me nimetame
Esimene element massiivi, järjestatud.

27
00:01:16,970 --> 00:01:20,920
Nii et me lihtsalt ütled
viis, sa oled nüüd järjestatud.

28
00:01:20,920 --> 00:01:24,570
>> Siis me vaatame järgmise
sorteerimata element massiivi

29
00:01:24,570 --> 00:01:27,610
ja me tahame lisada, et
arvesse järjestatud osa,

30
00:01:27,610 --> 00:01:29,750
nihutades elementide üle.

31
00:01:29,750 --> 00:01:33,470
Nii kahe on järgmine sortimata
element massiivi.

32
00:01:33,470 --> 00:01:36,250
On selge see kuulub enne
viis, nii et mida me teeme

33
00:01:36,250 --> 00:01:41,580
on omamoodi hoidke kaks kõrvale teise,
vahetustega viis üle ja seejärel sisestage kaks

34
00:01:41,580 --> 00:01:43,210
enne viit, kuhu peaks minema.

35
00:01:43,210 --> 00:01:45,280
Ja nüüd võib öelda, et kaks on järjestatud.

36
00:01:45,280 --> 00:01:48,400
>> Nii et nagu näete, me oleme ainult seni
vaatasin kaks elementi massiivi.

37
00:01:48,400 --> 00:01:50,600
Me ei ole vaadanud
puhata üldse, kuid me oleme

38
00:01:50,600 --> 00:01:54,582
sain need kaks elementi järjestatud vastavalt
teed käiguvahetusmehhanism.

39
00:01:54,582 --> 00:01:56,410
>> Nii me korrata protsessi uuesti.

40
00:01:56,410 --> 00:01:58,850
Vaata järgmise sorteerimata
element, mis on üks.

41
00:01:58,850 --> 00:02:04,010
Olgem hoida, et kõrvale teise,
suhtumist kõigesse üle ja panid ühe

42
00:02:04,010 --> 00:02:05,570
kus see peaks minema.

43
00:02:05,570 --> 00:02:08,110
>> Jällegi, ikka oleme alles kunagi
vaadeldi üks, kaks, ja viis.

44
00:02:08,110 --> 00:02:12,480
Me ei tea, mida veel on tulemas,
kuid me oleme järjestatud need kolm elementi.

45
00:02:12,480 --> 00:02:16,030
>> Järgmine sorteerimata element on
kolm, nii me pange kõrvale.

46
00:02:16,030 --> 00:02:18,200
Me minema üle, mida me
vaja mis seekord

47
00:02:18,200 --> 00:02:21,820
ei ole kõik nagu eelmistes
Kahel juhul on see lihtsalt viis.

48
00:02:21,820 --> 00:02:25,440
Ja siis me kinni kolm,
Kahe ja viie.

49
00:02:25,440 --> 00:02:27,849
>> Kuus on järgmine sorteerimata
element massiivi.

50
00:02:27,849 --> 00:02:31,140
Ja tegelikult kuue on rohkem kui viis, nii
me isegi ei pea tegema muud vahetada.

51
00:02:31,140 --> 00:02:35,710
Me lihtsalt pühitakse kuus õigus edasi
lõppu järjestatud portsjonina.

52
00:02:35,710 --> 00:02:38,270
>> Lõpuks nelja on
viimase sorteerimata element.

53
00:02:38,270 --> 00:02:42,060
Nii me pange kõrvale, vajub
elemendid peame minema üle,

54
00:02:42,060 --> 00:02:43,780
ja siis pane neli kuhu see kuulub.

55
00:02:43,780 --> 00:02:46,400
Ja nüüd vaatame, me oleme omamoodi
kõiki elemente.

56
00:02:46,400 --> 00:02:48,150
Märka sisestamisega
sorteerida, meil ei olnud

57
00:02:48,150 --> 00:02:50,240
minna edasi-tagasi üle massiivi.

58
00:02:50,240 --> 00:02:54,720
Me ainult läks kogu massiivi
üks kord, ja me nihkunud asjad

59
00:02:54,720 --> 00:02:59,870
et me tahaks juba tekkinud, et
et teha ruumi uutele elementidele.

60
00:02:59,870 --> 00:03:02,820
>> Mis siis halvimal juhul
stsenaarium sisestamise omamoodi?

61
00:03:02,820 --> 00:03:05,090
Halvimal juhul
massiiv on vastupidises järjekorras.

62
00:03:05,090 --> 00:03:11,180
Sa pead minema iga n elemendid
kuni n seisukohti, iga kord, kui me

63
00:03:11,180 --> 00:03:12,880
teha sisestamist.

64
00:03:12,880 --> 00:03:15,720
See on palju nihutada.

65
00:03:15,720 --> 00:03:18,014
>> Parimal juhul
massiiv on täiesti järjestatud.

66
00:03:18,014 --> 00:03:20,680
Ja omamoodi nagu juhtus
viie ning kuus näiteks

67
00:03:20,680 --> 00:03:23,779
kus me võiks lihtsalt pühitakse see
ilma teha käikudes,

68
00:03:23,779 --> 00:03:24,820
olime sisuliselt seda teha.

69
00:03:24,820 --> 00:03:27,560
>> Kui te kujutate ette, et meie
massiiv oli üks läbi kuue,

70
00:03:27,560 --> 00:03:29,900
olime alustad
kuulutatakse üks on järjestatud.

71
00:03:29,900 --> 00:03:33,300
Kaks on pärast üht nii saame lihtsalt
öelda, OK, samuti üks ja kaks on järjestatud.

72
00:03:33,300 --> 00:03:36,190
Kolm tuleb pärast kaht nii, OK,
üks ja kaks ja kolm on järjestatud.

73
00:03:36,190 --> 00:03:39,590
>> Me ei anna mingit vahetustehingud, me oleme
lihtsalt liigub selle suvalise rea

74
00:03:39,590 --> 00:03:42,460
vahel sorteeritud ja sorteerimata nagu me minna.

75
00:03:42,460 --> 00:03:46,646
Nii tõhusalt kui me tegime näiteks
keerates elemendid sinine, kui astume.

76
00:03:46,646 --> 00:03:48,270
Mis siis halvimal juhul runtime, siis?

77
00:03:48,270 --> 00:03:51,854
Pea meeles, kui me peame minema iga
n võimalikest n seisukohti,

78
00:03:51,854 --> 00:03:54,020
loodetavasti see annab teile
idee, et halvimal juhul

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

80
00:03:57,770 --> 00:04:00,220
>> Kui massiiv on täiesti
sorteeritud, kõik me peame tegema

81
00:04:00,220 --> 00:04:04,480
on vaadata iga element
kord, ja siis me teinud.

82
00:04:04,480 --> 00:04:08,440
Nii et parimal juhul on omega n.

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

84
00:04:09,490 --> 00:04:11,760
See on CS50.

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