1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Invoeging Sorteren]

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

3
00:00:04,240 --> 00:00:07,290
[Dit is CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Laten we eens een kijkje nemen op insertion sort, een algoritme voor het nemen van een lijst van nummers en ze te sorteren.

5
00:00:13,060 --> 00:00:18,300
Een algoritme onthouden is gewoon een stap-voor-stap procedure voor het bereiken van een taak.

6
00:00:18,300 --> 00:00:23,640
Het basisidee achter insertion sort, is om onze lijst te verdelen in twee delen,

7
00:00:23,640 --> 00:00:26,580
een gesorteerd deel en een ongesorteerd deel.

8
00:00:26,580 --> 00:00:29,290
>> Bij elke stap van het algoritme wordt een aantal bewogen

9
00:00:29,290 --> 00:00:32,439
van het ongesorteerde deel naar het gedeelte gesorteerd

10
00:00:32,439 --> 00:00:35,680
totdat uiteindelijk de gehele lijst is gesorteerd.

11
00:00:35,680 --> 00:00:43,340
Hier is de lijst van zes ongesorteerde getallen - 23, 42, 4, 16, 8 en 15.

12
00:00:43,340 --> 00:00:47,680
Aangezien deze nummers zijn niet allemaal in oplopende volgorde, ze gesorteerd.

13
00:00:47,680 --> 00:00:53,890
Aangezien wij nog niet begonnen sorteren nog, zullen we rekening houden met alle zes elementen onze ongesorteerde deel.

14
00:00:53,890 --> 00:00:59,270
>> Zodra we beginnen met het sorteren, zullen we deze gesorteerd getallen aan de linkerkant van deze.

15
00:00:59,270 --> 00:01:03,600
Dus, laten we beginnen met 23, het eerste element in onze lijst.

16
00:01:03,600 --> 00:01:06,930
Wij hebben nog geen elementen in ons gesorteerd gedeelte,

17
00:01:06,930 --> 00:01:12,460
dus laten we gewoon 23 overwegen om het begin en het einde van onze gesorteerd deel zijn.

18
00:01:12,460 --> 00:01:16,510
Nu, onze gesorteerd deel heeft een nummer, 23,

19
00:01:16,510 --> 00:01:20,260
en onze ongesorteerde deel heeft deze vijf nummers.

20
00:01:20,260 --> 00:01:27,320
Laten we nu het volgende nummer in te voegen in onze ongesorteerd deel, 42, in de gesorteerde gedeelte.

21
00:01:27,320 --> 00:01:35,930
>> Om dit te doen, zullen we moeten de 42 te vergelijken met de 23 - het enige element in onze gesorteerd deel tot nu toe.

22
00:01:35,930 --> 00:01:41,980
Tweeënveertig groter is dan 23, dus we kunnen alleen maar 42 toevoegen aan het einde

23
00:01:41,980 --> 00:01:45,420
van de gesorteerde deel van de lijst. Geweldig!

24
00:01:45,420 --> 00:01:51,850
Nu onze gesorteerd gedeelte bestaat uit twee elementen, en onze ongesorteerde deel heeft vier elementen.

25
00:01:51,850 --> 00:01:57,200
Dus, laten we nu naar de 4, het volgende element in de ongesorteerde deel.

26
00:01:57,200 --> 00:02:00,230
Ja, waar deze worden geplaatst in de gesorteerde gedeelte?

27
00:02:00,230 --> 00:02:04,220
>> Vergeet niet, we willen dit aantal plaatsen in gesorteerde volgorde

28
00:02:04,220 --> 00:02:08,680
zodat onze gesorteerd gedeelte blijft correct gesorteerd te allen tijde.

29
00:02:08,680 --> 00:02:14,380
Als we de vier aan de rechterkant van de 42, dan is onze lijst zal worden van de orde.

30
00:02:14,380 --> 00:02:18,380
Dus, laten we verder naar rechts te verplaatsen naar links in onze sorteren gedeelte.

31
00:02:18,380 --> 00:02:23,260
Als we bewegen, laten we elk nummer terug te schakelen een plek om ruimte te maken voor het nieuwe nummer.

32
00:02:25,440 --> 00:02:31,740
Oke, 4 is ook minder dan 23, dus we kunnen niet hier plaatsen het ook niet.

33
00:02:31,740 --> 00:02:34,480
We gaan de 23 juiste plaats.

34
00:02:36,500 --> 00:02:43,120
>> Dat betekent dat we graag de 4 plaatsen in de eerste sleuf in de gesorteerde gedeelte.

35
00:02:43,120 --> 00:02:46,300
Merk op hoe deze ruimte in de lijst al leeg was,

36
00:02:46,300 --> 00:02:51,120
omdat we al bewegende gesorteerd elementen zijn als we ooit ontmoet ze.

37
00:02:51,120 --> 00:02:52,740
Oke. Dus, we zijn halverwege.

38
00:02:52,740 --> 00:02:57,990
Laten we ons algoritme voort te zetten door het plaatsen van de 16 in de gesorteerde gedeelte.

39
00:02:59,260 --> 00:03:03,820
Zestien is minder dan 42, dus laten we de 42 naar rechts.

40
00:03:05,700 --> 00:03:10,190
Zestien is ook minder dan 23, dus laten we ook dat element verschuiven.

41
00:03:11,790 --> 00:03:20,820
>> Nu 16 is groter dan 4. Dus, het lijkt erop dat we graag de 16 in te voegen tussen de 4 en de 23.

42
00:03:20,820 --> 00:03:24,620
Terwijl u de gesorteerde deel van de lijst van rechts naar links,

43
00:03:24,620 --> 00:03:29,160
4 is het eerste nummer die we hebben gezien dat kleiner is dan het aantal

44
00:03:29,160 --> 00:03:31,540
we proberen in te voegen.

45
00:03:31,540 --> 00:03:35,820
Zo, nu kunnen we invoegen de 16 in deze lege sleuf,

46
00:03:35,820 --> 00:03:40,520
die vergeet niet, hebben we gecreëerd door bewegende elementen in het soort gedeelte boven

47
00:03:40,520 --> 00:03:43,340
zoals we hebben ondervonden ze.

48
00:03:43,340 --> 00:03:47,900
>> Oke. Nu, hebben we vier gesorteerd elementen en twee ongesorteerde elementen.

49
00:03:47,900 --> 00:03:51,600
Dus, laten we de 8 te verplaatsen naar de gesorteerde gedeelte.

50
00:03:51,600 --> 00:03:55,010
Acht is minder dan 42.

51
00:03:55,010 --> 00:03:56,940
Acht is minder dan 23.

52
00:03:56,940 --> 00:04:00,230
En 8 kleiner is dan 16.

53
00:04:00,230 --> 00:04:03,110
Slechts 8 hoger is dan 4.

54
00:04:03,110 --> 00:04:07,280
Dus, willen we graag de 8 in te voegen tussen de 4 en de 16.

55
00:04:09,070 --> 00:04:13,650
En nu hebben we alleen nog een verlaten meer elementen te sorteren - de 15.

56
00:04:13,950 --> 00:04:16,589
Vijftien is minder dan 42,

57
00:04:16,589 --> 00:04:19,130
Vijftien is minder dan 23.

58
00:04:19,130 --> 00:04:21,750
En 15 is minder dan 16.

59
00:04:21,750 --> 00:04:24,810
Maar 15 groter is dan 8.

60
00:04:24,810 --> 00:04:27,440
>> Dus, hier is waar we willen onze laatste inbrengen te maken.

61
00:04:28,770 --> 00:04:30,330
En we zijn klaar.

62
00:04:30,330 --> 00:04:33,540
We hebben geen elementen in de ongesorteerde gedeelte,

63
00:04:33,540 --> 00:04:36,670
en ons gesorteerd gedeelte in de juiste volgorde.

64
00:04:36,670 --> 00:04:40,270
De nummers zijn gerangschikt volgens de van klein naar groot.

65
00:04:40,270 --> 00:04:44,330
Dus, laten we een kijkje nemen op een aantal pseudocode dat de stappen die we zojuist uitgevoerde beschrijft.

66
00:04:46,760 --> 00:04:51,740
>> Op lijn 1, kunnen we zien dat we moeten itereren over elk element in de lijst

67
00:04:51,740 --> 00:04:57,060
behalve de eerste, zal omdat het eerste element in de ongesorteerde gedeelte eenvoudigweg

68
00:04:57,060 --> 00:05:00,220
het eerste element in de gesorteerde gedeelte.

69
00:05:00,220 --> 00:05:06,320
Op lijnen 2 en 3, zijn we het bijhouden van onze huidige plaats in het ongesorteerde deel.

70
00:05:06,320 --> 00:05:10,450
Element staat voor het aantal die we momenteel verhuizen naar de gesorteerde gedeelte,

71
00:05:10,450 --> 00:05:15,600
en j vertegenwoordigt onze index in de ongesorteerde deel.

72
00:05:15,600 --> 00:05:20,980
>> Op lijn 4, we itereren door het gesorteerd gedeelte van rechts naar links.

73
00:05:20,980 --> 00:05:26,010
Gestopt moet itereren wanneer de element links van de huidige positie

74
00:05:26,010 --> 00:05:30,050
is minder dan het element dat we proberen in te voegen.

75
00:05:30,050 --> 00:05:35,600
Op lijn 5, we verschuiven elk element dat we een ruimte tegenkomen naar rechts.

76
00:05:35,600 --> 00:05:40,950
Op die manier zullen we een duidelijke ruimte om in te voegen in wanneer we het eerste element

77
00:05:40,950 --> 00:05:44,080
minder dan het element dat we gaan verhuizen.

78
00:05:44,080 --> 00:05:50,800
Op lijn 6, we updaten onze balie te blijven bewegen naar links door de gesorteerde gedeelte.

79
00:05:50,800 --> 00:05:56,860
Tot slot, op lijn 7, we plaatsen het element in de gesorteerde deel van de lijst.

80
00:05:56,860 --> 00:06:00,020
>> We weten dat het goed is om in te voegen in de juiste positie j,

81
00:06:00,020 --> 00:06:05,360
omdat we al verplaatst het element dat wordt gebruikt om daar te zijn een plaats naar rechts.

82
00:06:05,360 --> 00:06:09,460
Vergeet niet, we bewegen door de gesorteerde gedeelte van rechts naar links,

83
00:06:09,460 --> 00:06:13,960
maar we gaan door het ongesorteerde deel van links naar rechts.

84
00:06:13,960 --> 00:06:19,090
Oke. Laten we nu eens kijken hoe lang loopt dat algoritme hebben deelgenomen.

85
00:06:19,090 --> 00:06:25,300
We zullen eerst de vraag stellen hoe lang duurt het voor dit algoritme om te draaien in het slechtste geval.

86
00:06:25,300 --> 00:06:29,040
Herinner je dat we deze looptijd vertegenwoordigen met Big O notatie.

87
00:06:32,530 --> 00:06:38,500
Om onze lijst te sorteren, moesten we itereren over de elementen in het ongesorteerde deel,

88
00:06:38,500 --> 00:06:43,430
en voor elk van deze elementen mogelijk over alle elementen in de gesorteerde gedeelte.

89
00:06:43,430 --> 00:06:47,950
Intuïtief, dit klinkt als een O (n ^ 2) werking.

90
00:06:47,950 --> 00:06:51,840
>> Kijkend naar onze pseudocode, hebben we een lus genest in een andere lus,

91
00:06:51,840 --> 00:06:55,290
die inderdaad klinkt als een O (n ^ 2) werking.

92
00:06:55,290 --> 00:07:01,590
Echter, de gesorteerde deel van de lijst bevatten niet de hele lijst tot het einde.

93
00:07:01,590 --> 00:07:06,920
Toch kunnen we potentieel te voegen een nieuw element aan het begin van de gesorteerde gedeelte

94
00:07:06,920 --> 00:07:09,320
elke iteratie van de algoritme,

95
00:07:09,320 --> 00:07:14,500
wat betekent dat we zouden hebben om op dit moment te kijken naar elk element in de gesorteerde gedeelte.

96
00:07:14,500 --> 00:07:20,090
Dus, dat betekent dat we kunnen potentieel een vergelijking te maken voor het tweede element,

97
00:07:20,090 --> 00:07:24,660
twee vergelijkingen voor de derde element, enzovoort.

98
00:07:24,660 --> 00:07:32,480
Dus het aantal stappen is de som van de getallen van 1 tot de lengte van de lijst minus 1.

99
00:07:32,480 --> 00:07:35,240
We kunnen vertegenwoordigen dit met een sommatie.

100
00:07:41,170 --> 00:07:47,270
>> We zullen hier niet ingaan op optellingen, maar het blijkt dat deze opsomming is gelijk aan

101
00:07:47,270 --> 00:07:57,900
n (n - 1) over 2, wat overeenkomt n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Wanneer we spreken over asymptotische runtime,

103
00:08:00,800 --> 00:08:05,170
deze n ^ 2 term gaat dit n termijn domineren.

104
00:08:05,170 --> 00:08:11,430
Dus, insertion sort is Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Wat als we insertion sort liep op een reeds gesorteerde lijst.

106
00:08:16,150 --> 00:08:20,960
In dat geval zou bouwen we eenvoudigweg de gesorteerde gedeelte van links naar rechts.

107
00:08:20,960 --> 00:08:25,050
Dus, zullen we alleen maar in de orde van n stappen.

108
00:08:25,050 --> 00:08:29,740
>> Dat betekent dat insertion sort een best-case performance van n heeft,

109
00:08:29,740 --> 00:08:34,130
die wij vertegenwoordigen met Ω (n).

110
00:08:34,130 --> 00:08:36,190
En dat is het voor insertion sort,

111
00:08:36,190 --> 00:08:40,429
slechts een van de vele algoritmen die we kunnen gebruiken om een ​​lijst te sorteren.

112
00:08:40,429 --> 00:08:43,210
Mijn naam is Tommy, en dit is CS50.

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

114
00:08:46,110 --> 00:08:49,230
Oh, je kan het gewoon niet stoppen, dat zodra het begint.

115
00:09:01,620 --> 00:09:04,760
Oh, wij deden dat - >> Boom!