1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: dezagun hautaketa sort begirada, algoritmo bat

2
00:00:09,980 --> 00:00:12,800
zenbakien zerrenda bat hartu eta hauek ordenatzeko.

3
00:00:12,800 --> 00:00:15,750
Algoritmo bat, gogoratu besterik ez da, urrats-urrats

4
00:00:15,750 --> 00:00:18,370
zeregin bat lortzeko prozedura.

5
00:00:18,370 --> 00:00:21,470
Aukeraketa sort oinarrizko ideia da zatitzea

6
00:00:21,470 --> 00:00:23,390
gure bi zatiak sartu zerrenda -

7
00:00:23,390 --> 00:00:26,810
ordenatuko zati bat eta Unsorted zati bat.

8
00:00:26,810 --> 00:00:30,200
Algoritmoaren urrats bakoitzean, zenbaki bat da, mugitu

9
00:00:30,200 --> 00:00:33,800
Unsorted ordenatuko zati zati azkenean arte

10
00:00:33,800 --> 00:00:35,880
zerrenda osoa ordenatuko da.

11
00:00:35,880 --> 00:00:38,510
Beraz, hona hemen sei zenbakien zerrenda bat da -

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

13
00:00:44,010 --> 00:00:47,680
Oraintxe zerrenda osoa Unsorted jotzen da.

14
00:00:47,680 --> 00:00:51,770
Nahiz eta 16 bezalako zenbaki bat dagoeneko bere zuzena

15
00:00:51,770 --> 00:00:56,040
kokapena, gure algoritmoa modu hori ezagutu arte ez du

16
00:00:56,040 --> 00:00:57,980
zerrenda osoa ordenatuko da.

17
00:00:57,980 --> 00:01:01,355
Beraz, zenbaki bakoitzeko kontuan dugu Unsorted ordenatzeko arte

18
00:01:01,355 --> 00:01:03,800
da geure buruari.

19
00:01:03,800 --> 00:01:06,890
Zerrenda ordena gorakorrean izan nahi dugun jakin dugu.

20
00:01:06,890 --> 00:01:10,200
Beraz, nahi gure zerrendaren zati ordenatuko sortu dugu

21
00:01:10,200 --> 00:01:13,280
ezkerretik eskuinera, handiena txikiena.

22
00:01:13,280 --> 00:01:17,970
Horretarako, gutxieneko elementu Unsorted behar dugu

23
00:01:17,970 --> 00:01:21,350
eta jarri, ordenatzen zati amaieran.

24
00:01:21,350 --> 00:01:25,370
Zerrenda hau ez da horrela antolatu zenetik, horretarako modu bakarra da

25
00:01:25,370 --> 00:01:29,330
Unsorted zati, elementu bakoitzaren begiratu gogoratzeko

26
00:01:29,330 --> 00:01:32,010
elementu da txikiena eta alderatuz

27
00:01:32,010 --> 00:01:33,770
duten elementu bakoitza.

28
00:01:33,770 --> 00:01:36,150
Beraz, lehen 23 begiratu dugu.

29
00:01:36,150 --> 00:01:38,650
Elementu lehenengo ikusten dugu, beraz, gogoan izan dugu

30
00:01:38,650 --> 00:01:40,050
gutxieneko bezala.

31
00:01:40,050 --> 00:01:42,320
Hurrengo 42 bilatuko dugu.

32
00:01:42,320 --> 00:01:46,720
42 23 baino handiagoa da, eta, beraz, 23 izango dira gutxienez.

33
00:01:46,720 --> 00:01:51,210
Next 4 eta 23 baino gutxiago da, beraz, 4 gogoratzen dugu

34
00:01:51,210 --> 00:01:52,880
gutxieneko gisa.

35
00:01:52,880 --> 00:01:56,380
Hurrengoa 16 eta 4 baino handiagoa da, eta, beraz, 4

36
00:01:56,380 --> 00:01:57,980
da, oraindik ere, gutxienez.

37
00:01:57,980 --> 00:02:03,670
8 4 baino handiagoa da, eta 15 4 baino handiagoa da, 4 izan behar du, beraz,

38
00:02:03,670 --> 00:02:05,980
Unsorted elementu txikiena.

39
00:02:05,980 --> 00:02:09,350
Beraz, nahiz eta gizakiak berehala dezakegu ikusteko 4 dela

40
00:02:09,350 --> 00:02:12,300
gutxieneko elementu, gure algoritmoa behar begiratzen

41
00:02:12,300 --> 00:02:15,710
Unsorted elementu behin, ondoren ere aurkitu dugu, 4 -

42
00:02:15,710 --> 00:02:16,860
gutxieneko elementu.

43
00:02:16,860 --> 00:02:19,900
Beraz, gaur egun, gutxieneko elementu, 4 aurkitu ditudan dugu, nahi dugu.

44
00:02:19,900 --> 00:02:23,410
mugitzeko zerrendaren zati ordenatzen sartu.

45
00:02:23,410 --> 00:02:27,320
Hau lehen urratsa da, horrek esan nahi du, 4 jarri nahi dugu

46
00:02:27,320 --> 00:02:29,680
zerrendaren hasieran.

47
00:02:29,680 --> 00:02:33,040
Oraintxe bertan 23 zerrendaren hasieran da, eta, beraz,

48
00:02:33,040 --> 00:02:36,080
dezagun swap 4 eta 23.

49
00:02:36,080 --> 00:02:38,870
Beraz, orain, gure zerrenda hau atsegin du.

50
00:02:38,870 --> 00:02:42,710
4 izan behar duela bere kokapena azken ezagutzen dugu, delako

51
00:02:42,710 --> 00:02:45,890
txikiena biak elementu eta elementu hasieran

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

53
00:02:46,960 --> 00:02:50,650
Honek esan nahi du, beraz, ez dugu inoiz berriro eraman beharko.

54
00:02:50,650 --> 00:02:53,910
Hargatik errepikatu prozesu honetan beste elementu bat gehitzeko

55
00:02:53,910 --> 00:02:55,910
ordenatuko zerrendaren zati.

56
00:02:55,910 --> 00:02:58,950
4 begiratu behar ez dugun ezagutzen dugu, delako

57
00:02:58,950 --> 00:03:00,000
Dagoeneko ordenatuko da.

58
00:03:00,000 --> 00:03:03,540
Beraz, 42 hasi ahal izango dugu, bezala gogoratzen dugu

59
00:03:03,540 --> 00:03:05,290
gutxieneko elementu.

60
00:03:05,290 --> 00:03:08,700
Beraz, hurrengo 23 eta 42 baino gutxiago bilatuko dugu, beraz,

61
00:03:08,700 --> 00:03:11,620
gogoratu 23 gutxieneko berria da.

62
00:03:11,620 --> 00:03:14,870
16, hau da, 23 baino gutxiago ikusiko dugu, eta, beraz,

63
00:03:14,870 --> 00:03:16,800
16 gutxieneko berria da.

64
00:03:16,800 --> 00:03:19,720
Orain 8 baino 16 gutxiago ikusi dugu, eta, beraz,

65
00:03:19,720 --> 00:03:21,130
8 gutxieneko berria da.

66
00:03:21,130 --> 00:03:25,900
Eta, azkenik, 8 15 baino gutxiago da, beraz, 8 gutxienez badakigu

67
00:03:25,900 --> 00:03:27,780
Unsorted elementu.

68
00:03:27,780 --> 00:03:30,660
Beraz, horrek esan nahi du 8 erantsi behar dugu ordenatzen

69
00:03:30,660 --> 00:03:32,450
zerrendaren zati.

70
00:03:32,450 --> 00:03:35,990
Oraintxe 4 ordenatuko elementu bakarra da, beraz, jarri nahi dugu

71
00:03:35,990 --> 00:03:38,410
8 next 4.

72
00:03:38,410 --> 00:03:41,920
42 geroztik Unsorted zatia lehenengo elementua da

73
00:03:41,920 --> 00:03:47,260
zerrendan, 42 eta 8 swap nahi dugu.

74
00:03:47,260 --> 00:03:49,680
Beraz, orain, gure zerrenda hau atsegin du.

75
00:03:49,680 --> 00:03:53,830
4 eta 8 zerrendaren zati horrela antolatu, eta

76
00:03:53,830 --> 00:03:56,440
Gainerako zenbakiak irudikatzeko Unsorted

77
00:03:56,440 --> 00:03:58,260
zerrendaren zati.

78
00:03:58,260 --> 00:04:00,630
Hargatik iterazio beste batekin jarraitzeko.

79
00:04:00,630 --> 00:04:03,850
23 Une honetan, ez dugu, ez baita behar begiratzen

80
00:04:03,850 --> 00:04:05,770
4 eta 8 gehiago dut dutelako

81
00:04:05,770 --> 00:04:07,660
dagoeneko ordenatuko da.

82
00:04:07,660 --> 00:04:10,270
16 23 baino gutxiago da, beraz, gogoan izan dugu

83
00:04:10,270 --> 00:04:12,070
16 gutxienez berria.

84
00:04:12,070 --> 00:04:18,149
16 42 baino gutxiago da, baina 15 baino 16 gutxiago, eta, beraz, 15 izan behar du

85
00:04:18,149 --> 00:04:20,480
gutxieneko elementu Unsorted.

86
00:04:20,480 --> 00:04:24,580
Beraz, gaur egun, 15 eta 23 swap nahi dugu

87
00:04:24,580 --> 00:04:26,310
ematen diguten zerrenda honetan.

88
00:04:26,310 --> 00:04:30,500
Zerrendaren zati ordenatuko 4, 8 eta 15 osatzen dute, eta

89
00:04:30,500 --> 00:04:33,210
elementu horiek oraindik Unsorted.

90
00:04:33,210 --> 00:04:36,900
Baina besterik ez da gertatzen hurrengo Unsorted elementu, 16,

91
00:04:36,900 --> 00:04:38,480
dagoeneko ordenatuko da.

92
00:04:38,480 --> 00:04:42,060
Hala eta guztiz ere, ez dago modurik gure algoritmoa jakin 16 dela

93
00:04:42,060 --> 00:04:45,230
dagoeneko bere kokapena zuzena da, beraz, oraindik behar dugu

94
00:04:45,230 --> 00:04:47,870
errepikatu prozesua bera.

95
00:04:47,870 --> 00:04:53,750
Beraz, 16 42 baino gutxiago dela ikusiko dugu, eta 16 baino gutxiago 23 eta, beraz,

96
00:04:53,750 --> 00:04:56,230
16 gutxieneko elementu izan behar du.

97
00:04:56,230 --> 00:04:59,010
Ezinezkoa da, berez elementu honen trukatu, gaitezke, beraz

98
00:04:59,010 --> 00:05:01,780
utz kokapen honetan.

99
00:05:01,780 --> 00:05:04,660
Beraz, gure algoritmoa pass bat gehiago behar dugu.

100
00:05:04,660 --> 00:05:09,370
42 23 baino handiagoa da, eta, beraz, 23 izan behar du

101
00:05:09,370 --> 00:05:10,970
gutxieneko Unsorted elementu.

102
00:05:10,970 --> 00:05:17,410
Ondoren, 23 eta 42 trukatu dugu, amaituko dugu gure azken

103
00:05:17,410 --> 00:05:18,530
ordenatuko zerrenda -

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

105
00:05:23,390 --> 00:05:26,830
42 leku egokian egon behar da geroztik ezagutzen dugu

106
00:05:26,830 --> 00:05:30,210
elementu bakarra utzi, eta duten aukeraketa ordenatu.

107
00:05:30,210 --> 00:05:32,100
Dezagun gure algoritmoa batzuk formalizatzeko

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

109
00:05:34,540 --> 00:05:37,760
On line bat, ikusi behar dugun integratzeko dezakegu

110
00:05:37,760 --> 00:05:39,530
zerrendako elementu guztiak.

111
00:05:39,530 --> 00:05:42,150
Azken elementu izan ezik, izan ere, 1 elementua

112
00:05:42,150 --> 00:05:44,230
zerrenda dagoeneko ordenatuko da.

113
00:05:44,230 --> 00:05:48,100
On line bi, Unsorted, lehenengo elementua kontuan hartzen badugu

114
00:05:48,100 --> 00:05:51,080
zerrendaren zati minimoa izan da, gure genuen bezala

115
00:05:51,080 --> 00:05:53,750
Adibidez, eta, beraz, zerbait alderatu dugu.

116
00:05:53,750 --> 00:05:57,260
Line hiru bigarren begizta hasten den zehar batetik bestera joateko dugu

117
00:05:57,260 --> 00:05:59,170
Unsorted elementu bakoitza.

118
00:05:59,170 --> 00:06:02,150
Badakigu, i iterazio ondoren, ordenatuko zati

119
00:06:02,150 --> 00:06:05,330
gure zerrendan elementu i Urrats bakoitzak izan behar

120
00:06:05,330 --> 00:06:06,890
era askotako elementu bat.

121
00:06:06,890 --> 00:06:11,770
Beraz, lehen Unsorted elementu behar posizioa i gehi 1 izango da.

122
00:06:11,770 --> 00:06:15,440
Lau On line, oraingo elementu alderatu dugu gutxieneko

123
00:06:15,440 --> 00:06:17,750
dut ikusi dugun elementu hain urruti.

124
00:06:17,750 --> 00:06:20,560
Uneko elementu minimoa baino txikiagoa bada

125
00:06:20,560 --> 00:06:23,870
elementu, ondoren, gaur egungo elementu berri bezala gogoratzen dugu

126
00:06:23,870 --> 00:06:26,250
line bost gutxienez.

127
00:06:26,250 --> 00:06:29,900
Azkenik, sei eta zazpi. Lerroak, gutxieneko swap dugu

128
00:06:29,900 --> 00:06:33,080
elementu Unsorted lehen elementu eta, horrela,

129
00:06:33,080 --> 00:06:36,990
zerrendaren zati ordenatuko gehituz.

130
00:06:36,990 --> 00:06:40,030
Dugu algoritmo bat ondoren, galdera garrantzitsu bat eskatu

131
00:06:40,030 --> 00:06:43,370
programatzaile gisa geure buruari zenbat denbora ez hartu?

132
00:06:43,370 --> 00:06:46,970
Eskatzen dugu lehenik eta behin galdera zenbat denbora ez hartu hau

133
00:06:46,970 --> 00:06:50,070
algoritmoaren kasu txarrena exekutatu?

134
00:06:50,070 --> 00:06:51,640
Gogorarazten entzierro hau adierazten dugu

135
00:06:51,640 --> 00:06:55,060
O big notazioa denbora.

136
00:06:55,060 --> 00:06:58,650
Ordena gutxieneko Unsorted elementu zehazteko, dugu

137
00:06:58,650 --> 00:07:01,880
funtsean elementu bakoitzaren alderatu izan zerrendan

138
00:07:01,880 --> 00:07:04,040
zerrendako beste elementu bat behin.

139
00:07:04,040 --> 00:07:08,430
Senez, n eragiketa karratu O bat bezalako soinuak hau.

140
00:07:08,430 --> 00:07:12,050
Gure pseudocode begira, izan ere habiaratuak barruan loop

141
00:07:12,050 --> 00:07:14,420
loop beste, hain zuzen ere soinuak O bat bezalako

142
00:07:14,420 --> 00:07:16,480
n eragiketa karratu.

143
00:07:16,480 --> 00:07:19,250
Hala eta guztiz ere, gogoratu baina ez dugu behar baino gehiago begiratu

144
00:07:19,250 --> 00:07:23,460
zerrenda osoa gutxieneko Unsorted elementu erabakigarria?

145
00:07:23,460 --> 00:07:26,600
Bazekien 4 zen horrela antolatu ondoren, adibidez, ez genuen

146
00:07:26,600 --> 00:07:28,170
begiratu behar da berriro ere.

147
00:07:28,170 --> 00:07:31,020
Beraz, hau ez txikiagoa exekutatzen ari den denbora?

148
00:07:31,020 --> 00:07:34,510
Gure zerrenda luzera 6, bost egin behar dugu

149
00:07:34,510 --> 00:07:37,990
lehen elementu konparazioak, lau konparazioak egiteko

150
00:07:37,990 --> 00:07:40,750
Bigarren elementua, eta abar.

151
00:07:40,750 --> 00:07:44,690
Horrek esan nahi du, urratsen kopuru osoa batura da

152
00:07:44,690 --> 00:07:49,160
Osoko zenbaki 1etik zerrenda ken 1 luzera.

153
00:07:49,160 --> 00:07:51,005
Summation bat irudikatu ahal izango dugu.

154
00:07:57,980 --> 00:07:59,910
Ez dugu summations sartu hemen.

155
00:07:59,910 --> 00:08:04,900
Baina bihurtzen da summation hori n aldiz berdina

156
00:08:04,900 --> 00:08:07,540
n ken 1 2 baino gehiago.

157
00:08:07,540 --> 00:08:14,220
Edo equivalently, n 2 baino gehiagoko minus n 2 baino gehiago karratu.

158
00:08:14,220 --> 00:08:18,860
Exekuzio asymptotic buruz hitz egiten denean, epe karratu n

159
00:08:18,860 --> 00:08:22,070
n epe honetan menderatzeko.

160
00:08:22,070 --> 00:08:27,850
Beraz, aukeraketa sort O n karratu.

161
00:08:27,850 --> 00:08:31,460
Gogoratu gure Adibidez, hautaketa ordena oraindik behar

162
00:08:31,460 --> 00:08:33,850
egiaztatu zen kopuru hori dagoeneko horrela antolatu bada

163
00:08:33,850 --> 00:08:35,450
mugitu behar dira.

164
00:08:35,450 --> 00:08:38,929
Beraz, horrek esan nahi du ran aukeraketa sort bat dagoeneko baino gehiago

165
00:08:38,929 --> 00:08:43,070
ordenatuko da zerrenda, urratsen kopuru bera behar luke

166
00:08:43,070 --> 00:08:46,340
litzateke zerrenda erabat Unsorted baino gehiago exekutatzen ari denean.

167
00:08:46,340 --> 00:08:51,470
Beraz, aukeraketa sort n karratu kasuan errendimendu onena du,

168
00:08:51,470 --> 00:08:56,820
omega n karratu dugu.

169
00:08:56,820 --> 00:08:58,600
Eta hori da aukeraketa sort.

170
00:08:58,600 --> 00:09:00,630
Just algoritmoak asko dugu

171
00:09:00,630 --> 00:09:02,390
zerrenda bat erabili ordenatzeko.

172
00:09:02,390 --> 00:09:05,910
Nire izena Tommy da, eta, hau da cs50.