1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] Tommy: Kom ons neem 'n blik op die seleksie soort, 'n algoritme

2
00:00:09,980 --> 00:00:12,800
vir die neem van 'n lys van getalle en sorteer hulle.

3
00:00:12,800 --> 00:00:15,750
'N algoritme, onthou, is eenvoudig 'n stap-vir-stap

4
00:00:15,750 --> 00:00:18,370
prosedure vir die totstandbrenging van 'n taak.

5
00:00:18,370 --> 00:00:21,470
Die basiese idee agter die seleksie soort is te verdeel

6
00:00:21,470 --> 00:00:23,390
ons lys in twee gedeeltes

7
00:00:23,390 --> 00:00:26,810
'n gesorteer gedeelte en 'n ongesorteerde gedeelte.

8
00:00:26,810 --> 00:00:30,200
By elke stap van die algoritme, is 'n aantal verskuif vanaf die

9
00:00:30,200 --> 00:00:33,800
ongesorteerde gedeelte na die gesorteerde gedeelte totdat uiteindelik die

10
00:00:33,800 --> 00:00:35,880
hele lys is gesorteer.

11
00:00:35,880 --> 00:00:38,510
So hier is 'n lys van ses nommers -

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

13
00:00:44,010 --> 00:00:47,680
Nou die hele lys word beskou as ongesorteerde data.

14
00:00:47,680 --> 00:00:51,770
Selfs al is 'n aantal soos 16 kan reeds in die korrekte

15
00:00:51,770 --> 00:00:56,040
plek, ons algoritme het geen manier om te weet dat, totdat die

16
00:00:56,040 --> 00:00:57,980
hele lys is gesorteer.

17
00:00:57,980 --> 00:01:01,355
So ons sal elke nommer ongesorteerde oorweeg word totdat ons sorteer

18
00:01:01,355 --> 00:01:03,800
dit self.

19
00:01:03,800 --> 00:01:06,890
Ons weet dat ons wil die lys te wees in stygende orde.

20
00:01:06,890 --> 00:01:10,200
So ons sal wil bou aan die gesorteerde gedeelte van ons lys

21
00:01:10,200 --> 00:01:13,280
van links na regs, die kleinste tot die grootste.

22
00:01:13,280 --> 00:01:17,970
Om dit te doen, moet ons die minimum ongesorteerde element te vind

23
00:01:17,970 --> 00:01:21,350
en sit dit aan die einde van die gesorteerde gedeelte.

24
00:01:21,350 --> 00:01:25,370
Aangesien hierdie lys nie gesorteer, die enigste manier om dit te doen is om te

25
00:01:25,370 --> 00:01:29,330
kyk na elke element in die ongesorteerde gedeelte, onthou

26
00:01:29,330 --> 00:01:32,010
Watter element is die laagste en vergelyk

27
00:01:32,010 --> 00:01:33,770
elke element dat.

28
00:01:33,770 --> 00:01:36,150
So sal ons eers kyk na die 23.

29
00:01:36,150 --> 00:01:38,650
Dit is die eerste element wat ons gesien het, so sal ons onthou

30
00:01:38,650 --> 00:01:40,050
dit as die minimum.

31
00:01:40,050 --> 00:01:42,320
Volgende sal ons kyk na 42.

32
00:01:42,320 --> 00:01:46,720
42 is groter as 23, so 23 is nog steeds die minimum.

33
00:01:46,720 --> 00:01:51,210
Volgende is die 4 wat is minder as 23, so ons sal onthou 4

34
00:01:51,210 --> 00:01:52,880
as die nuwe minimum.

35
00:01:52,880 --> 00:01:56,380
Volgende is 16 wat is groter as 4, so 4

36
00:01:56,380 --> 00:01:57,980
is nog steeds die minimum.

37
00:01:57,980 --> 00:02:03,670
8 is groter as 4 en 15 is groter as 4, so 4 moet

38
00:02:03,670 --> 00:02:05,980
die kleinste ongesorteerde element.

39
00:02:05,980 --> 00:02:09,350
So selfs al is ons as mense kan onmiddellik sien dat 4 is

40
00:02:09,350 --> 00:02:12,300
die minimum element, ons algoritme nodig het om na te kyk

41
00:02:12,300 --> 00:02:15,710
elke ongesorteerde element, selfs nadat ons die 4 gevind het - die

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

43
00:02:16,860 --> 00:02:19,900
So nou dat ons die minimum element, 4 gevind het, sal ons wil

44
00:02:19,900 --> 00:02:23,410
om dit te skuif in die gesorteerde gedeelte van die lys.

45
00:02:23,410 --> 00:02:27,320
Want dit is die eerste stap, dit beteken dat ons wil 4 te stel

46
00:02:27,320 --> 00:02:29,680
die begin van die lys.

47
00:02:29,680 --> 00:02:33,040
Reg nou 23 is aan die begin van die lys, so

48
00:02:33,040 --> 00:02:36,080
Kom ons ruil die 4 en die 23.

49
00:02:36,080 --> 00:02:38,870
So nou is ons lys lyk.

50
00:02:38,870 --> 00:02:42,710
Ons weet dat 4 moet in sy finale plek, want dit is

51
00:02:42,710 --> 00:02:45,890
beide die kleinste element en die element aan die begin

52
00:02:45,890 --> 00:02:46,960
van die lys.

53
00:02:46,960 --> 00:02:50,650
Dit beteken dus dat ons nooit nodig om dit weer te beweeg.

54
00:02:50,650 --> 00:02:53,910
So laat ons herhaal hierdie proses om 'n ander element te voeg aan die

55
00:02:53,910 --> 00:02:55,910
gesorteer gedeelte van die lys.

56
00:02:55,910 --> 00:02:58,950
Ons weet dat ons nie nodig het om te kyk na die 4, want dit is

57
00:02:58,950 --> 00:03:00,000
reeds gesorteer.

58
00:03:00,000 --> 00:03:03,540
Sodat ons kan begin by die 42, wat ons sal onthou as die

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

60
00:03:05,290 --> 00:03:08,700
So, volgende sal ons kyk na die 23 wat minder as 42, so ons

61
00:03:08,700 --> 00:03:11,620
Onthou 23 is die nuwe minimum.

62
00:03:11,620 --> 00:03:14,870
Volgende sien ons die 16 wat minder is as 23, so

63
00:03:14,870 --> 00:03:16,800
16 is die nuwe minimum.

64
00:03:16,800 --> 00:03:19,720
Nou kyk ons ​​by die 8 wat minder is as 16, so

65
00:03:19,720 --> 00:03:21,130
8 is die nuwe minimum.

66
00:03:21,130 --> 00:03:25,900
En laastens 8 is minder as 15, so ons weet dat die 8 is 'n minimum

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

68
00:03:27,780 --> 00:03:30,660
So dit beteken dat ons 8 voeg aan die gesorteerde

69
00:03:30,660 --> 00:03:32,450
gedeelte van die lys.

70
00:03:32,450 --> 00:03:35,990
Reg nou 4 is die enigste gesorteer element, so ons wil te plaas

71
00:03:35,990 --> 00:03:38,410
die 8 volgende aan die 4.

72
00:03:38,410 --> 00:03:41,920
Sedert 42 is die eerste element in die ongesorteerde gedeelte van die

73
00:03:41,920 --> 00:03:47,260
lys, sal ons wil die 42 en die 8 te ruil.

74
00:03:47,260 --> 00:03:49,680
So nou is ons lys lyk.

75
00:03:49,680 --> 00:03:53,830
4 en 8 verteenwoordig die gesorteerde gedeelte van die lys, en die

76
00:03:53,830 --> 00:03:56,440
oorblywende getalle verteenwoordig die ongesorteerde

77
00:03:56,440 --> 00:03:58,260
gedeelte van die lys.

78
00:03:58,260 --> 00:04:00,630
So laat ons voortgaan met 'n ander iterasie.

79
00:04:00,630 --> 00:04:03,850
Ons begin met 23 hierdie tyd, want ons hoef nie te kyk na

80
00:04:03,850 --> 00:04:05,770
die 4 en die 8 nie, want hulle het

81
00:04:05,770 --> 00:04:07,660
reeds gesorteer.

82
00:04:07,660 --> 00:04:10,270
16 is minder as 23, so ons sal onthou

83
00:04:10,270 --> 00:04:12,070
16 as die nuwe minimum.

84
00:04:12,070 --> 00:04:18,149
16 is minder as 42, maar 15 is minder as 16, so 15 moet

85
00:04:18,149 --> 00:04:20,480
die minimum ongesorteerde element.

86
00:04:20,480 --> 00:04:24,580
So nou het ons wil die 15 en die 23 tot te ruil

87
00:04:24,580 --> 00:04:26,310
gee ons hierdie lys.

88
00:04:26,310 --> 00:04:30,500
Die gesorteer gedeelte van die lys bestaan ​​uit 4, 8 en 15, en

89
00:04:30,500 --> 00:04:33,210
hierdie elemente is nog steeds ongesorteerde data.

90
00:04:33,210 --> 00:04:36,900
Maar dit gebeur net so dat die volgende ongesorteerde element, 16,

91
00:04:36,900 --> 00:04:38,480
is reeds gesorteer.

92
00:04:38,480 --> 00:04:42,060
Daar is egter geen manier vir ons algoritme om te weet dat 16

93
00:04:42,060 --> 00:04:45,230
is reeds in sy regte plek, so het ons nog nodig het om te

94
00:04:45,230 --> 00:04:47,870
presies dieselfde proses herhaal.

95
00:04:47,870 --> 00:04:53,750
So sien ons dat 16 is minder as 42, en 16 is minder as 23, so

96
00:04:53,750 --> 00:04:56,230
16 moet die minimum element.

97
00:04:56,230 --> 00:04:59,010
Dit is onmoontlik om hierdie element te ruil met homself, sodat ons kan

98
00:04:59,010 --> 00:05:01,780
laat dit eenvoudig in hierdie plek.

99
00:05:01,780 --> 00:05:04,660
So ons moet een meer slaag van ons algoritme.

100
00:05:04,660 --> 00:05:09,370
42 is meer as 23, so 23 moet wees om die

101
00:05:09,370 --> 00:05:10,970
minimum ongesorteerde element.

102
00:05:10,970 --> 00:05:17,410
Sodra ons ruil die 23 en die 42, eindig ons met ons finale

103
00:05:17,410 --> 00:05:18,530
gesorteerde lys -

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

105
00:05:23,390 --> 00:05:26,830
Ons weet 42 moet in die korrekte plek, want dit is die

106
00:05:26,830 --> 00:05:30,210
enigste element is links, en dit is 'n seleksie soort.

107
00:05:30,210 --> 00:05:32,100
Kom ons kyk nou formaliseer ons algoritme met 'n paar

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

109
00:05:34,540 --> 00:05:37,760
On line een, kan ons sien dat ons nodig het om te integreer oor

110
00:05:37,760 --> 00:05:39,530
elke element van die lys.

111
00:05:39,530 --> 00:05:42,150
Behalwe die laaste element, want die 1 element

112
00:05:42,150 --> 00:05:44,230
lys is reeds gesorteer.

113
00:05:44,230 --> 00:05:48,100
On line twee, ons kyk na die eerste element van die unsorted

114
00:05:48,100 --> 00:05:51,080
gedeelte van die lys te wees van die minimum, soos ons gedoen het met ons

115
00:05:51,080 --> 00:05:53,750
byvoorbeeld, so ons het iets om te vergelyk.

116
00:05:53,750 --> 00:05:57,260
Lyn drie begin 'n tweede rondte wat ons itereer oor

117
00:05:57,260 --> 00:05:59,170
elke ongesorteerde element.

118
00:05:59,170 --> 00:06:02,150
Ons weet dat na i iterasies, die gesorteerde gedeelte

119
00:06:02,150 --> 00:06:05,330
van ons lys moet ek elemente in dit sedert elke stap

120
00:06:05,330 --> 00:06:06,890
vorme een element.

121
00:06:06,890 --> 00:06:11,770
Dus is die eerste ongesorteerde element moet in posisie i plus 1.

122
00:06:11,770 --> 00:06:15,440
On line vier ons dit vergelyk met die huidige element tot die minimum

123
00:06:15,440 --> 00:06:17,750
element wat ons tot dusver gesien het.

124
00:06:17,750 --> 00:06:20,560
Indien die huidige element is kleiner as die minimum

125
00:06:20,560 --> 00:06:23,870
element, dan onthou ons die huidige element as die nuwe

126
00:06:23,870 --> 00:06:26,250
minimum on line vyf.

127
00:06:26,250 --> 00:06:29,900
Ten slotte, op die lyne ses en sewe, ruil ons die minimum

128
00:06:29,900 --> 00:06:33,080
element met die eerste ongesorteerde element, en daardeur

129
00:06:33,080 --> 00:06:36,990
toe te voeg aan die gesorteerde gedeelte van die lys.

130
00:06:36,990 --> 00:06:40,030
Sodra ons 'n algoritme, 'n belangrike vraag te vra

131
00:06:40,030 --> 00:06:43,370
onsself as programmeerders hoe lank het dit neem?

132
00:06:43,370 --> 00:06:46,970
Ons sal eers die vraag vra hoe lank neem dit vir hierdie

133
00:06:46,970 --> 00:06:50,070
algoritme uit te voer in die ergste geval?

134
00:06:50,070 --> 00:06:51,640
Onthou ons verteenwoordig die verloop

135
00:06:51,640 --> 00:06:55,060
tyd met die groot O notasie.

136
00:06:55,060 --> 00:06:58,650
Ten einde die minimum ongesorteerde element te bepaal, het ons

137
00:06:58,650 --> 00:07:01,880
wese het elke element in die lys te vergelyk

138
00:07:01,880 --> 00:07:04,040
elke ander element in die lys.

139
00:07:04,040 --> 00:07:08,430
Intuïtief, dit klink soos 'n O van n kwadraat werking.

140
00:07:08,430 --> 00:07:12,050
Op soek na ons pseudokode, ons het ook 'n lus geneste binne

141
00:07:12,050 --> 00:07:14,420
nog 'n lus, wat inderdaad klink soos 'n O

142
00:07:14,420 --> 00:07:16,480
van n kwadraat werking.

143
00:07:16,480 --> 00:07:19,250
Egter onthou dat ons nie nodig het om te kyk oor die

144
00:07:19,250 --> 00:07:23,460
volledige lys by die bepaling van die minimum ongesorteerde element?

145
00:07:23,460 --> 00:07:26,600
Sodra ons het geweet dat die 4 gesorteer, byvoorbeeld, ons het nie

146
00:07:26,600 --> 00:07:28,170
nodig het om te kyk na dit weer.

147
00:07:28,170 --> 00:07:31,020
So doen dit laer die loop van die tyd?

148
00:07:31,020 --> 00:07:34,510
Vir 'n lys van lengte 6, ons nodig het vyf te maak

149
00:07:34,510 --> 00:07:37,990
vergelykings vir die eerste element, vier vergelykings vir

150
00:07:37,990 --> 00:07:40,750
die tweede element, en so aan.

151
00:07:40,750 --> 00:07:44,690
Dit beteken dat die totale aantal van die stappe is die som van

152
00:07:44,690 --> 00:07:49,160
die heelgetalle van 1 tot die lengte van die lys minus 1.

153
00:07:49,160 --> 00:07:51,005
Ons kan verteenwoordig hierdie met 'n opsomming.

154
00:07:57,980 --> 00:07:59,910
Ons sal nie gaan in die opsommings hier.

155
00:07:59,910 --> 00:08:04,900
Maar dit blyk dat hierdie opsomming is gelyk aan n keer

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

157
00:08:07,540 --> 00:08:14,220
Of gelykerwys, n oor 2 vierkant minus n oor 2.

158
00:08:14,220 --> 00:08:18,860
Wanneer praat oor die asimptotiese runtime, n kwadraat term

159
00:08:18,860 --> 00:08:22,070
gaan hierdie n term te oorheers.

160
00:08:22,070 --> 00:08:27,850
So seleksie soort van n kwadraat O is.

161
00:08:27,850 --> 00:08:31,460
Onthou dat in ons voorbeeld, seleksie soort nog nodig om te

162
00:08:31,460 --> 00:08:33,850
Kontroleer of die nommer wat reeds gesorteer

163
00:08:33,850 --> 00:08:35,450
wat nodig is om te verskuif word.

164
00:08:35,450 --> 00:08:38,929
So dit beteken dat as ons seleksie soort gehardloop oor 'n reeds

165
00:08:38,929 --> 00:08:43,070
gesorteerde lys, sou dit dieselfde aantal stappe soos dit vereis

166
00:08:43,070 --> 00:08:46,340
sou wanneer jy loop oor 'n heeltemal ongesorteerde lys.

167
00:08:46,340 --> 00:08:51,470
So seleksie soort het 'n beste geval prestasie van n kwadraat,

168
00:08:51,470 --> 00:08:56,820
wat ons met omega n kwadraat.

169
00:08:56,820 --> 00:08:58,600
En dit is dit vir keuring soort.

170
00:08:58,600 --> 00:09:00,630
Net een van die vele algoritmes wat ons kan

171
00:09:00,630 --> 00:09:02,390
gebruik om 'n lys te sorteer.

172
00:09:02,390 --> 00:09:05,910
My naam is Tommy, en dit is cs50.