1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Infogning Sortera]

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

3
00:00:04,240 --> 00:00:07,290
[Detta är CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Låt oss ta en titt på insättning sortera, en algoritm för att ta en lista med tal och sortera dem.

5
00:00:13,060 --> 00:00:18,300
En algoritm, kom ihåg, är helt enkelt ett steg-för-steg förfarande för att utföra en uppgift.

6
00:00:18,300 --> 00:00:23,640
Den grundläggande idén bakom införandet sortera, är att dela vår lista i två delar,

7
00:00:23,640 --> 00:00:26,580
en sorterad del och en osorterad parti.

8
00:00:26,580 --> 00:00:29,290
>> Vid varje steg i algoritmen, är ett antal flyttas

9
00:00:29,290 --> 00:00:32,439
från osorterade delen till den sorterade delen

10
00:00:32,439 --> 00:00:35,680
tills slutligen hela listan är sorterad.

11
00:00:35,680 --> 00:00:43,340
Här är listan över sex osorterade tal - 23, 42, 4, 16, 8, och 15.

12
00:00:43,340 --> 00:00:47,680
Eftersom dessa siffror är inte alla i stigande ordning, de är osorterade.

13
00:00:47,680 --> 00:00:53,890
Eftersom vi inte har börjat sortera ännu, vi betrakta alla sex element vårt osorterat del.

14
00:00:53,890 --> 00:00:59,270
>> När vi börjar sortera, vi sätta dessa sorterade siffror till vänster om dessa.

15
00:00:59,270 --> 00:01:03,600
Så, låt oss börja med 23, det första elementet i vår lista.

16
00:01:03,600 --> 00:01:06,930
Vi har inte några element i vår sorterade del ännu,

17
00:01:06,930 --> 00:01:12,460
så låt oss bara betrakta 23 som början och slutet av vår sorterade delen.

18
00:01:12,460 --> 00:01:16,510
Nu har vår sorterade delen en siffra, 23,

19
00:01:16,510 --> 00:01:20,260
och vår osorterade delen har dessa fem siffror.

20
00:01:20,260 --> 00:01:27,320
Låt oss nu in i nästa nummer i vår osorterat del, 42, in i den sorterade delen.

21
00:01:27,320 --> 00:01:35,930
>> För att göra det behöver vi för att jämföra 42 till 23 - den enda del i vår sorterade delen hittills.

22
00:01:35,930 --> 00:01:41,980
Fyrtiotvå är större än 23, så vi kan helt enkelt lägga 42 till slutet

23
00:01:41,980 --> 00:01:45,420
av den sorterade delen av listan. Bra!

24
00:01:45,420 --> 00:01:51,850
Nu har vår sorterade del har två element, och vår osorterade del har fyra delar.

25
00:01:51,850 --> 00:01:57,200
Så, låt oss nu gå till 4, nästa element i osorterade delen.

26
00:01:57,200 --> 00:02:00,230
Så bör där detta placeras i den sorterade delen?

27
00:02:00,230 --> 00:02:04,220
>> Kom ihåg, vill vi placera detta nummer i sorterad ordning

28
00:02:04,220 --> 00:02:08,680
så vår sorterade partiet förblir korrekt sorteras vid alla tidpunkter.

29
00:02:08,680 --> 00:02:14,380
Om vi ​​placerar 4 till höger om 42, så vår lista kommer att vara ur funktion.

30
00:02:14,380 --> 00:02:18,380
Så, låt oss fortsätta gå höger till vänster i vår Sortera del.

31
00:02:18,380 --> 00:02:23,260
När vi går, låt oss flytta varje nummer ned en plats att göra plats för det nya numret.

32
00:02:25,440 --> 00:02:31,740
Okej, är 4 också mindre än 23, så vi kan inte placera den här heller.

33
00:02:31,740 --> 00:02:34,480
Låt oss flytta 23 rätta ställe.

34
00:02:36,500 --> 00:02:43,120
>> Det betyder att vi vill placera 4 i den första öppningen i sorterade delen.

35
00:02:43,120 --> 00:02:46,300
Lägg märke till hur detta utrymme i listan redan tom,

36
00:02:46,300 --> 00:02:51,120
eftersom vi har rört sig sorterade element ner som vi har stött dem.

37
00:02:51,120 --> 00:02:52,740
Okej. Så, vi halvvägs där.

38
00:02:52,740 --> 00:02:57,990
Låt oss fortsätta vår algoritm genom att föra in 16 i den sorterade delen.

39
00:02:59,260 --> 00:03:03,820
Sexton är mindre än 42, så låt oss flytta 42 till höger.

40
00:03:05,700 --> 00:03:10,190
Sexton är också mindre än 23, så låt oss också flytta det elementet.

41
00:03:11,790 --> 00:03:20,820
>> Nu är 16 större än 4. Så ser det ut som om vi skulle vilja sätta in 16 mellan 4 och 23.

42
00:03:20,820 --> 00:03:24,620
När du flyttar genom den sorterade delen av listan från höger till vänster,

43
00:03:24,620 --> 00:03:29,160
4 är det första numret har vi sett som är mindre än det antal

44
00:03:29,160 --> 00:03:31,540
vi försöker infoga.

45
00:03:31,540 --> 00:03:35,820
Så nu kan vi sätta in 16 i denna tomma plats,

46
00:03:35,820 --> 00:03:40,520
som kom ihåg, har vi skapat av rörliga element i sorteringen delen över

47
00:03:40,520 --> 00:03:43,340
som vi har stött på dem.

48
00:03:43,340 --> 00:03:47,900
>> Okej. Nu har vi fyra sorterade element och två osorterade element.

49
00:03:47,900 --> 00:03:51,600
Så, låt oss flytta 8 i den sorterade delen.

50
00:03:51,600 --> 00:03:55,010
Åtta är mindre än 42.

51
00:03:55,010 --> 00:03:56,940
Åtta är mindre än 23.

52
00:03:56,940 --> 00:04:00,230
Och 8 är mindre än 16.

53
00:04:00,230 --> 00:04:03,110
Men 8 är större än 4.

54
00:04:03,110 --> 00:04:07,280
Så vill vi att sätta in 8 mellan 4 och 16.

55
00:04:09,070 --> 00:04:13,650
Och nu har vi bara en del kvar att sortera - den 15.

56
00:04:13,950 --> 00:04:16,589
Femton är mindre än 42,

57
00:04:16,589 --> 00:04:19,130
Femton är mindre än 23.

58
00:04:19,130 --> 00:04:21,750
Och 15 är mindre än 16.

59
00:04:21,750 --> 00:04:24,810
Men 15 är större än 8.

60
00:04:24,810 --> 00:04:27,440
>> Så, här är där vi vill göra vår sista insättning.

61
00:04:28,770 --> 00:04:30,330
Och vi är klara.

62
00:04:30,330 --> 00:04:33,540
Vi har inga fler element i osorterade delen,

63
00:04:33,540 --> 00:04:36,670
och vår sorterade delen är i rätt ordning.

64
00:04:36,670 --> 00:04:40,270
Siffrorna är ordnade från lägsta till högsta.

65
00:04:40,270 --> 00:04:44,330
Så, låt oss ta en titt på några pseudokod som beskriver de steg vi bara utförs.

66
00:04:46,760 --> 00:04:51,740
>> På rad 1, kan vi se att vi kommer att behöva iterera över varje element i listan

67
00:04:51,740 --> 00:04:57,060
utom den första, kommer sedan den första delen i den osorterade delen helt enkelt bli

68
00:04:57,060 --> 00:05:00,220
det första elementet i den sorterade delen.

69
00:05:00,220 --> 00:05:06,320
På linje 2 och 3, vi hålla koll på vår nuvarande plats i osorterade delen.

70
00:05:06,320 --> 00:05:10,450
Element representerar antalet vi nu går in i den sorterade delen,

71
00:05:10,450 --> 00:05:15,600
och j representerar vårt index i osorterade delen.

72
00:05:15,600 --> 00:05:20,980
>> På rad 4, vi iterera igenom den sorterade delen från höger till vänster.

73
00:05:20,980 --> 00:05:26,010
Vi vill sluta iteration när elementet till vänster om vår nuvarande position

74
00:05:26,010 --> 00:05:30,050
är mindre än elementet vi försöker infoga.

75
00:05:30,050 --> 00:05:35,600
På rad 5, vi flytta varje element vi möter ett utrymme till höger.

76
00:05:35,600 --> 00:05:40,950
På så sätt kommer vi att ha ett fritt utrymme för att infoga i när vi hittar det första elementet

77
00:05:40,950 --> 00:05:44,080
mindre än elementet vi flyttar.

78
00:05:44,080 --> 00:05:50,800
På rad 6, vi uppdaterar vår disk för att fortsätta att röra sig kvar genom den sorterade delen.

79
00:05:50,800 --> 00:05:56,860
Slutligen, på linje 7, vi sätter elementet i den sorterade delen av listan.

80
00:05:56,860 --> 00:06:00,020
>> Vi vet att det är okej att sätta på plats j,

81
00:06:00,020 --> 00:06:05,360
eftersom vi har redan flyttat det element som används för att vara där en plats till höger.

82
00:06:05,360 --> 00:06:09,460
Kom ihåg, vi rör sig genom den sorterade delen från höger till vänster,

83
00:06:09,460 --> 00:06:13,960
men vi rör sig genom osorterade delen från vänster till höger.

84
00:06:13,960 --> 00:06:19,090
Okej. Låt oss nu ta en titt på hur långvariga som algoritm tog.

85
00:06:19,090 --> 00:06:25,300
Vi kommer först fråga frågan hur lång tid tar det för denna algoritm att köra i värsta fall.

86
00:06:25,300 --> 00:06:29,040
Minns att vi representerar det gångtid med Big O notation.

87
00:06:32,530 --> 00:06:38,500
För att sortera vår lista, vi var tvungna att iterera över elementen i osorterade delen,

88
00:06:38,500 --> 00:06:43,430
och för varje enskild beståndsdel, eventuellt över alla element i den sorterade delen.

89
00:06:43,430 --> 00:06:47,950
Intuitivt, detta låter som en O (n ^ 2) drift.

90
00:06:47,950 --> 00:06:51,840
>> Titta på vår pseudokod har vi en slinga kapslad inuti en annan slinga,

91
00:06:51,840 --> 00:06:55,290
som faktiskt låter som en O (n ^ 2) drift.

92
00:06:55,290 --> 00:07:01,590
Däremot har den sorterade delen av listan innehåller inte hela listan ända till slutet.

93
00:07:01,590 --> 00:07:06,920
Ändå kan vi sätta potentiellt nytt element i början av sorterade delen

94
00:07:06,920 --> 00:07:09,320
på varje iteration av algoritmen,

95
00:07:09,320 --> 00:07:14,500
vilket innebär att vi skulle behöva titta på varje element närvarande i den sorterade delen.

96
00:07:14,500 --> 00:07:20,090
Så innebär att vi skulle kunna göra en jämförelse för det andra elementet,

97
00:07:20,090 --> 00:07:24,660
två jämförelser för det tredje elementet, och så vidare.

98
00:07:24,660 --> 00:07:32,480
Så är det totala antalet steg summan av heltalen från 1 till längden av listan minus 1.

99
00:07:32,480 --> 00:07:35,240
Vi kan representera detta med en summering.

100
00:07:41,170 --> 00:07:47,270
>> Vi kommer inte att gå in i summeringar här, men det visar sig att denna summering är lika med

101
00:07:47,270 --> 00:07:57,900
n (n - 1) över 2, vilket motsvarar n ^ 2/2 - N / 2.

102
00:07:57,900 --> 00:08:00,800
När man talar om asymptotisk runtime,

103
00:08:00,800 --> 00:08:05,170
Detta n ^ 2 term kommer att dominera denna N sikt.

104
00:08:05,170 --> 00:08:11,430
Så, införande Sortera Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Tänk om vi körde insättning Sortera på en redan sorterad lista.

106
00:08:16,150 --> 00:08:20,960
I så fall skulle vi bygga helt enkelt upp den sorterade delen från vänster till höger.

107
00:08:20,960 --> 00:08:25,050
Så behöver vi bara på beställning av n steg.

108
00:08:25,050 --> 00:08:29,740
>> Det innebär att införandet Sortera har bästa fall prestanda N,

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

110
00:08:34,130 --> 00:08:36,190
Och det är det för insättning sortera,

111
00:08:36,190 --> 00:08:40,429
bara en av de många algoritmer som vi kan använda för att sortera en lista.

112
00:08:40,429 --> 00:08:43,210
Mitt namn är Tommy, och detta är CS50.

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

114
00:08:46,110 --> 00:08:49,230
Åh, du bara inte kan sluta att när det börjar.

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