1
00:00:00,000 --> 00:00:02,826
>> [MUSIK SPELA]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Så insättningssortering är en annan
algoritm vi kan använda för att sortera en array.

4
00:00:09,370 --> 00:00:12,350
Tanken bakom denna algoritm
är att bygga din sorterade arrayen

5
00:00:12,350 --> 00:00:19,670
på plats, flytta delar av
det sätt som du går, för att göra plats.

6
00:00:19,670 --> 00:00:22,240
Detta är något annorlunda
från val sortera eller bubbla

7
00:00:22,240 --> 00:00:25,460
sortera, till exempel, där
vi justera platser,

8
00:00:25,460 --> 00:00:26,910
där vi gör swappar.

9
00:00:26,910 --> 00:00:29,760
>> I detta fall vad vi faktiskt
gör är glidelement

10
00:00:29,760 --> 00:00:31,390
över, ur vägen.

11
00:00:31,390 --> 00:00:34,030
Hur fungerar denna algoritm
arbeta i pseudokod?

12
00:00:34,030 --> 00:00:37,646
Bra låt oss bara godtyckligt säga att
första elementet i arrayen sorteras.

13
00:00:37,646 --> 00:00:38,770
Vi bygger den på plats.

14
00:00:38,770 --> 00:00:42,660
>> Vi ska gå en del i taget och
bygga det, och så det första vi ser

15
00:00:42,660 --> 00:00:43,890
är en en elementgrupp.

16
00:00:43,890 --> 00:00:47,720
Och per definition, en
elementuppsättningen sorteras.

17
00:00:47,720 --> 00:00:50,850
>> Sedan ska vi upprepa denna process until--
vi ska upprepa följande process

18
00:00:50,850 --> 00:00:52,900
tills alla elementen sorteras.

19
00:00:52,900 --> 00:00:57,770
Titta på nästa osorterat elementet och
sätt in det i den sorterade delen,

20
00:00:57,770 --> 00:01:01,209
genom att skifta det nödvändiga antalet
element ur vägen.

21
00:01:01,209 --> 00:01:03,750
Förhoppningsvis visualisering
hjälper dig att se exakt vad som är

22
00:01:03,750 --> 00:01:05,980
händer med insättningssortering.

23
00:01:05,980 --> 00:01:08,010
>> Så återigen, här är vår
Hela osorterade array,

24
00:01:08,010 --> 00:01:10,970
alla element markerade med rött.

25
00:01:10,970 --> 00:01:13,320
Och låt oss följa
stegen att vår pseudokod.

26
00:01:13,320 --> 00:01:16,970
Det första vi gör är vi kallar
första elementet i arrayen, sortering.

27
00:01:16,970 --> 00:01:20,920
Så vi är bara gonna säga
fem, du nu sortering.

28
00:01:20,920 --> 00:01:24,570
>> Sedan tittar vi på nästa
osorterade element i arrayen

29
00:01:24,570 --> 00:01:27,610
och vi vill infoga att
in i den sorterade partiet,

30
00:01:27,610 --> 00:01:29,750
genom att flytta element över.

31
00:01:29,750 --> 00:01:33,470
Så två är nästa osorterade
element i gruppen.

32
00:01:33,470 --> 00:01:36,250
Tydligt den tillhör före
fem, så vad vi ska göra

33
00:01:36,250 --> 00:01:41,580
är slags hålla två åt sidan för en andra,
skift fem över, och sedan in två

34
00:01:41,580 --> 00:01:43,210
före fem, där att ska gå.

35
00:01:43,210 --> 00:01:45,280
Och nu kan vi säga att två sorteras.

36
00:01:45,280 --> 00:01:48,400
>> Så som ni kan se, vi har bara så långt
tittat på två element i arrayen.

37
00:01:48,400 --> 00:01:50,600
Vi har inte tittat på
vila alls, men vi har

38
00:01:50,600 --> 00:01:54,582
fick dessa två element sorterat efter
sätt av växlingsmekanismen.

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

40
00:01:56,410 --> 00:01:58,850
Titta på nästa osorterade
element, det är en.

41
00:01:58,850 --> 00:02:04,010
Låt oss hålla det åt sidan för en sekund,
skifta allt över, och sätta en

42
00:02:04,010 --> 00:02:05,570
där det ska gå.

43
00:02:05,570 --> 00:02:08,110
>> Återigen, fortfarande, vi har bara någonsin
tittat på ett, två, och fem.

44
00:02:08,110 --> 00:02:12,480
Vi vet inte vad som kommer,
men vi har sorterat dessa tre element.

45
00:02:12,480 --> 00:02:16,030
>> Nästa osorterat elementet är
tre, så vi ska ställa den åt sidan.

46
00:02:16,030 --> 00:02:18,200
Vi kommer att flytta över vad vi
behöver som, denna gång

47
00:02:18,200 --> 00:02:21,820
är inte allt som i föregående
två fall är det bara fem.

48
00:02:21,820 --> 00:02:25,440
Och sedan ska vi hålla tre,
mellan de två och fem.

49
00:02:25,440 --> 00:02:27,849
>> Sex är nästa osorterade
element till arrayen.

50
00:02:27,849 --> 00:02:31,140
Och i själva verket sex är större än fem, så
Vi behöver inte ens göra något byte.

51
00:02:31,140 --> 00:02:35,710
Vi kan bara tack sex rätt på
I slutet av den sorterade delen.

52
00:02:35,710 --> 00:02:38,270
>> Slutligen, är fyra av
sista osorterade element.

53
00:02:38,270 --> 00:02:42,060
Så vi ska ställa den åt sidan, flytta över
de element som vi behöver för att flytta över,

54
00:02:42,060 --> 00:02:43,780
och sedan lägga fyra där den hör hemma.

55
00:02:43,780 --> 00:02:46,400
Och nu ser, vi har sort
av alla element.

56
00:02:46,400 --> 00:02:48,150
Lägg märke med insättning
sortera, hade vi inte

57
00:02:48,150 --> 00:02:50,240
att gå fram och tillbaka över matrisen.

58
00:02:50,240 --> 00:02:54,720
Vi gick bara över matrisen
en tid, och vi skiftade saker

59
00:02:54,720 --> 00:02:59,870
att vi hade redan stött på, för att
att göra plats för de nya elementen.

60
00:02:59,870 --> 00:03:02,820
>> Så vad är det värsta fallet
scenario med insättningssortering?

61
00:03:02,820 --> 00:03:05,090
I värsta fall, den
array är i omvänd ordning.

62
00:03:05,090 --> 00:03:11,180
Du måste flytta vart och ett av n element
upp till n positioner, varenda gång vi

63
00:03:11,180 --> 00:03:12,880
göra en införing.

64
00:03:12,880 --> 00:03:15,720
Det är en mycket växling.

65
00:03:15,720 --> 00:03:18,014
>> I bästa fall, den
array är perfekt sorteras.

66
00:03:18,014 --> 00:03:20,680
Och ungefär som vad som hände
med fem och sex i exemplet,

67
00:03:20,680 --> 00:03:23,779
där vi bara kunde lägga fram det på
utan att behöva göra någon växling,

68
00:03:23,779 --> 00:03:24,820
Vi skulle i princip göra det.

69
00:03:24,820 --> 00:03:27,560
>> Om ni föreställa er att vår
matris var en genom sex,

70
00:03:27,560 --> 00:03:29,900
vi skulle börja med
förklara ett sorteras.

71
00:03:29,900 --> 00:03:33,300
Två kommer efter en så att vi kan bara
säger, OK, väl ett och två är sorterade.

72
00:03:33,300 --> 00:03:36,190
Tre kommer efter två så, OK,
en och två och tre sorteras.

73
00:03:36,190 --> 00:03:39,590
>> Vi är inte gör några swappar, vi är
bara flytta denna godtycklig linje

74
00:03:39,590 --> 00:03:42,460
mellan sorteras och osorterade när vi går.

75
00:03:42,460 --> 00:03:46,646
Så effektivt som vi gjorde i exemplet,
roterande element blå, som vi går vidare.

76
00:03:46,646 --> 00:03:48,270
Så vad är det värsta fallet runtime, då?

77
00:03:48,270 --> 00:03:51,854
Kom ihåg att om vi måste flytta vart och ett av
de n elementen eventuellt N-positionema,

78
00:03:51,854 --> 00:03:54,020
förhoppningsvis som ger dig
en idé som det värsta fallet

79
00:03:54,020 --> 00:03:57,770
runtime är Big O n kvadrat.

80
00:03:57,770 --> 00:04:00,220
>> Om arrayen är perfekt
sorteras, allt vi har att göra

81
00:04:00,220 --> 00:04:04,480
är att titta på varje enskilt element
en gång, och sedan vi är klar.

82
00:04:04,480 --> 00:04:08,440
Så i bästa fall, är det omega n.

83
00:04:08,440 --> 00:04:09,490
>> Jag är Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Detta är CS50.

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