1
00:00:00,000 --> 00:00:02,826
>> [Musik spiller]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Så indsættelse slags er en anden
algoritme vi kan bruge til at sortere et array.

4
00:00:09,370 --> 00:00:12,350
Ideen bag denne algoritme
er at opbygge din sorterede vifte

5
00:00:12,350 --> 00:00:19,670
på plads, skiftende elementer ud af
den måde, som du går, for at gøre plads.

6
00:00:19,670 --> 00:00:22,240
Dette er en smule anderledes
fra valg sortere eller boble

7
00:00:22,240 --> 00:00:25,460
Sorter, for eksempel, hvor
vi justerer de steder,

8
00:00:25,460 --> 00:00:26,910
hvor vi laver swaps.

9
00:00:26,910 --> 00:00:29,760
>> I dette tilfælde, hvad vi er faktisk
gør, er glidende elementer

10
00:00:29,760 --> 00:00:31,390
i, ud af vejen.

11
00:00:31,390 --> 00:00:34,030
Hvordan denne algoritme
arbejde i pseudokode?

12
00:00:34,030 --> 00:00:37,646
Jamen lad os bare vilkårligt sige, at
første element i arrayet er sorteret.

13
00:00:37,646 --> 00:00:38,770
Vi bygger det på plads.

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

15
00:00:42,660 --> 00:00:43,890
er en ét element array.

16
00:00:43,890 --> 00:00:47,720
Og per definition en en
element array sorteret.

17
00:00:47,720 --> 00:00:50,850
>> Så vil vi gentage denne proces until--
vi vil gentage følgende proces

18
00:00:50,850 --> 00:00:52,900
indtil alle elementer sorteres.

19
00:00:52,900 --> 00:00:57,770
Kig på den næste usorterede element og
indsætte det i sorterede portion

20
00:00:57,770 --> 00:01:01,209
ved at flytte det krævede antal
elementer af vejen.

21
00:01:01,209 --> 00:01:03,750
Forhåbentlig vil denne visualisering
vil hjælpe dig se præcis, hvad der er

22
00:01:03,750 --> 00:01:05,980
foregår med indsættelse slags.

23
00:01:05,980 --> 00:01:08,010
>> Så igen, her er vores
Hele usorteret array,

24
00:01:08,010 --> 00:01:10,970
alle elementerne vist med rødt.

25
00:01:10,970 --> 00:01:13,320
Og lad os følge den
trin i vores pseudokode.

26
00:01:13,320 --> 00:01:16,970
Det første, vi gør, er vi kalder
første element i arrayet, sorteres.

27
00:01:16,970 --> 00:01:20,920
Så vi er bare vil sige
fem, er du nu ordnet.

28
00:01:20,920 --> 00:01:24,570
>> Så ser vi på den næste
usorteret element i arrayet

29
00:01:24,570 --> 00:01:27,610
og vi ønsker at indsætte, at
i sorteret del,

30
00:01:27,610 --> 00:01:29,750
ved at flytte elementer i.

31
00:01:29,750 --> 00:01:33,470
Så to er den næste usorteret
element i arrayet.

32
00:01:33,470 --> 00:01:36,250
Klart det hører inden
fem, så hvad vi skal gøre

33
00:01:36,250 --> 00:01:41,580
er slags holde to til side til en anden,
skift fem forhold, og derefter indsætte to

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

35
00:01:43,210 --> 00:01:45,280
Og nu kan vi sige, at to er sorteret.

36
00:01:45,280 --> 00:01:48,400
>> Så som du kan se, har vi kun hidtil
så på to elementer i arrayet.

37
00:01:48,400 --> 00:01:50,600
Vi har ikke set på
hvile på alle, men vi har

38
00:01:50,600 --> 00:01:54,582
fik disse to elementer ordnet efter
måde skiftemekanismen.

39
00:01:54,582 --> 00:01:56,410
>> Så vi gentage processen igen.

40
00:01:56,410 --> 00:01:58,850
Kig på den næste usorteret
element, det er en.

41
00:01:58,850 --> 00:02:04,010
Lad os antage, at afsat til en anden,
skift alt forbi, og sætte en

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

43
00:02:05,570 --> 00:02:08,110
>> Igen, stadig, vi har kun nogensinde
så på én, to og fem.

44
00:02:08,110 --> 00:02:12,480
Vi ved ikke, hvad der ellers er på vej,
men vi har ordnet disse tre elementer.

45
00:02:12,480 --> 00:02:16,030
>> Næste usorteret element er
tre, så vi vil sætte den til side.

46
00:02:16,030 --> 00:02:18,200
Vi vil ændre sig med det, vi
skal der, denne gang

47
00:02:18,200 --> 00:02:21,820
er ikke alt som i den tidligere
to tilfælde, det er bare de fem.

48
00:02:21,820 --> 00:02:25,440
Og så vil vi holde os tre i,
mellem to og fem.

49
00:02:25,440 --> 00:02:27,849
>> Seks er den næste usorteret
element til arrayet.

50
00:02:27,849 --> 00:02:31,140
Og i virkeligheden seks er større end fem, så
Vi behøver ikke engang at gøre noget swapping.

51
00:02:31,140 --> 00:02:35,710
Vi kan bare tack seks til højre ad
slutningen af ​​sorteret del.

52
00:02:35,710 --> 00:02:38,270
>> Endelig er fire
sidste usorteret element.

53
00:02:38,270 --> 00:02:42,060
Så vi vil lægge det til side, skift i løbet af
de elementer, vi har brug for at flytte forbi,

54
00:02:42,060 --> 00:02:43,780
og derefter sætte fire, hvor den hører.

55
00:02:43,780 --> 00:02:46,400
Og nu se, vi har sortering
af alle elementerne.

56
00:02:46,400 --> 00:02:48,150
Læg mærke med indsættelse
sortere, havde vi ikke

57
00:02:48,150 --> 00:02:50,240
at gå frem og tilbage over array.

58
00:02:50,240 --> 00:02:54,720
Vi gik kun på tværs array
én gang, og vi skiftede ting

59
00:02:54,720 --> 00:02:59,870
at vi havde allerede stødt på, med henblik på
at gøre plads til de nye elementer.

60
00:02:59,870 --> 00:03:02,820
>> Så hvad er den værste fald
scenarie med indsættelse slags?

61
00:03:02,820 --> 00:03:05,090
I værste tilfælde
array er i omvendt rækkefølge.

62
00:03:05,090 --> 00:03:11,180
Du er nødt til at flytte hvert af n elementer
op til n positioner, hver eneste gang vi

63
00:03:11,180 --> 00:03:12,880
foretage en indsættelse.

64
00:03:12,880 --> 00:03:15,720
Det er en masse skiftende.

65
00:03:15,720 --> 00:03:18,014
>> I bedste tilfælde er den
array er perfekt sorteret.

66
00:03:18,014 --> 00:03:20,680
Og lidt ligesom, hvad der skete
med fem og seks i eksempel

67
00:03:20,680 --> 00:03:23,779
hvor vi bare kunne hæfte det på
uden at skulle gøre noget skiftende,

68
00:03:23,779 --> 00:03:24,820
vi ville hovedsageligt gøre.

69
00:03:24,820 --> 00:03:27,560
>> Hvis du forestiller dig, at vores
matrix var en til seks,

70
00:03:27,560 --> 00:03:29,900
vi ville starte med
erklære en sorteres.

71
00:03:29,900 --> 00:03:33,300
To kommer efter en, så vi kan bare
sige, OK, godt et og to er ordnet.

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

73
00:03:36,190 --> 00:03:39,590
>> Vi er ikke at foretage nogen swaps, er vi
bare flytte denne vilkårlige linje

74
00:03:39,590 --> 00:03:42,460
mellem sorteret og usorteret, som vi går.

75
00:03:42,460 --> 00:03:46,646
Så effektivt som vi gjorde i eksemplet,
dreje elementer blå, som vi går videre.

76
00:03:46,646 --> 00:03:48,270
Så hvad er den værste fald runtime, så?

77
00:03:48,270 --> 00:03:51,854
Husk, at hvis vi er nødt til at flytte hver af
de n elementer eventuelt N positioner,

78
00:03:51,854 --> 00:03:54,020
forhåbentlig, der giver dig
en idé om, at det værste tilfælde

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

80
00:03:57,770 --> 00:04:00,220
>> Hvis array er perfekt
sorteret, alt, hvad vi har at gøre

81
00:04:00,220 --> 00:04:04,480
er at se på hvert enkelt element
én gang, og så vi er færdig.

82
00:04:04,480 --> 00:04:08,440
Så i bedste fald, 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
Det er CS50.

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