1
00:00:00,000 --> 00:00:02,826
>> [MUSIC SPILLE]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Så innsetting sort er en annen
algoritme vi kan bruke til å sortere en matrise.

4
00:00:09,370 --> 00:00:12,350
Ideen bak denne algoritmen
er å bygge din sorterte utvalg

5
00:00:12,350 --> 00:00:19,670
på plass, forskyvning av elementene
den måten som du går, for å gjøre plass.

6
00:00:19,670 --> 00:00:22,240
Dette er litt annerledes
fra utvalget sort eller boble

7
00:00:22,240 --> 00:00:25,460
slag, for eksempel, der
vi justere steder,

8
00:00:25,460 --> 00:00:26,910
hvor vi gjør bytteavtaler.

9
00:00:26,910 --> 00:00:29,760
>> I dette tilfellet hva vi faktisk
gjør er glideelementer

10
00:00:29,760 --> 00:00:31,390
over, ut av veien.

11
00:00:31,390 --> 00:00:34,030
Hvordan virker denne algoritmen
arbeide i pseudokode?

12
00:00:34,030 --> 00:00:37,646
Vel la oss bare vilkårlig si at
første element i matrisen er sortert.

13
00:00:37,646 --> 00:00:38,770
Vi bygger den på plass.

14
00:00:38,770 --> 00:00:42,660
>> Vi skal gå ett element om gangen og
bygge den, og så det første vi ser

15
00:00:42,660 --> 00:00:43,890
er et element av en matrise.

16
00:00:43,890 --> 00:00:47,720
Og per definisjon, en en
element tabellen er sortert.

17
00:00:47,720 --> 00:00:50,850
>> Så får vi gjenta denne prosessen until--
vi vil gjenta følgende prosess

18
00:00:50,850 --> 00:00:52,900
inntil alle elementene er sortert.

19
00:00:52,900 --> 00:00:57,770
Se på den neste usortert element og
sett det inn i den sorterte delen,

20
00:00:57,770 --> 00:01:01,209
ved å forskyve det nødvendige antall
av elementer ut av veien.

21
00:01:01,209 --> 00:01:03,750
Forhåpentligvis kan dette visualisering
vil hjelpe deg å se nøyaktig hva som er

22
00:01:03,750 --> 00:01:05,980
skjer med innsetting slag.

23
00:01:05,980 --> 00:01:08,010
>> Så igjen, her er vår
Hele usortert array,

24
00:01:08,010 --> 00:01:10,970
alle de elementer som er angitt i rødt.

25
00:01:10,970 --> 00:01:13,320
Og la oss følge
trinnene ved pseudokode.

26
00:01:13,320 --> 00:01:16,970
Det første vi gjør, er vi kaller
første element i matrisen, sortert.

27
00:01:16,970 --> 00:01:20,920
Så vi er bare skal si
five, du er nå sortert.

28
00:01:20,920 --> 00:01:24,570
>> Deretter ser vi på neste
usortert element i matrisen

29
00:01:24,570 --> 00:01:27,610
og vi ønsker å sette inn som
inn i den sorterte del,

30
00:01:27,610 --> 00:01:29,750
ved å flytte elementene over.

31
00:01:29,750 --> 00:01:33,470
Så to er neste usortert
element i matrisen.

32
00:01:33,470 --> 00:01:36,250
Klart det hører før
fem, så hva vi skal gjøre

33
00:01:36,250 --> 00:01:41,580
er liksom holde to til side for en andre,
skifte five over, og deretter sett i to

34
00:01:41,580 --> 00:01:43,210
før fem, hvor du skal gå.

35
00:01:43,210 --> 00:01:45,280
Og nå kan vi si at to er sortert.

36
00:01:45,280 --> 00:01:48,400
>> Så som du kan se, har vi bare så langt
sett på to elementer av matrisen.

37
00:01:48,400 --> 00:01:50,600
Vi har ikke sett på
hvile i det hele tatt, men vi har

38
00:01:50,600 --> 00:01:54,582
fikk disse to elementene sortert etter
hjelp av skiftemekanismen.

39
00:01:54,582 --> 00:01:56,410
>> Så vi gjenta prosessen på nytt.

40
00:01:56,410 --> 00:01:58,850
Se på den neste usortert
element, er at en.

41
00:01:58,850 --> 00:02:04,010
La oss holde det til side for en andre,
skifte alt over, og sette en

42
00:02:04,010 --> 00:02:05,570
hvor den skal gå.

43
00:02:05,570 --> 00:02:08,110
>> Igjen, fortsatt, har vi bare noen gang
så på en, to og fem.

44
00:02:08,110 --> 00:02:12,480
Vi vet ikke hva annet som kommer,
men vi har sortert disse tre elementene.

45
00:02:12,480 --> 00:02:16,030
>> Neste usortert element er
tre, så vi får sett den til side.

46
00:02:16,030 --> 00:02:18,200
Vi skal skifte over hva vi
må, som denne gang

47
00:02:18,200 --> 00:02:21,820
er ikke alt som i forrige
to tilfeller er det bare fem.

48
00:02:21,820 --> 00:02:25,440
Og så får vi holde oss tre i,
mellom to og fem.

49
00:02:25,440 --> 00:02:27,849
>> Seks er neste usortert
element til matrisen.

50
00:02:27,849 --> 00:02:31,140
Og i virkeligheten seks er større enn fem, så
vi trenger ikke engang å gjøre noe bytte.

51
00:02:31,140 --> 00:02:35,710
Vi kan bare tack seks rett på å
enden av sortert partiet.

52
00:02:35,710 --> 00:02:38,270
>> Endelig er fire den
siste usortert element.

53
00:02:38,270 --> 00:02:42,060
Så vi får sett den til side, skifte over
elementene vi trenger å skifte over,

54
00:02:42,060 --> 00:02:43,780
og deretter sette fire der det hører hjemme.

55
00:02:43,780 --> 00:02:46,400
Og nå ser, har vi liksom
av alle elementene.

56
00:02:46,400 --> 00:02:48,150
Legg merke til med innsetting
sortere, har vi ikke

57
00:02:48,150 --> 00:02:50,240
å gå frem og tilbake over rekken.

58
00:02:50,240 --> 00:02:54,720
Vi bare gikk over rekken
en gang, og vi flyttet ting

59
00:02:54,720 --> 00:02:59,870
at vi allerede hadde oppstått, for
å gjøre plass til de nye elementene.

60
00:02:59,870 --> 00:03:02,820
>> Så hva er det verste tilfellet
scenario med innsetting slag?

61
00:03:02,820 --> 00:03:05,090
I verste tilfelle,
matrise er i omvendt rekkefølge.

62
00:03:05,090 --> 00:03:11,180
Man må skifte hvert av de n elementene
opp til n stillinger, hver eneste gang vi

63
00:03:11,180 --> 00:03:12,880
gjøre en innsetting.

64
00:03:12,880 --> 00:03:15,720
Det er mye giring.

65
00:03:15,720 --> 00:03:18,014
>> I beste tilfelle er
matrise er perfekt sortert.

66
00:03:18,014 --> 00:03:20,680
Og liksom som hva som skjedde
med fem og seks i eksemplet

67
00:03:20,680 --> 00:03:23,779
der vi kunne bare tråkle den på
uten å måtte gjøre noe skiftende,

68
00:03:23,779 --> 00:03:24,820
vi skulle egentlig gjøre det.

69
00:03:24,820 --> 00:03:27,560
>> Hvis du forestille deg at vår
matrise var én til seks,

70
00:03:27,560 --> 00:03:29,900
Vi vil starte med å
erklære en er sortert.

71
00:03:29,900 --> 00:03:33,300
To kommer etter en slik at vi kan bare
sier, OK, vel en og to er sortert.

72
00:03:33,300 --> 00:03:36,190
Tre kommer etter to så, OK,
en og to og tre er sortert.

73
00:03:36,190 --> 00:03:39,590
>> Vi er ikke å gjøre noen bytteavtaler, vi er
bare å flytte denne vilkårlig linje

74
00:03:39,590 --> 00:03:42,460
mellom sortert og usortert mens vi går.

75
00:03:42,460 --> 00:03:46,646
Så effektivt som vi gjorde i eksempelet,
snu elementer blå, så vi fortsetter.

76
00:03:46,646 --> 00:03:48,270
Så hva er den verste fall runtime, da?

77
00:03:48,270 --> 00:03:51,854
Husk, hvis vi må skifte hver av
de n elementene muligens n posisjoner,

78
00:03:51,854 --> 00:03:54,020
forhåpentligvis som gir deg
en idé om at det verste tilfellet

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

80
00:03:57,770 --> 00:04:00,220
>> Hvis rekken er helt
sortert, alt vi har å gjøre

81
00:04:00,220 --> 00:04:04,480
er å se på hvert enkelt element
en gang, og så er vi ferdige.

82
00:04:04,480 --> 00:04:08,440
Så i beste fall, det er omega n.

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

84
00:04:09,490 --> 00:04:11,760
Dette er CS50.

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