1
00:00:00,000 --> 00:00:03,360
>> [Musika jotzen]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Ondo da, beraz,
burbuila sort algoritmoa da

4
00:00:06,730 --> 00:00:08,730
elementu multzo bat ordenatzeko erabili ahal izango duzu.

5
00:00:08,730 --> 00:00:10,850
Ikus dezagun nola funtzionatzen duen begirada bat.

6
00:00:10,850 --> 00:00:13,240
>> Beraz, oinarrizko ideia atzean
burbuila sort da hau.

7
00:00:13,240 --> 00:00:17,340
Oro har, goi-mailako eraman nahi dugu
baloratzen, oro har, eskubidea elementuak,

8
00:00:17,340 --> 00:00:20,340
eta baloratzen elementu jaistea, oro har,
ezker, jo genuen espero.

9
00:00:20,340 --> 00:00:23,256
Behekoan gauzei egon nahi dugu
hasieran, eta goi-mailako gauzak

10
00:00:23,256 --> 00:00:24,970
amaieran izan.

11
00:00:24,970 --> 00:00:26,130
>> Nola egiten dugu hau?

12
00:00:26,130 --> 00:00:28,040
Beno pseudocode kodea ere,
esan genezake, dezagun

13
00:00:28,040 --> 00:00:30,320
swap ez-zero balio bat kontagailu bat ezartzeko.

14
00:00:30,320 --> 00:00:32,570
Ikusiko dugu zergatik egiten dugun bigarren bat ere.

15
00:00:32,570 --> 00:00:36,090
Eta gero, honako hauek errepikatu dugu
Prozesu swap kontagailua 0 izan arte,

16
00:00:36,090 --> 00:00:39,910
edo swaps ez dugu egin arte guztietan.

17
00:00:39,910 --> 00:00:43,170
>> Berrezarri swap kontagailu
0 ez bada dagoeneko 0.

18
00:00:43,170 --> 00:00:46,420
Ondoren, begiratu at guztietan
ondoko elementu pare.

19
00:00:46,420 --> 00:00:49,550
Bi elementu horiek dira bada
Ez ordenan, trukatzeko,

20
00:00:49,550 --> 00:00:51,620
eta gehitu 1 swap mostradorera.

21
00:00:51,620 --> 00:00:53,870
Zuk pentsatzen bada
hau ikusmenarekin aurretik,

22
00:00:53,870 --> 00:00:57,471
nabarituko hori txikiagoa dela mugituko da
baloratzen ezkerreko elementu

23
00:00:57,471 --> 00:01:00,720
eta goi-mailako baloratzen eskubidea elementuak,
eraginkortasunez zer egin nahi dugun egiten,

24
00:01:00,720 --> 00:01:03,940
hau da, talde horiek mugitu
horrela elementuen.

25
00:01:03,940 --> 00:01:07,035
Dezagun ikusteko nola hau
gure array erabiliz begiratu dezake

26
00:01:07,035 --> 00:01:10,504
Hori probatzeko erabiliko dugu
Algoritmo horien out.

27
00:01:10,504 --> 00:01:13,420
Sailkatu array bat dugu hemen, berriz,
elementu guztiak bidez adierazten

28
00:01:13,420 --> 00:01:14,840
Gorriz izatea.

29
00:01:14,840 --> 00:01:17,970
Eta ezarri dut nire swap counter
nulua balio bat.

30
00:01:17,970 --> 00:01:20,610
Arbitrarioki aukeratu nuen
negatiboa 1-- ez da 0.

31
00:01:20,610 --> 00:01:23,840
Prozesu hau errepikatu nahi dugu
0 da swap counter arte.

32
00:01:23,840 --> 00:01:26,540
Hori dela eta, nire swap ezarri dut
Zero ez balio batzuk kontraerasoan,

33
00:01:26,540 --> 00:01:29,400
Bestela delako
swap counter 0 izango litzateke.

34
00:01:29,400 --> 00:01:31,610
Ez genuke ere hasiko du
Algoritmoaren prozesua.

35
00:01:31,610 --> 00:01:33,610
Beraz, berriro ere, pausoak are--
berrezarri swap mostradorera

36
00:01:33,610 --> 00:01:37,900
0, orduan ondoko bakoitzean begiratu
bikotea, eta ari dira barrutitik kanpo egonez gero,

37
00:01:37,900 --> 00:01:40,514
trukatzeko, eta gehitu 1
swap mostradorera.

38
00:01:40,514 --> 00:01:41,680
Hargatik hasiko prozesu honetan.

39
00:01:41,680 --> 00:01:44,430
Beraz, lehenengo gauza egiten dugu
swap counter ezarri dugu 0,

40
00:01:44,430 --> 00:01:46,660
eta, ondoren, bila hasten gara
aldameneko pare bakoitzean.

41
00:01:46,660 --> 00:01:49,140
>> Beraz, lehen hasten gara 5 eta 2 begira.

42
00:01:49,140 --> 00:01:52,410
Direla daudelarik ikusi dugu
aginduko du eta, beraz, trukatu dugu.

43
00:01:52,410 --> 00:01:53,830
Eta gehitzen badiogu 1 swap mostradorera.

44
00:01:53,830 --> 00:01:57,860
Beraz, orain gure swap counter 1 da,
eta 2 eta 5 aktibatu dira.

45
00:01:57,860 --> 00:01:59,370
Orain, prozesua errepikatu dugu berriro.

46
00:01:59,370 --> 00:02:03,540
>> Begiratu hurrengo aldameneko pare batean gaude,
5 eta 1 halaber ordena Oraindik dute,

47
00:02:03,540 --> 00:02:06,960
beraz, horiek aldatu dugu eta gehitu
1 swap mostradorera.

48
00:02:06,960 --> 00:02:08,900
Ondoren, begiratu 5 eta 3 dugu.

49
00:02:08,900 --> 00:02:13,830
Dira dute ordena, beraz trukatu ditugu
haiek eta guk gehitu 1 swap mostradorera.

50
00:02:13,830 --> 00:02:15,550
Ondoren, begiratu 5 eta 6 dugu.

51
00:02:15,550 --> 00:02:18,630
Oraindik ordena dutela, beraz, ez dugu benetan
trukatzeko ezer une honetan behar.

52
00:02:18,630 --> 00:02:20,250
Ondoren, begiratu 6 eta 4 dugu.

53
00:02:20,250 --> 00:02:24,920
Oraindik ere ordena, beraz trukatu ditugu
haiek eta guk gehitu 1 swap mostradorera.

54
00:02:24,920 --> 00:02:26,230
>> Orain konturatu zer gertatu zen.

55
00:02:26,230 --> 00:02:29,514
Nik egin dugu jauzi 6 modu guztiak amaieran.

56
00:02:29,514 --> 00:02:32,180
Beraz, aukeraketa ordenatu batean, dut ez baduzu
bideo hori ikusi, zer egin genuen

57
00:02:32,180 --> 00:02:35,290
Bukatu dugu mugituz
Eraikin txikiena elementu

58
00:02:35,290 --> 00:02:39,640
ordenatzen array funtsean bertatik
Ezkerretik eskuinera, handiena txikiena.

59
00:02:39,640 --> 00:02:43,200
Burbuila moduko kasuan, berriz, bagaude
Algoritmo bereziki, honako hau,

60
00:02:43,200 --> 00:02:46,720
benetan ari gara eraikitzen joan
eskubidea ordenatuko array

61
00:02:46,720 --> 00:02:49,100
Ezkerretik, handienetik txikienera.

62
00:02:49,100 --> 00:02:53,840
Dute eraginkortasunez bubbled dugu 6an,
balio handiena, amaieran modu guztiak.

63
00:02:53,840 --> 00:02:56,165
>> Eta, beraz, ez dugu orain deklaratu ahal
Hori ordenatuko

64
00:02:56,165 --> 00:02:59,130
eta etorkizun iterations--
array igaro, berriro

65
00:02:59,130 --> 00:03:01,280
ez dugu 6 kontuan hartu behar dira jada.

66
00:03:01,280 --> 00:03:03,850
Kontuan hartu beharreko bakarra daukagu
Unsorted elementu

67
00:03:03,850 --> 00:03:06,299
denean ari gara ondoko bikote begira.

68
00:03:06,299 --> 00:03:08,340
Beraz, inork amaitu dugu
burbuila ordenatu pasatzen.

69
00:03:08,340 --> 00:03:11,941
Beraz, orain, atzera egingo dugu galderari,
errepikatu swap kontagailua 0 izan arte.

70
00:03:11,941 --> 00:03:13,690
Beno swap mostradorera
4 da, beraz goaz

71
00:03:13,690 --> 00:03:15,410
Prozesu hau berriro errepikatuz mantentzeko.

72
00:03:15,410 --> 00:03:19,180
>> Swap counter berrezartzeko goaz
0 eta aldameneko bikote bakoitzak begiratu.

73
00:03:19,180 --> 00:03:21,890
Beraz, hasteko, 2 eta 1 dugu ari dira
ordena, beraz trukatu dugu

74
00:03:21,890 --> 00:03:23,620
eta 1 gehitzen badiogu swap mostradorera.

75
00:03:23,620 --> 00:03:25,490
2 eta 3, ari ordena dutela.

76
00:03:25,490 --> 00:03:27,060
Ez dugu ezer egin behar.

77
00:03:27,060 --> 00:03:28,420
3 eta 5 ematea komeni da.

78
00:03:28,420 --> 00:03:30,150
Ez dugu behar ezer ez egin.

79
00:03:30,150 --> 00:03:32,515
>> 5 eta 4 out dira
ordenaren, eta, beraz, ez dugu

80
00:03:32,515 --> 00:03:35,130
horiek aldatu eta gehitu behar
1 swap mostradorera.

81
00:03:35,130 --> 00:03:38,880
Eta orain mugitu dugu 5
hurrengo elementu handiena da,

82
00:03:38,880 --> 00:03:40,920
Unsorted zati amaierara arte.

83
00:03:40,920 --> 00:03:44,360
Beraz, gaur egun ez diegu
ordenatzen zati zati.

84
00:03:44,360 --> 00:03:47,180
>> Orain ikusten ari zara
pantaila eta seguruenik esango,

85
00:03:47,180 --> 00:03:50,130
Ezin dut, array gisa
oraintxe ordenatuko da.

86
00:03:50,130 --> 00:03:51,820
Baina ezin dugu frogatu duen oraindik.

87
00:03:51,820 --> 00:03:54,359
Ez dugu bermea dute
Dela ordenatuta.

88
00:03:54,359 --> 00:03:56,900
Baina hori da, non swap
counter ari den jokoan sartzen joan.

89
00:03:56,900 --> 00:03:59,060
>> Beraz pass bat amaitu dugu.

90
00:03:59,060 --> 00:04:00,357
Swap mostradorera 2 da.

91
00:04:00,357 --> 00:04:02,190
Beraz, errepikatu egingo da
Prozesu honetan, berriz ere,

92
00:04:02,190 --> 00:04:04,290
errepikatu swap kontagailua 0 izan arte.

93
00:04:04,290 --> 00:04:05,550
Berrezarri swap kontagailua 0.

94
00:04:05,550 --> 00:04:06,820
Beraz, berrezarri egingo dugu.

95
00:04:06,820 --> 00:04:09,810
>> Orain begiratu ondoko pare bakoitzean.

96
00:04:09,810 --> 00:04:11,880
Duten ordena da, 1 eta 2.

97
00:04:11,880 --> 00:04:13,590
2 eta 3 ematea komeni da.

98
00:04:13,590 --> 00:04:15,010
3 eta 4 ematea komeni da.

99
00:04:15,010 --> 00:04:19,250
Beraz, puntu honetan, nabarituko amaitu dugu
aldameneko pare guztietan begiratzen,

100
00:04:19,250 --> 00:04:22,530
baina swap counter 0 dago oraindik.

101
00:04:22,530 --> 00:04:25,520
>> Ez badugu dute aldatzeko
edozein elementu, orduan

102
00:04:25,520 --> 00:04:28,340
behar du izan, by
hortaz.

103
00:04:28,340 --> 00:04:32,000
Eta beraz, era askotako eraginkortasuna,
dugu informatikariak hori maite,

104
00:04:32,000 --> 00:04:35,560
da gainera gaur deklaratu ahal
baldintza hauek bete beharko sorta osoa

105
00:04:35,560 --> 00:04:38,160
ordenatuko dira, ez baikenuen delako
Edozein elementu trukatu dituzte.

106
00:04:38,160 --> 00:04:40,380
Hori nahiko polita.

107
00:04:40,380 --> 00:04:43,260
>> Beraz, zein da kasu txarrena
burbuila sort kasua?

108
00:04:43,260 --> 00:04:46,240
Kasurik okerrenean array da
Erabat alderantzizko ordenan,

109
00:04:46,240 --> 00:04:49,870
eta, beraz, bakoitzaren burbuila behar dugu
elementu handiak guztiak

110
00:04:49,870 --> 00:04:51,780
array zehar modu.

111
00:04:51,780 --> 00:04:55,350
Eta guk eraginkortasunez halaber behar
burbuila elementu txiki guztiak atzera

112
00:04:55,350 --> 00:04:57,050
array zehar modu guztiak, too.

113
00:04:57,050 --> 00:05:01,950
Beraz, n elementu bakoitzari ditu mugitzeko
n beste elementu guztietan.

114
00:05:01,950 --> 00:05:04,102
Beraz, hori kasu okerrena da.

115
00:05:04,102 --> 00:05:05,810
Kasu honetan onena
eszenatoki arren, hau da,

116
00:05:05,810 --> 00:05:07,880
hautaketa ordena desberdina.

117
00:05:07,880 --> 00:05:10,040
Array da dagoeneko
ordenatuko denean ere joaten gara.

118
00:05:10,040 --> 00:05:12,550
Guk ez dugu izan inolako egiteko
lehen pass swaps.

119
00:05:12,550 --> 00:05:14,940
Beraz, nahi den begiratu behar dugu
elementu gutxiago at, ezta?

120
00:05:14,940 --> 00:05:18,580
Ez dugu hau errepikatu beharko
prozesatu baino zenbat aldiz.

121
00:05:18,580 --> 00:05:19,540
>> Beraz, zer esan nahi du horrek?

122
00:05:19,540 --> 00:05:22,390
Beraz, zein da kasu okerrena
burbuila ordenatu, eta zer da

123
00:05:22,390 --> 00:05:25,330
kasu burbuila ordenatu eszenatokia onena?

124
00:05:25,330 --> 00:05:27,770
Ba hau asmatzen duzu?

125
00:05:27,770 --> 00:05:32,420
Kasurik okerrenean batetik bestera joateko behar duzu
n elementuak n uneoro zeharkatuz.

126
00:05:32,420 --> 00:05:34,220
Beraz, kasu txarrena karratu n.

127
00:05:34,220 --> 00:05:36,550
>> Array primeran bada
ordenatuko arren, zuk bakarrik

128
00:05:36,550 --> 00:05:38,580
den bakoitzean begiratu dute
elementuen behin.

129
00:05:38,580 --> 00:05:42,670
Eta swap counter da oraindik bada 0,
esan dezakezu array hau ordenatuko da.

130
00:05:42,670 --> 00:05:45,780
Eta beraz, kasurik onenean ere, hau da,
benetan aukeraketa baino hobeto

131
00:05:45,780 --> 00:05:49,230
orain arte bezala n omega da.

132
00:05:49,230 --> 00:05:50,270
>> Naiz Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Hau CS50 da.

134
00:05:52,140 --> 00:05:54,382