1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Insertion Sorter]

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

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

4
00:00:07,290 --> 00:00:13,060
La oss ta en titt på innsetting sortere, en algoritme for å ta en liste med tall og sortere dem.

5
00:00:13,060 --> 00:00:18,300
En algoritme, husk, det er rett og slett en steg-for-trinn prosedyre for å oppnå en oppgave.

6
00:00:18,300 --> 00:00:23,640
Den grunnleggende ideen bak innsetting sortere, er å dele vår liste i to deler,

7
00:00:23,640 --> 00:00:26,580
en sortert del og en usortert del.

8
00:00:26,580 --> 00:00:29,290
>> På hvert trinn av algoritmen, er et nummer flyttes

9
00:00:29,290 --> 00:00:32,439
fra usorterte porsjon til den sorterte parti

10
00:00:32,439 --> 00:00:35,680
til slutt hele listen sorteres.

11
00:00:35,680 --> 00:00:43,340
Her er listen over seks usorterte tall - 23, 42, 4, 16, 8, og 15.

12
00:00:43,340 --> 00:00:47,680
Siden disse tallene er ikke alle i stigende rekkefølge, de unsorted.

13
00:00:47,680 --> 00:00:53,890
Siden vi ikke har begynt å sortere ennå, vil vi vurdere alle seks elementene vår usortert del.

14
00:00:53,890 --> 00:00:59,270
>> Når vi begynner å sortere, vil vi sette disse sortert tallene til venstre for disse.

15
00:00:59,270 --> 00:01:03,600
Så, la oss starte med 23, det første elementet i listen vår.

16
00:01:03,600 --> 00:01:06,930
Vi har ikke noen elementer i vår sortert del ennå,

17
00:01:06,930 --> 00:01:12,460
så la oss rett og slett vurdere 23 for å være starten og slutten av vår sortert del.

18
00:01:12,460 --> 00:01:16,510
Nå har vår sortert delen ett nummer, 23,

19
00:01:16,510 --> 00:01:20,260
og vår usortert del har disse fem tall.

20
00:01:20,260 --> 00:01:27,320
La oss nå sette inn neste nummer i vår usortert del, 42, inn i sorteres del.

21
00:01:27,320 --> 00:01:35,930
>> For å gjøre dette, må vi sammenligne den 42 til 23 - det eneste elementet i vår sortert del så langt.

22
00:01:35,930 --> 00:01:41,980
Førtito er større enn 23, så vi kan bare legge 42 til slutten

23
00:01:41,980 --> 00:01:45,420
av kildesortert parti av listen. Flott!

24
00:01:45,420 --> 00:01:51,850
Nå kan våre sorteres del har to elementer, og vår usortert del har fire elementer.

25
00:01:51,850 --> 00:01:57,200
Så, la oss nå flytte til 4, det neste elementet i usortert del.

26
00:01:57,200 --> 00:02:00,230
Så, bør der dette plasseres i den sorterte del?

27
00:02:00,230 --> 00:02:04,220
>> Husk, vi ønsker å plassere dette nummeret i sortert rekkefølge

28
00:02:04,220 --> 00:02:08,680
så vår sortert del forblir riktig sortert til alle tider.

29
00:02:08,680 --> 00:02:14,380
Hvis vi plasserer 4 til høyre for 42, så vår liste vil være ute av drift.

30
00:02:14,380 --> 00:02:18,380
Så, la oss fortsette å flytte høyre mot venstre i våre slags del.

31
00:02:18,380 --> 00:02:23,260
Når vi beveger oss, la oss skifte hvert nummer ned et sted å gjøre plass til det nye nummeret.

32
00:02:25,440 --> 00:02:31,740
Ok, er 4 også mindre enn 23, så vi kan ikke plassere det her heller.

33
00:02:31,740 --> 00:02:34,480
La oss flytte 23 rette sted.

34
00:02:36,500 --> 00:02:43,120
>> Det betyr at vi ønsker å plassere 4 inn det første sporet i den sorterte delen.

35
00:02:43,120 --> 00:02:46,300
Legg merke til hvordan denne plassen på listen var allerede tom,

36
00:02:46,300 --> 00:02:51,120
fordi vi har vært på vei sortert elementer ned som vi har møtt dem.

37
00:02:51,120 --> 00:02:52,740
OK. Så, vi halvveis.

38
00:02:52,740 --> 00:02:57,990
La oss videre vår algoritme ved å sette 16 inn den sorterte parti.

39
00:02:59,260 --> 00:03:03,820
Seksten er mindre enn 42, så la oss forskyve 42 til høyre.

40
00:03:05,700 --> 00:03:10,190
Seksten er også mindre enn 23, så la oss også skifte det elementet.

41
00:03:11,790 --> 00:03:20,820
>> Nå er 16 større enn 4. Så det ser ut som vi ønsker å sette inn 16 mellom 4 og 23.

42
00:03:20,820 --> 00:03:24,620
Mens flytte gjennom den sorterte parti av listen fra høyre mot venstre,

43
00:03:24,620 --> 00:03:29,160
4 er det første tallet vi har sett som er mindre enn antallet

44
00:03:29,160 --> 00:03:31,540
vi prøver å sette inn.

45
00:03:31,540 --> 00:03:35,820
Så nå kan vi sette inn 16 i denne tomme sporet,

46
00:03:35,820 --> 00:03:40,520
som, husk, vi har laget av bevegelige elementer i den slags del over

47
00:03:40,520 --> 00:03:43,340
som vi har møtt dem.

48
00:03:43,340 --> 00:03:47,900
>> OK. Nå har vi fire sortert elementer og to usorterte elementer.

49
00:03:47,900 --> 00:03:51,600
Så, la oss flytte åtte i den sorterte delen.

50
00:03:51,600 --> 00:03:55,010
Åtte er mindre enn 42.

51
00:03:55,010 --> 00:03:56,940
Åtte er mindre enn 23.

52
00:03:56,940 --> 00:04:00,230
Og 8 er mindre enn 16 år.

53
00:04:00,230 --> 00:04:03,110
Men 8 er større enn 4.

54
00:04:03,110 --> 00:04:07,280
Så vil vi gjerne sette åtte mellom 4 og 16 år.

55
00:04:09,070 --> 00:04:13,650
Og nå er det bare ett element til venstre for å sortere - den 15.

56
00:04:13,950 --> 00:04:16,589
Femten er mindre enn 42,

57
00:04:16,589 --> 00:04:19,130
Femten er mindre enn 23.

58
00:04:19,130 --> 00:04:21,750
Og 15 er mindre enn 16.

59
00:04:21,750 --> 00:04:24,810
Men 15 er større enn 8.

60
00:04:24,810 --> 00:04:27,440
>> Så, her er der vi ønsker å gjøre vårt endelige innsetting.

61
00:04:28,770 --> 00:04:30,330
Og vi er ferdige.

62
00:04:30,330 --> 00:04:33,540
Vi har ingen flere elementer i usortert del,

63
00:04:33,540 --> 00:04:36,670
og vår sortert delen er i riktig rekkefølge.

64
00:04:36,670 --> 00:04:40,270
Tallene er bestilt fra minste til største.

65
00:04:40,270 --> 00:04:44,330
Så, la oss ta en titt på noen pseudokode som beskriver hvilke tiltak vi bare utført.

66
00:04:46,760 --> 00:04:51,740
>> På linje 1, kan vi se at vi må iterere over hvert element i listen

67
00:04:51,740 --> 00:04:57,060
bortsett fra den første, vil siden det første elementet i usortert del rett og slett blitt

68
00:04:57,060 --> 00:05:00,220
det første elementet i den sorterte delen.

69
00:05:00,220 --> 00:05:06,320
På linjene 2 og 3, vi holde styr på vår nåværende plass i usortert del.

70
00:05:06,320 --> 00:05:10,450
Element representerer nummeret vi nå beveger seg inn i sortert del,

71
00:05:10,450 --> 00:05:15,600
og j representerer vår indeksen inn i usortert del.

72
00:05:15,600 --> 00:05:20,980
>> På linje 4, vi gjentar gjennom den sorterte delen fra høyre til venstre.

73
00:05:20,980 --> 00:05:26,010
Vi ønsker å stoppe iterating når elementet til venstre for vår nåværende posisjon

74
00:05:26,010 --> 00:05:30,050
er mindre enn elementet vi prøver å sette inn.

75
00:05:30,050 --> 00:05:35,600
På linje 5, vi flytter hvert element vi møter en plass til høyre.

76
00:05:35,600 --> 00:05:40,950
På den måten vil vi ha en klar plass til å sette inn når vi finner det første elementet

77
00:05:40,950 --> 00:05:44,080
mindre enn elementet vi flytte.

78
00:05:44,080 --> 00:05:50,800
På linje 6, vi oppdaterer vår mot å fortsette å bevege seg mot venstre gjennom den sorterte delen.

79
00:05:50,800 --> 00:05:56,860
Endelig, på linje 7, vi setter elementet inn i sorterte parti av listen.

80
00:05:56,860 --> 00:06:00,020
>> Vi vet at det er greit å sette på plass j,

81
00:06:00,020 --> 00:06:05,360
fordi vi allerede har flyttet element som pleide å være der en plass til høyre.

82
00:06:05,360 --> 00:06:09,460
Husk, vi beveger seg gjennom den sorterte delen fra høyre til venstre,

83
00:06:09,460 --> 00:06:13,960
men vi skal flytte gjennom usortert del fra venstre til høyre.

84
00:06:13,960 --> 00:06:19,090
OK. La oss nå ta en titt på hvor lenge kjører som algoritmen tok.

85
00:06:19,090 --> 00:06:25,300
Vi vil først stille spørsmålet hvor lang tid tar det for denne algoritmen til å kjøre i verste fall.

86
00:06:25,300 --> 00:06:29,040
Husker at vi representerer dette gangtid med Big O notasjon.

87
00:06:32,530 --> 00:06:38,500
For å sortere vår liste, vi måtte iterere over elementene i usortert del,

88
00:06:38,500 --> 00:06:43,430
og for hver av disse elementer, potensielt over alle elementer i den sorterte del.

89
00:06:43,430 --> 00:06:47,950
Intuitivt, dette høres ut som en O (n ^ 2) drift.

90
00:06:47,950 --> 00:06:51,840
>> Ser på pseudokode vår, har vi en løkke nestet inni en annen loop,

91
00:06:51,840 --> 00:06:55,290
som riktignok høres ut som en O (n ^ 2) drift.

92
00:06:55,290 --> 00:07:01,590
Men gjorde den sorterte delen av listen ikke inneholder hele listen helt til slutten.

93
00:07:01,590 --> 00:07:06,920
Likevel kunne vi potensielt sette et nytt element på begynnelsen av kildesortert del

94
00:07:06,920 --> 00:07:09,320
på hver iterasjon av algoritmen,

95
00:07:09,320 --> 00:07:14,500
noe som betyr at vi måtte se på hvert element for tiden i den sorterte delen.

96
00:07:14,500 --> 00:07:20,090
Slik, betyr at vi kan potensielt gjøre en sammenligning for det andre elementet,

97
00:07:20,090 --> 00:07:24,660
to sammenligninger for det tredje elementet, og så videre.

98
00:07:24,660 --> 00:07:32,480
Så, er det totale antall trinn summen av de hele tall fra 1 til lengden av listen minus 1.

99
00:07:32,480 --> 00:07:35,240
Vi kan representere dette med en summering.

100
00:07:41,170 --> 00:07:47,270
>> Vi vil ikke gå inn summeringer her, men det viser seg at dette summering er lik

101
00:07:47,270 --> 00:07:57,900
n (n - 1) i løpet 2, som er ekvivalent n ^ 2/2 - N / 2.

102
00:07:57,900 --> 00:08:00,800
Når man snakker om asymptotisk kjøretid,

103
00:08:00,800 --> 00:08:05,170
dette n ^ 2 sikt kommer til å dominere denne n sikt.

104
00:08:05,170 --> 00:08:11,430
Så, er innsetting slags Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Hva om vi kjørte innsetting sortere på en allerede sortert liste.

106
00:08:16,150 --> 00:08:20,960
I så fall, ville vi bare bygge opp den sorterte delen fra venstre til høyre.

107
00:08:20,960 --> 00:08:25,050
Så vil vi bare trenger i størrelsesorden n trinn.

108
00:08:25,050 --> 00:08:29,740
>> Det betyr at innsetting sorter har en beste fall ytelse av n,

109
00:08:29,740 --> 00:08:34,130
som vi representerer med Ω (n).

110
00:08:34,130 --> 00:08:36,190
Og det er det for innsetting sortere,

111
00:08:36,190 --> 00:08:40,429
bare ett av mange algoritmer vi kan bruke til å sortere en liste.

112
00:08:40,429 --> 00:08:43,210
Mitt navn er Tommy, og dette er CS50.

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

114
00:08:46,110 --> 00:08:49,230
Å, du bare ikke kan stoppe det når det begynner.

115
00:09:01,620 --> 00:09:04,760
Oh, vi gjorde det - >> Boom!