1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Indsættelse 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
Lad os tage et kig på indsættelse slags, en algoritme til at tage en liste over numre og sortere dem.

5
00:00:13,060 --> 00:00:18,300
En algoritme, husk, er simpelthen en trin-for-trin procedure for opstilling af en opgave.

6
00:00:18,300 --> 00:00:23,640
Den grundlæggende idé bag indsættelse slags, er at opdele vores liste i to dele,

7
00:00:23,640 --> 00:00:26,580
en sorteret del og en usorteret portion.

8
00:00:26,580 --> 00:00:29,290
>> På hvert trin af algoritmen er en række flyttet

9
00:00:29,290 --> 00:00:32,439
fra usorteret del til den sorterede portion

10
00:00:32,439 --> 00:00:35,680
indtil sidst hele listen er sorteret.

11
00:00:35,680 --> 00:00:43,340
Her er listen af ​​seks usorterede numre - 23, 42, 4, 16, 8 og 15.

12
00:00:43,340 --> 00:00:47,680
Da disse tal ikke er alle i stigende rækkefølge, de er usorteret.

13
00:00:47,680 --> 00:00:53,890
Da vi ikke er begyndt sortering endnu, vil vi overveje alle seks elementer vores usorteret portion.

14
00:00:53,890 --> 00:00:59,270
>> Når vi begynder sortering, vil vi sætte disse sorteret numre til venstre for disse.

15
00:00:59,270 --> 00:01:03,600
Så lad os starte med 23, det første element i vores liste.

16
00:01:03,600 --> 00:01:06,930
Vi har ikke nogen elementer i vores sorteret del endnu,

17
00:01:06,930 --> 00:01:12,460
så lad os blot overveje 23 være begyndelsen og slutningen af ​​vores sorteret portion.

18
00:01:12,460 --> 00:01:16,510
Nu er vores sorteret del har ét nummer, 23,

19
00:01:16,510 --> 00:01:20,260
og vores usorteret del har disse fem numre.

20
00:01:20,260 --> 00:01:27,320
Lad os nu indsætte det næste nummer i vores usorterede portion, 42, ind i den sorterede del.

21
00:01:27,320 --> 00:01:35,930
>> For at gøre dette, vil vi nødt til at sammenligne den 42 til 23 - det eneste element i vores sorterede portion hidtil.

22
00:01:35,930 --> 00:01:41,980
Fyrre-to er større end 23, så vi kan blot tilføje 42 til enden

23
00:01:41,980 --> 00:01:45,420
Den sorterede portion af listen. Great!

24
00:01:45,420 --> 00:01:51,850
Nu er vores sorteres del har to elementer, og vores usorteret del har fire elementer.

25
00:01:51,850 --> 00:01:57,200
Så lad os nu gå videre til 4, det næste element i den usorterede del.

26
00:01:57,200 --> 00:02:00,230
Så bør hvor det placeres i den sorterede portion?

27
00:02:00,230 --> 00:02:04,220
>> Husk, vi ønsker at placere dette nummer i sorteret orden

28
00:02:04,220 --> 00:02:08,680
så vores sorteret del forbliver korrekt sorteret på alle tidspunkter.

29
00:02:08,680 --> 00:02:14,380
Hvis vi placerer 4 til højre for 42, så vores liste vil være ude af drift.

30
00:02:14,380 --> 00:02:18,380
Så lad os fortsætte med at bevæge højre mod venstre i vores slags portion.

31
00:02:18,380 --> 00:02:23,260
Som vi bevæger os, lad os flytte hvert nummer ned et sted at gøre plads til det nye nummer.

32
00:02:25,440 --> 00:02:31,740
Okay, 4 er også mindre end 23, så vi kan ikke placere den her heller.

33
00:02:31,740 --> 00:02:34,480
Lad os flytte den 23 rigtige sted.

34
00:02:36,500 --> 00:02:43,120
>> Det betyder, at vi gerne vil placere 4 i den første slot i den sorterede del.

35
00:02:43,120 --> 00:02:46,300
Bemærk hvordan denne plads på listen allerede var tom,

36
00:02:46,300 --> 00:02:51,120
fordi vi har været i bevægelse sorteret elementer ned som vi har mødt dem.

37
00:02:51,120 --> 00:02:52,740
Ok. Så vi er halvvejs.

38
00:02:52,740 --> 00:02:57,990
Lad os fortsætte vores algoritme ved at sætte 16 ind i sorterede portion.

39
00:02:59,260 --> 00:03:03,820
Seksten er mindre end 42, så lad os flytte 42 til højre.

40
00:03:05,700 --> 00:03:10,190
Seksten er også mindre end 23, så lad os også skifte dette element.

41
00:03:11,790 --> 00:03:20,820
>> Nu, 16 er større end fire. Så det ser ud som vi gerne vil indsætte 16 mellem 4 og 23.

42
00:03:20,820 --> 00:03:24,620
Samtidig bevæger sig gennem sorteret del af listen fra højre mod venstre,

43
00:03:24,620 --> 00:03:29,160
4 er det første tal, vi har set, at der er mindre end det antal,

44
00:03:29,160 --> 00:03:31,540
vi forsøger at indsætte.

45
00:03:31,540 --> 00:03:35,820
Så nu kan vi indsætte de 16 i denne tomme slot,

46
00:03:35,820 --> 00:03:40,520
der, husk, har vi skabt ved at flytte elementer i den slags del over

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

48
00:03:43,340 --> 00:03:47,900
>> Ok. Nu har vi fire sorteret elementer og to usorterede elementer.

49
00:03:47,900 --> 00:03:51,600
Så lad os flytte 8 i den sorterede del.

50
00:03:51,600 --> 00:03:55,010
Otte er mindre end 42.

51
00:03:55,010 --> 00:03:56,940
Otte er under 23.

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

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

54
00:04:03,110 --> 00:04:07,280
Så vil vi gerne indsætte 8 mellem 4 og 16.

55
00:04:09,070 --> 00:04:13,650
Og nu har vi bare have én mere tilbage element til at sortere - de 15.

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

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

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

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

60
00:04:24,810 --> 00:04:27,440
>> Så her er, hvor vi ønsker at gøre vores endelige indsættelse.

61
00:04:28,770 --> 00:04:30,330
Og vi er færdige.

62
00:04:30,330 --> 00:04:33,540
Vi har ikke flere elementer i den usorterede del,

63
00:04:33,540 --> 00:04:36,670
og vores sorteres del er i den rigtige rækkefølge.

64
00:04:36,670 --> 00:04:40,270
Numrene bestilles fra den mindste til den største.

65
00:04:40,270 --> 00:04:44,330
Så lad os tage et kig på nogle pseudokode, der beskriver de skridt, vi har lige udført.

66
00:04:46,760 --> 00:04:51,740
>> På linie 1, kan vi se, at vi bliver nødt til at gentage over hvert element i listen

67
00:04:51,740 --> 00:04:57,060
undtagelse af den første, vil siden det første element i den usorterede del simpelthen blive

68
00:04:57,060 --> 00:05:00,220
det første element i den sorterede del.

69
00:05:00,220 --> 00:05:06,320
På linjer 2 og 3, vi holde styr på vores nuværende plads i usorterede del.

70
00:05:06,320 --> 00:05:10,450
Element repræsenterer antallet vi i øjeblikket bevæger sig ind i den sorterede portion,

71
00:05:10,450 --> 00:05:15,600
og j repræsenterer vores indeks i usorteret portion.

72
00:05:15,600 --> 00:05:20,980
>> På linje 4, vi iteration gennem den sorterede del fra højre mod venstre.

73
00:05:20,980 --> 00:05:26,010
Vi ønsker at holde op med iteration, når elementet til venstre for vores nuværende position

74
00:05:26,010 --> 00:05:30,050
er mindre end det element, vi forsøger at indsætte.

75
00:05:30,050 --> 00:05:35,600
I linje 5, vi flytte hvert element møder vi en plads til højre.

76
00:05:35,600 --> 00:05:40,950
På den måde, vil vi have en klar plads til at indsætte ind i, når vi finder det første element

77
00:05:40,950 --> 00:05:44,080
mindre end det element, vi flytter.

78
00:05:44,080 --> 00:05:50,800
I linje 6, opdaterer vi vores tæller fortsat at flytte til venstre gennem den sorterede del.

79
00:05:50,800 --> 00:05:56,860
Endelig, på linje 7, vi isætningen af ​​elementet i den sorterede del af listen.

80
00:05:56,860 --> 00:06:00,020
>> Vi ved, at det er ok at indsætte i position j,

81
00:06:00,020 --> 00:06:05,360
fordi vi allerede har flyttet det element, der bruges til at være der en plads til højre.

82
00:06:05,360 --> 00:06:09,460
Husk, vi bevæger sig gennem den sorterede del fra højre til venstre,

83
00:06:09,460 --> 00:06:13,960
men vi flytter gennem den usorterede del fra venstre til højre.

84
00:06:13,960 --> 00:06:19,090
Ok. Lad os nu tage et kig på, hvor lang tid kørende, algoritme tog.

85
00:06:19,090 --> 00:06:25,300
Vi vil først spørge, hvor lang tid tager det for denne algoritme til at køre i værste fald.

86
00:06:25,300 --> 00:06:29,040
Husk på, at vi repræsenterer dette køretid med Big O notation.

87
00:06:32,530 --> 00:06:38,500
For at sortere vores liste, vi havde til at gentage over elementerne i den usorterede del,

88
00:06:38,500 --> 00:06:43,430
og for hver af disse bestanddele, eventuelt over alle elementer i den sorterede portion.

89
00:06:43,430 --> 00:06:47,950
Intuitivt dette lyder som en O (n ^ 2) operation.

90
00:06:47,950 --> 00:06:51,840
>> Ser man på vores pseudokode, har vi en løkke indlejret i en anden sløjfe,

91
00:06:51,840 --> 00:06:55,290
som, ja, lyder som en O (n ^ 2) operation.

92
00:06:55,290 --> 00:07:01,590
Men den sorterede del af listen ikke indeholder hele listen, indtil den bitre ende.

93
00:07:01,590 --> 00:07:06,920
Alligevel kunne vi potentielt indsætte et nyt element i begyndelsen af ​​det sorterede portion

94
00:07:06,920 --> 00:07:09,320
på hver iteration af algoritmen,

95
00:07:09,320 --> 00:07:14,500
hvilket betyder, at vi er nødt til at se på hvert element i øjeblikket i den sorterede del.

96
00:07:14,500 --> 00:07:20,090
Så det betyder, at vi potentielt kunne gøre en sammenligning for det andet element,

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

98
00:07:24,660 --> 00:07:32,480
Så er det samlede antal af trin er summen af ​​de hele tal fra 1 til længden af ​​listen minus 1.

99
00:07:32,480 --> 00:07:35,240
Vi kan repræsentere dette med en summation.

100
00:07:41,170 --> 00:07:47,270
>> Vi vil ikke gå ind i summationer her, men det viser sig, at denne summation er lig med

101
00:07:47,270 --> 00:07:57,900
n (n - 1) over 2, hvilket er ækvivalent n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Når vi taler om asymptotisk runtime,

103
00:08:00,800 --> 00:08:05,170
denne n ^ 2 udtryk kommer til at dominere denne n sigt.

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

105
00:08:11,430 --> 00:08:16,150
Hvad hvis vi løb indsættelse slags på en allerede sorteret liste.

106
00:08:16,150 --> 00:08:20,960
I dette tilfælde ville vi blot opbygge det sorterede portion fra venstre mod højre.

107
00:08:20,960 --> 00:08:25,050
Så vi behøver kun i størrelsesordenen n trin.

108
00:08:25,050 --> 00:08:29,740
>> Det betyder, at insertion art har en bedst tænkelige ydeevne n,

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

110
00:08:34,130 --> 00:08:36,190
Og det er det for indsættelse slags,

111
00:08:36,190 --> 00:08:40,429
blot én af de mange algoritmer, vi kan bruge til at sortere en liste.

112
00:08:40,429 --> 00:08:43,210
Mit 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
Åh, du kan bare ikke stoppe, at når den starter.

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