1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Lad os tage et kig på udvælgelse slags, en algoritme

2
00:00:09,980 --> 00:00:12,800
for at tage en liste over numre og sortere dem.

3
00:00:12,800 --> 00:00:15,750
En algoritme, husk, er simpelthen en trin-for-trin

4
00:00:15,750 --> 00:00:18,370
procedure for opstilling af en opgave.

5
00:00:18,370 --> 00:00:21,470
Den grundlæggende idé bag udvælgelsen slags er at opdele

6
00:00:21,470 --> 00:00:23,390
vores liste i to dele -

7
00:00:23,390 --> 00:00:26,810
en sorteret del og en usorteret portion.

8
00:00:26,810 --> 00:00:30,200
På hvert trin af algoritmen, er et tal flyttes fra

9
00:00:30,200 --> 00:00:33,800
usorteret del til den sorterede del, indtil i sidste ende

10
00:00:33,800 --> 00:00:35,880
Hele listen er sorteret.

11
00:00:35,880 --> 00:00:38,510
Så her er en liste med seks numre -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8 og 15.

13
00:00:44,010 --> 00:00:47,680
Lige nu hele listen anses usorteret.

14
00:00:47,680 --> 00:00:51,770
Selv om en række som 16 kan allerede være i sin rette

15
00:00:51,770 --> 00:00:56,040
placering, vores algoritme har ingen mulighed for at vide, at indtil

16
00:00:56,040 --> 00:00:57,980
Hele listen er sorteret.

17
00:00:57,980 --> 00:01:01,355
Så vi vil overveje alle tal, der skal usorteret indtil vi sorterer

18
00:01:01,355 --> 00:01:03,800
det os.

19
00:01:03,800 --> 00:01:06,890
Vi ved, at vi ønsker, at listen skal være i stigende orden.

20
00:01:06,890 --> 00:01:10,200
Så vi vil gerne opbygge det sorterede del af vores liste

21
00:01:10,200 --> 00:01:13,280
fra venstre mod højre, mindst til størst.

22
00:01:13,280 --> 00:01:17,970
For at gøre det, vil vi nødt til at finde den mindste usorteret element

23
00:01:17,970 --> 00:01:21,350
og sætte det i slutningen af ​​det sorterede portion.

24
00:01:21,350 --> 00:01:25,370
Da denne liste ikke er sorteret, den eneste måde at gøre det er at

25
00:01:25,370 --> 00:01:29,330
se på hvert element i den usorterede del, huske

26
00:01:29,330 --> 00:01:32,010
hvilket element er det laveste og sammenligne

27
00:01:32,010 --> 00:01:33,770
hvert element i denne.

28
00:01:33,770 --> 00:01:36,150
Så vi vil først se på den 23.

29
00:01:36,150 --> 00:01:38,650
Dette er det første element, vi har set, så vi vil huske

30
00:01:38,650 --> 00:01:40,050
det som minimum.

31
00:01:40,050 --> 00:01:42,320
Næste vil vi se på 42.

32
00:01:42,320 --> 00:01:46,720
42 er større end 23, så 23 stadig et minimum.

33
00:01:46,720 --> 00:01:51,210
Næste er den 4, som er mindre end 23, så vi vil huske 4

34
00:01:51,210 --> 00:01:52,880
som den nye minimum.

35
00:01:52,880 --> 00:01:56,380
Next er 16, som er større end 4, således 4

36
00:01:56,380 --> 00:01:57,980
er stadig et minimum.

37
00:01:57,980 --> 00:02:03,670
8 er større end 4, og 15 er større end 4, således 4 skal være

38
00:02:03,670 --> 00:02:05,980
den mindste usorteret element.

39
00:02:05,980 --> 00:02:09,350
Så selvom vi som mennesker kan straks se, at 4 er

40
00:02:09,350 --> 00:02:12,300
den mindste del, vores algoritme nødvendigt at se på

41
00:02:12,300 --> 00:02:15,710
hver usorterede element, selv efter at vi har fundet den 4 -

42
00:02:15,710 --> 00:02:16,860
minimum element.

43
00:02:16,860 --> 00:02:19,900
Så nu, at vi har fundet den mindste element, 4, vil vi gerne

44
00:02:19,900 --> 00:02:23,410
at flytte den i den sorterede del af listen.

45
00:02:23,410 --> 00:02:27,320
Da dette er det første skridt, det betyder, at vi ønsker at sætte 4 på

46
00:02:27,320 --> 00:02:29,680
begyndelsen af ​​listen.

47
00:02:29,680 --> 00:02:33,040
Lige nu 23 er i begyndelsen af ​​listen, så

48
00:02:33,040 --> 00:02:36,080
lad os bytte 4 og 23.

49
00:02:36,080 --> 00:02:38,870
Så nu vores liste ser sådan ud.

50
00:02:38,870 --> 00:02:42,710
Vi ved, at 4 skal være i sin endelige placering, fordi det er

51
00:02:42,710 --> 00:02:45,890
både det mindste element og elementet i begyndelsen

52
00:02:45,890 --> 00:02:46,960
af listen.

53
00:02:46,960 --> 00:02:50,650
Så det betyder, at vi ikke får brug for at flytte den igen.

54
00:02:50,650 --> 00:02:53,910
Så lad os gentage denne proces for at tilføje endnu et element til den

55
00:02:53,910 --> 00:02:55,910
sorteret del af listen.

56
00:02:55,910 --> 00:02:58,950
Vi ved, at vi ikke behøver at se på 4, fordi det er

57
00:02:58,950 --> 00:03:00,000
allerede sorteret.

58
00:03:00,000 --> 00:03:03,540
Så vi kan starte på 42, ​​som vi vil huske som den

59
00:03:03,540 --> 00:03:05,290
minimum element.

60
00:03:05,290 --> 00:03:08,700
Så næste vi vil se på 23, som er mindre end 42, så vi

61
00:03:08,700 --> 00:03:11,620
Husk 23 er det nye minimum.

62
00:03:11,620 --> 00:03:14,870
Næste vi ser 16, som er mindre end 23, så

63
00:03:14,870 --> 00:03:16,800
16 er det nye minimum.

64
00:03:16,800 --> 00:03:19,720
Nu skal vi se på de 8, som er mindre end 16, så

65
00:03:19,720 --> 00:03:21,130
8 er den nye minimum.

66
00:03:21,130 --> 00:03:25,900
Og endelig 8 er mindre end 15, så vi ved, 8 er et minimum

67
00:03:25,900 --> 00:03:27,780
usorteret element.

68
00:03:27,780 --> 00:03:30,660
Så det betyder, at vi bør tilføje 8 til det sorterede

69
00:03:30,660 --> 00:03:32,450
del af listen.

70
00:03:32,450 --> 00:03:35,990
Lige nu 4 er det eneste sorteres element, så vi ønsker at placere

71
00:03:35,990 --> 00:03:38,410
de 8 ved siden af ​​4.

72
00:03:38,410 --> 00:03:41,920
Idet 42 er det første element i den usorterede del af

73
00:03:41,920 --> 00:03:47,260
liste, vil vi ønsker at bytte den 42 og den 8.

74
00:03:47,260 --> 00:03:49,680
Så nu vores liste ser sådan ud.

75
00:03:49,680 --> 00:03:53,830
4 og 8 repræsenterer sorteret del af listen, og

76
00:03:53,830 --> 00:03:56,440
resterende tal repræsenterer usorteret

77
00:03:56,440 --> 00:03:58,260
del af listen.

78
00:03:58,260 --> 00:04:00,630
Så lad os fortsætte med en anden iteration.

79
00:04:00,630 --> 00:04:03,850
Vi starter med 23 denne gang, da vi ikke behøver at se på

80
00:04:03,850 --> 00:04:05,770
Den 4 og 8 længere, fordi de har

81
00:04:05,770 --> 00:04:07,660
allerede blevet sorteret.

82
00:04:07,660 --> 00:04:10,270
16 er under 23, så vi vil huske

83
00:04:10,270 --> 00:04:12,070
16 som den nye minimum.

84
00:04:12,070 --> 00:04:18,149
16 er mindre end 42, men 15 er mindre end 16, så 15 skal være

85
00:04:18,149 --> 00:04:20,480
den minimale usorteret element.

86
00:04:20,480 --> 00:04:24,580
Så nu er vi ønsker at bytte de 15 og 23 til

87
00:04:24,580 --> 00:04:26,310
give os denne liste.

88
00:04:26,310 --> 00:04:30,500
Den sorterede portion af listen består af 4, 8 og 15, og

89
00:04:30,500 --> 00:04:33,210
disse elementer er stadig usorteret.

90
00:04:33,210 --> 00:04:36,900
Men det bare så sker det, at den næste usorteret element, 16,

91
00:04:36,900 --> 00:04:38,480
allerede sorteret.

92
00:04:38,480 --> 00:04:42,060
Men der er ingen måde for vores algoritme til at vide, at 16

93
00:04:42,060 --> 00:04:45,230
er allerede i sin korrekte placering, så vi stadig nødt til at

94
00:04:45,230 --> 00:04:47,870
gentages nøjagtig samme proces.

95
00:04:47,870 --> 00:04:53,750
Så vi se, at 16 er mindre end 42, og 16 er mindre end 23, så

96
00:04:53,750 --> 00:04:56,230
16 skal være den mindste element.

97
00:04:56,230 --> 00:04:59,010
Det er umuligt at bytte dette element med sig selv, så vi kan

98
00:04:59,010 --> 00:05:01,780
blot lade det på denne placering.

99
00:05:01,780 --> 00:05:04,660
Så vi har brug for endnu en pass af vores algoritme.

100
00:05:04,660 --> 00:05:09,370
42 er over 23, så 23 skal være

101
00:05:09,370 --> 00:05:10,970
mindst usorteret element.

102
00:05:10,970 --> 00:05:17,410
Når vi bytte 23 og 42, ender vi med vores endelige

103
00:05:17,410 --> 00:05:18,530
sorteret liste -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
Vi ved 42 skal være på det rigtige sted, da det er den

106
00:05:26,830 --> 00:05:30,210
eneste element tilbage, og det er udvælgelse slags.

107
00:05:30,210 --> 00:05:32,100
Lad os nu formalisere vores algoritme med nogle

108
00:05:32,100 --> 00:05:34,540
pseudokode.

109
00:05:34,540 --> 00:05:37,760
På linje et, kan vi se, at vi er nødt til at integrere i

110
00:05:37,760 --> 00:05:39,530
hvert element på listen.

111
00:05:39,530 --> 00:05:42,150
Undtagen det sidste element, idet 1 element

112
00:05:42,150 --> 00:05:44,230
Listen er allerede sorteret.

113
00:05:44,230 --> 00:05:48,100
I linje to, betragter vi det første element i den usorterede

114
00:05:48,100 --> 00:05:51,080
del af listen for at være det minimum, som vi gjorde med vores

115
00:05:51,080 --> 00:05:53,750
eksempel, så vi har noget at sammenligne med.

116
00:05:53,750 --> 00:05:57,260
Linje tre begynder en anden sløjfe, hvor vi gentage over

117
00:05:57,260 --> 00:05:59,170
hvert usorteret element.

118
00:05:59,170 --> 00:06:02,150
Vi ved, at efter jeg iterationer, den sorterede portion

119
00:06:02,150 --> 00:06:05,330
på vores liste, skal jeg har elementer i det, da hvert trin

120
00:06:05,330 --> 00:06:06,890
sorterer ét element.

121
00:06:06,890 --> 00:06:11,770
Så det første usorteret element skal være i position I plus 1.

122
00:06:11,770 --> 00:06:15,440
I linje fire, sammenligner vi det aktuelle element til et minimum

123
00:06:15,440 --> 00:06:17,750
element, som vi har set hidtil.

124
00:06:17,750 --> 00:06:20,560
Hvis det aktuelle element er mindre end den mindste

125
00:06:20,560 --> 00:06:23,870
element, så vi husker det aktuelle element som ny

126
00:06:23,870 --> 00:06:26,250
minimum på linje fem.

127
00:06:26,250 --> 00:06:29,900
Endelig på linje seks og syv, bytte vi det minimum

128
00:06:29,900 --> 00:06:33,080
element med det første usorterede element, hvorved

129
00:06:33,080 --> 00:06:36,990
at føje den til sorteret del af listen.

130
00:06:36,990 --> 00:06:40,030
Når vi har en algoritme, til et vigtigt spørgsmål spørge

131
00:06:40,030 --> 00:06:43,370
os selv som programmører er hvor lang tid tog det tage?

132
00:06:43,370 --> 00:06:46,970
Vi vil først spørge, hvor lang tid tager det for denne

133
00:06:46,970 --> 00:06:50,070
algoritme til at køre i værste fald?

134
00:06:50,070 --> 00:06:51,640
Husker vi repræsenterer dette løb

135
00:06:51,640 --> 00:06:55,060
tid med store O notation.

136
00:06:55,060 --> 00:06:58,650
For at bestemme den minimale usorteret element, vi

137
00:06:58,650 --> 00:07:01,880
hovedsageligt skulle sammenligne hvert element på listen for at

138
00:07:01,880 --> 00:07:04,040
hver andet element i listen.

139
00:07:04,040 --> 00:07:08,430
Intuitivt dette lyder som en O n kvadreret operation.

140
00:07:08,430 --> 00:07:12,050
Ser man på vores pseudokode, har vi også en løkke indlejret i

141
00:07:12,050 --> 00:07:14,420
en anden sløjfe, som faktisk lyder som en O

142
00:07:14,420 --> 00:07:16,480
n kvadreret funktion.

143
00:07:16,480 --> 00:07:19,250
Men husk, at vi ikke behøvede at kigge over

144
00:07:19,250 --> 00:07:23,460
hele listen ved fastsættelsen af ​​mindstebeløbet usorteret element?

145
00:07:23,460 --> 00:07:26,600
Når vi vidste, at 4 blev sorteret, for eksempel, havde vi ikke

146
00:07:26,600 --> 00:07:28,170
nødt til at se på det igen.

147
00:07:28,170 --> 00:07:31,020
Så betyder det lavere køretid?

148
00:07:31,020 --> 00:07:34,510
For vores liste over længde 6, havde vi brug for at lave fem

149
00:07:34,510 --> 00:07:37,990
sammenligninger for det første element, fire sammenligninger for

150
00:07:37,990 --> 00:07:40,750
det andet element, og så videre.

151
00:07:40,750 --> 00:07:44,690
Det betyder, at det samlede antal af trin er summen af

152
00:07:44,690 --> 00:07:49,160
de hele tal fra 1 til længden af ​​listen minus 1.

153
00:07:49,160 --> 00:07:51,005
Vi kan repræsentere dette med en summation.

154
00:07:57,980 --> 00:07:59,910
Vi vil ikke gå ind i summationer her.

155
00:07:59,910 --> 00:08:04,900
Men det viser sig, at denne summation er lig med n gange

156
00:08:04,900 --> 00:08:07,540
n minus 1 over 2.

157
00:08:07,540 --> 00:08:14,220
Eller ækvivalent, n kvadreret over 2 minus n over 2.

158
00:08:14,220 --> 00:08:18,860
Når vi taler om asymptotisk runtime, denne n kvadreret udtryk

159
00:08:18,860 --> 00:08:22,070
vil dominere dette n sigt.

160
00:08:22,070 --> 00:08:27,850
Så selection slags er O n potens.

161
00:08:27,850 --> 00:08:31,460
Husk på, at i vores eksempel, udvælgelse slags stadig behov for

162
00:08:31,460 --> 00:08:33,850
kontrollere, om et nummer, der allerede var sorteret

163
00:08:33,850 --> 00:08:35,450
nødvendig for at blive flyttet.

164
00:08:35,450 --> 00:08:38,929
Så det betyder, at hvis vi kørte udvælgelse slags over en allerede

165
00:08:38,929 --> 00:08:43,070
sorteret liste, ville det kræve det samme antal skridt, da det

166
00:08:43,070 --> 00:08:46,340
ville, når du kører over et helt usorteret liste.

167
00:08:46,340 --> 00:08:51,470
Så selection art har en bedste fald udførelse af n kvadreret,

168
00:08:51,470 --> 00:08:56,820
som vi repræsenterer med omega n potens.

169
00:08:56,820 --> 00:08:58,600
Og det er det for udvælgelse slags.

170
00:08:58,600 --> 00:09:00,630
Blot én af de mange algoritmer, vi kan

171
00:09:00,630 --> 00:09:02,390
bruge til at sortere en liste.

172
00:09:02,390 --> 00:09:05,910
Mit navn er Tommy, og dette er CS50.