1
00:00:00,000 --> 00:00:02,826
>> [Muziek]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Dus insertion sort is een ander
algoritme we kunnen gebruiken om een ​​array te sorteren.

4
00:00:09,370 --> 00:00:12,350
Het idee achter dit algoritme
is het gesorteerde array bouwen

5
00:00:12,350 --> 00:00:19,670
in de plaats, het verschuiven van elementen uit
de weg als je gaat, om ruimte te maken.

6
00:00:19,670 --> 00:00:22,240
Dit is iets anders
uit selectie sort of bel

7
00:00:22,240 --> 00:00:25,460
sorteren, bijvoorbeeld wanneer
we het aanpassen van de locaties,

8
00:00:25,460 --> 00:00:26,910
waar we het maken van swaps.

9
00:00:26,910 --> 00:00:29,760
>> In dit geval wat we eigenlijk
doen is schuifelementen

10
00:00:29,760 --> 00:00:31,390
over, uit de weg.

11
00:00:31,390 --> 00:00:34,030
Hoe werkt dit algoritme
werken in pseudocode?

12
00:00:34,030 --> 00:00:37,646
Nou laten we gewoon willekeurig zeggen dat de
eerste element van de array wordt gesorteerd.

13
00:00:37,646 --> 00:00:38,770
We bouwen op zijn plaats.

14
00:00:38,770 --> 00:00:42,660
>> We gaan één element in een tijd en
bouwen, en dus het eerste wat we zien

15
00:00:42,660 --> 00:00:43,890
is één element array.

16
00:00:43,890 --> 00:00:47,720
En per definitie een
element-array wordt gesorteerd.

17
00:00:47,720 --> 00:00:50,850
>> Dan zullen we dit proces herhalen until--
zullen we het volgende proces te herhalen

18
00:00:50,850 --> 00:00:52,900
totdat alle elementen gesorteerd.

19
00:00:52,900 --> 00:00:57,770
Kijk naar de volgende ongesorteerd element en
voeg deze aan de gesorteerde gedeelte,

20
00:00:57,770 --> 00:01:01,209
door het verschuiven van het vereiste aantal
elementen uit de weg.

21
00:01:01,209 --> 00:01:03,750
Hopelijk deze visualisatie
helpt u precies zien wat er

22
00:01:03,750 --> 00:01:05,980
er met insertion sort.

23
00:01:05,980 --> 00:01:08,010
>> Dus nogmaals, hier is onze
hele ongesorteerde array,

24
00:01:08,010 --> 00:01:10,970
alle elementen in rood aangegeven.

25
00:01:10,970 --> 00:01:13,320
En laten we volgen
stappen pseudocode.

26
00:01:13,320 --> 00:01:16,970
Het eerste wat we doen, we noemen het
eerste element van de array gesorteerd.

27
00:01:16,970 --> 00:01:20,920
Dus we gaan gewoon zeg
vijf, je bent nu opgelost.

28
00:01:20,920 --> 00:01:24,570
>> Daarna kijken we naar de volgende
ongesorteerde element van de array

29
00:01:24,570 --> 00:01:27,610
en we willen voegen dat
in de gesorteerde gedeelte,

30
00:01:27,610 --> 00:01:29,750
door het verschuiven van elementen over.

31
00:01:29,750 --> 00:01:33,470
Dus twee is de volgende ongesorteerd
element van de array.

32
00:01:33,470 --> 00:01:36,250
Het is duidelijk dat het voor het hoort
vijf, dus wat we gaan doen

33
00:01:36,250 --> 00:01:41,580
is een soort van houden twee opzij voor een tweede,
verschuiven vijf over, en plaats twee

34
00:01:41,580 --> 00:01:43,210
voor vijf, waar je moet gaan.

35
00:01:43,210 --> 00:01:45,280
En nu kunnen we zeggen dat twee wordt gesorteerd.

36
00:01:45,280 --> 00:01:48,400
>> Dus zoals je kunt zien, hebben we alleen zo ver
bekeek twee elementen van de array.

37
00:01:48,400 --> 00:01:50,600
We hebben niet gekeken naar de
rust helemaal niet, maar we hebben

38
00:01:50,600 --> 00:01:54,582
kreeg deze twee elementen naargelang
weg van het schakelmechanisme.

39
00:01:54,582 --> 00:01:56,410
>> Zodat we het proces herhalen.

40
00:01:56,410 --> 00:01:58,850
Kijk naar de volgende ongesorteerde
element, dat is één.

41
00:01:58,850 --> 00:02:04,010
Laten we stellen dat gereserveerd voor een tweede,
verschuiven alles over, en zet een

42
00:02:04,010 --> 00:02:05,570
waar het zou moeten gaan.

43
00:02:05,570 --> 00:02:08,110
>> Nogmaals, nog steeds, hebben we alleen ooit
keken, twee en vijf.

44
00:02:08,110 --> 00:02:12,480
We weten niet wat er nog komt,
maar we hebben deze drie elementen gesorteerd worden.

45
00:02:12,480 --> 00:02:16,030
>> Volgende ongesorteerd element
drie, dus we zullen het opzij zetten.

46
00:02:16,030 --> 00:02:18,200
We zullen verschuiven over wat we
moeten die ditmaal

47
00:02:18,200 --> 00:02:21,820
niet alles zoals in het voorgaande
twee gevallen, het is gewoon de vijf.

48
00:02:21,820 --> 00:02:25,440
En dan zullen we drie in steken,
tussen de twee en vijf.

49
00:02:25,440 --> 00:02:27,849
>> Zes is de volgende ongesorteerd
element aan de array.

50
00:02:27,849 --> 00:02:31,140
En inderdaad zes meer dan vijf, dus
we niet eens behoefte aan een swapping doen.

51
00:02:31,140 --> 00:02:35,710
We kunnen gewoon overstag zes recht op
het einde van de gesorteerde gedeelte.

52
00:02:35,710 --> 00:02:38,270
>> Tenslotte vier de
laatste ongesorteerd element.

53
00:02:38,270 --> 00:02:42,060
Dus we het opzij zetten, dan verschuiven
de elementen moeten we dan verschuiven,

54
00:02:42,060 --> 00:02:43,780
en vervolgens vier waar het thuishoort.

55
00:02:43,780 --> 00:02:46,400
En kijk nu, we hebben een soort
alle elementen.

56
00:02:46,400 --> 00:02:48,150
Opmerken met invoeging
sorteren, hebben we niet

57
00:02:48,150 --> 00:02:50,240
heen en weer over de matrix gaan.

58
00:02:50,240 --> 00:02:54,720
We gingen alleen over de array
één keer, en we verschoven dingen

59
00:02:54,720 --> 00:02:59,870
dat we al hadden ondervonden, met het oog
om ruimte voor de nieuwe elementen te maken.

60
00:02:59,870 --> 00:03:02,820
>> Dus wat is het ergste geval
scenario met inbrengen soort?

61
00:03:02,820 --> 00:03:05,090
In het ergste geval, de
array in omgekeerde volgorde.

62
00:03:05,090 --> 00:03:11,180
Je moet elk van de n elementen verschuiven
tot n posities, iedere keer dat wij

63
00:03:11,180 --> 00:03:12,880
maak een inbrengen.

64
00:03:12,880 --> 00:03:15,720
Dat is een hoop van het verschuiven.

65
00:03:15,720 --> 00:03:18,014
>> In het beste geval is de
array wordt perfect opgelost.

66
00:03:18,014 --> 00:03:20,680
En een soort als wat er gebeurd
met vijf en zes in het voorbeeld,

67
00:03:20,680 --> 00:03:23,779
waar we konden gewoon overstag het op
zonder enige verschuiving te doen,

68
00:03:23,779 --> 00:03:24,820
we zouden in wezen dat te doen.

69
00:03:24,820 --> 00:03:27,560
>> Als je je voorstellen dat onze
serie was één tot en met zes,

70
00:03:27,560 --> 00:03:29,900
we af zou beginnen door
verklaren één wordt gesorteerd.

71
00:03:29,900 --> 00:03:33,300
Twee komt na een, zodat we kunnen gewoon
zeggen, OK, goed één en twee zijn gesorteerd.

72
00:03:33,300 --> 00:03:36,190
Drie komt na twee zo, OK,
één en twee en drie zijn gesorteerd.

73
00:03:36,190 --> 00:03:39,590
>> We zijn niet het maken van een swap, we zijn
gewoon verplaatsen van dit willekeurige lijn

74
00:03:39,590 --> 00:03:42,460
tussen gesorteerd en ongesorteerd als we verder gaan.

75
00:03:42,460 --> 00:03:46,646
Zo effectief we in het voorbeeld,
draaien elementen blauw, als we verder gaan.

76
00:03:46,646 --> 00:03:48,270
Dus wat is het ergste geval runtime, dan?

77
00:03:48,270 --> 00:03:51,854
Vergeet niet, als we moeten elke shift
de n elementen eventueel n plaatsen,

78
00:03:51,854 --> 00:03:54,020
hopelijk dat geeft
een idee dat het ergste geval

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

80
00:03:57,770 --> 00:04:00,220
>> Als de matrix perfect
naargelang, alles wat we moeten doen

81
00:04:00,220 --> 00:04:04,480
is te kijken naar elk element
een keer, en dan zijn we klaar.

82
00:04:04,480 --> 00:04:08,440
Dus in het beste geval is het omega van de n.

83
00:04:08,440 --> 00:04:09,490
>> Ik ben Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Dit is CS50.

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