1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-SMITH: Kaixo, naiz Mark
Grozen-Smith, eta hau da, Quicksort.

3
00:00:10,390 --> 00:00:13,520
Just txertatzeko sort eta burbuila bezalako
ordenatu, Quicksort algoritmo bat da

4
00:00:13,520 --> 00:00:15,720
Zerrenda edo gauzak array bat ordenatzeko.

5
00:00:15,720 --> 00:00:19,080
Sinpletasunagatik, Demagun dutenak
Gauzak osokoak besterik ez dira, baina

6
00:00:19,080 --> 00:00:22,060
Ezagutzen Quicksort lan egiten duten
zenbakiak baino zerbait gehiago.

7
00:00:22,060 --> 00:00:24,720
Quickstart pixka bat zailagoa da
baino txertatzeko edo burbuila, baina da

8
00:00:24,720 --> 00:00:27,560
ere askoz eraginkorragoa
kasu gehienetan.

9
00:00:27,560 --> 00:00:28,150
Itxaron segundo bat.

10
00:00:28,150 --> 00:00:30,760
Ba, besterik gabe esan zuen "gehien
Kasu, "ez" guztiak "?

11
00:00:30,760 --> 00:00:31,710
Interesgarria, ez.

12
00:00:31,710 --> 00:00:33,560
Ez kasu guztietan berdinak dira.

13
00:00:33,560 --> 00:00:36,650
Ez xehetasuna hau kezkatu baduzu
ez dute ikusi big O idazkera oraindik, baina

14
00:00:36,650 --> 00:00:39,730
Quicksort O bat (n karratu) algoritmoa da
txarrena at, besterik ez bezalakoa

15
00:00:39,730 --> 00:00:41,430
txertatzeko edo burbuila ordenatu.

16
00:00:41,430 --> 00:00:44,950
Hala ere, normalean askoz gehiago jokatzen du
analogikoa m zaharra algoritmo bat bezala.

17
00:00:44,950 --> 00:00:45,750
Zergatik?

18
00:00:45,750 --> 00:00:46,810
Horretan itzuli geroago dugu.

19
00:00:46,810 --> 00:00:49,610
Baina orain, dezagun ikasi nahiko luke
Quicksort nola funtzionatzen.

20
00:00:49,610 --> 00:00:53,080
>> Hargatik oinez hau Quicksorting bidez
zenbaki osoen array txikiena etatik

21
00:00:53,080 --> 00:00:54,260
handiena da.

22
00:00:54,260 --> 00:01:00,110
Hemen zenbaki osoko 6 dugu,
5, 1, 3, 8, 4, 7, 9, eta 2.

23
00:01:00,110 --> 00:01:03,480
Lehenik eta behin, azken elementua jaso dugu
array hau - Kasu honetan, bi -

24
00:01:03,480 --> 00:01:06,870
eta deitu "pibota." duen Hurrengo, dugun
hasteko bi gauza begiratu -

25
00:01:06,870 --> 00:01:10,220
bata, indize baxuena, hau aipatzeko dut
nahi eskuinean dagoen ostatu gisa

26
00:01:10,220 --> 00:01:13,970
horman, eta, bi, ezkerreko
elementua, eta horrek "oraingoa deitu dizut

27
00:01:13,970 --> 00:01:17,260
elementua. "Zer egin behar dugu,
beste elementu guztiak, beste itxura

28
00:01:17,260 --> 00:01:20,930
pibota baino, eta elementu guztiak jarri
to pibota baino txikiagoa

29
00:01:20,930 --> 00:01:24,140
hormaren utzi eta horiek guztiak
to pibota baino handiagoa

30
00:01:24,140 --> 00:01:25,570
hormaren eskuinaldean.

31
00:01:25,570 --> 00:01:29,560
Ondoren, azkenik, pibota erortzen egingo dugu
eskuineko horma dutela arteko jarri on

32
00:01:29,560 --> 00:01:32,970
zenbaki guztietan, hura baino txikiagoa
eta zenbaki guztietan handiagoa.

33
00:01:32,970 --> 00:01:34,460
>> Hacerlo en duten utzi.

34
00:01:34,460 --> 00:01:38,540
Hartu 2, jarri hormaren at
, eta hasieran deitu 6 "uneko

35
00:01:38,540 --> 00:01:41,590
elementua. "Beraz begiratu nahi dugu
Gure gaur egungo elementu, 6.

36
00:01:41,590 --> 00:01:44,200
Eta baino handiagoa da geroztik
2, hori utzi, han joan

37
00:01:44,200 --> 00:01:45,610
hormaren eskuinera.

38
00:01:45,610 --> 00:01:48,980
Ondoren, mugitzen dugu 5era gisa begiratu gure
egungo elementu eta ikusi duten honetan

39
00:01:48,980 --> 00:01:51,840
da, berriz ere, pibota baino handiagoa, hain dugu
utzi non da eskuin bozkatu,

40
00:01:51,840 --> 00:01:53,190
hormaren alde.

41
00:01:53,190 --> 00:01:53,880
Mugitzen dugu.

42
00:01:53,880 --> 00:01:56,750
Gure gaur egungo elementu da
gaur egun 1, eta - oh.

43
00:01:56,750 --> 00:01:58,030
Hau desberdina da orain.

44
00:01:58,030 --> 00:02:00,890
Egungo elementu baino txikiagoa da gaur
pibota, beraz, jarri nahi dugu

45
00:02:00,890 --> 00:02:02,570
hormaren ezkerrera.

46
00:02:02,570 --> 00:02:06,555
Horretarako, utzi piztu besterik hamarkadaren
indize txikiena duen egungo elementu

47
00:02:06,555 --> 00:02:07,970
besterik hormaren eskuinera eserita.

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
Orain, horma mugitzen dugu indize bat sortu
beraz, 1 ezkerrean dago

50
00:02:17,570 --> 00:02:19,750
Horman, orain alde.

51
00:02:19,750 --> 00:02:20,310
>> Itxaron.

52
00:02:20,310 --> 00:02:23,450
Nahasten dut besterik ez da elementu
eskuineko hormaren alde, ez?

53
00:02:23,450 --> 00:02:23,890
Ez kezkatu.

54
00:02:23,890 --> 00:02:24,930
Hori da isuna.

55
00:02:24,930 --> 00:02:27,570
Du axola buruz dugun oraingoz gauza bakarra
da, elementu horiek guztiak

56
00:02:27,570 --> 00:02:29,570
hormaren eskuinaldean handiagoak dira
pibota baino.

57
00:02:29,570 --> 00:02:31,760
Ez dago benetako ordena oraindik onartuta dago.

58
00:02:31,760 --> 00:02:33,200
>> Orain, ordenatzeko itzuli.

59
00:02:33,200 --> 00:02:35,840
Beraz, aurrera jarraituko dugu begira
elementuetako gainerako.

60
00:02:35,840 --> 00:02:39,075
Eta kasu honetan, ez direla ikusten dugu
baino ez du beste elementu gutxiago

61
00:02:39,075 --> 00:02:42,100
pibota, beraz, horiek guztiak utzi dugu
hormaren eskuinaldean.

62
00:02:42,100 --> 00:02:45,980
Azkenik, lortu uneko elementua dugu
eta ikusi pibota dela.

63
00:02:45,980 --> 00:02:48,830
Orain, horrek esan nahi du bi dugula
array, lehenengo izaki atal

64
00:02:48,830 --> 00:02:51,820
pibota da eta ezkerreko aldean txiki
horman, eta bigarren izatearen

65
00:02:51,820 --> 00:02:54,500
to pibota batekoa baino handiagoa
eskuineko hormaren alde.

66
00:02:54,500 --> 00:02:57,040
Arteko pibota elementua jarri nahi dugu
biak, eta orduan jakingo dugu

67
00:02:57,040 --> 00:03:01,000
pibota bere eskubidea da
final ordenatuko leku.

68
00:03:01,000 --> 00:03:04,980
Beraz, egiten duen lehenengo elementua aldatzeko dugu
eskubidea pibota duten harresiaren alde,

69
00:03:04,980 --> 00:03:06,410
eta badakigu pibota en
bere eskuineko posizioa.

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> Ondoren errepikatu dugu prozesu hau egiteko
subarrays utzi eta pibota eskuinean.

72
00:03:15,650 --> 00:03:18,700
Geroztik azken subarray bakarra da
elementu luzeak, badakigu hori da dagoeneko

73
00:03:18,700 --> 00:03:22,480
nola egin dezaket izarrekin izango duzu ordenatuko delako
aginduko Oraindik elementu bat besterik ez bada?

74
00:03:22,480 --> 00:03:28,860
Subarray eskuinaldean egiteko, dugu
ikusi pibota dela 5 da, eta hormaren

75
00:03:28,860 --> 00:03:32,250
besterik ez da 6 du utzi.

76
00:03:32,250 --> 00:03:34,970
Eta egungo elementu ere
hasten 6 gisa.

77
00:03:34,970 --> 00:03:36,200
Beraz, 6 5 baino handiagoa da.

78
00:03:36,200 --> 00:03:38,590
Hori utzi, non da bozkatu,
eskuineko hormaren alde.

79
00:03:38,590 --> 00:03:41,060
Orain, mugitzea, 3 5 baino txikiagoa da.

80
00:03:41,060 --> 00:03:44,160
Beraz pizten dugu lehen elementu batzuekin
besterik hormaren eskuinaldean.

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
Orain, horma mugitu dut izan da.

83
00:03:50,750 --> 00:03:53,010
Orain, mugitzea 8 arte.

84
00:03:53,010 --> 00:03:56,480
8 5 baino handiagoa da,
eta horrela utziko dugu.

85
00:03:56,480 --> 00:03:58,720
4 5 baino txikiagoa da, beraz, piztu dugu.

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
Eta on.

88
00:04:03,570 --> 00:04:04,820
Eta on.

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> Aldi bakoitzean prozesua errepikatu dugu on
ezkerreko eta eskuineko array alboetan. dugu

91
00:04:13,670 --> 00:04:17,010
pibota bat aukeratu eta konparazioak egin
eta beste maila bat utzi sortu eta

92
00:04:17,010 --> 00:04:18,240
eskubidea subarrays.

93
00:04:18,240 --> 00:04:21,500
Dei errekurtsiboa honetan egingo arte jarraituko
Azkenean denean dugu iritsiko gara

94
00:04:21,500 --> 00:04:25,290
banatzen sortu array orokorrean sartu
luzera 1 of subarrays besterik.

95
00:04:25,290 --> 00:04:28,060
Hortik aurrera, badakigu array ordenatuko da
elementu guztietan duelako, at

96
00:04:28,060 --> 00:04:29,330
noizbait, pibota izan da.

97
00:04:29,330 --> 00:04:32,720
Bestela esanda, elementu bakoitzeko, guztiak
ezkerrera zenbakiak txikiagoan dira

98
00:04:32,720 --> 00:04:36,420
balioak eta joan zenbaki guztiak
eskubidea balore handiagoa izan.

99
00:04:36,420 --> 00:04:38,980
>> Metodo hau oso ondo funtzionatzen du bada
aukeratu pibota balioa da

100
00:04:38,980 --> 00:04:41,930
erdian, gutxi gorabehera,
zerrenda balioen sorta.

101
00:04:41,930 --> 00:04:45,630
Hori esan nahi du, mugitzen dugu ondoren
elementuen inguruan, badira asko bezala buruz

102
00:04:45,630 --> 00:04:48,390
pibota ezkerraldeko elementu
Han eskuinera diren bezala.

103
00:04:48,390 --> 00:04:52,380
Eta arrail-eta-konkistatzen izaera
Orduz Quicksort algoritmoa hartu da

104
00:04:52,380 --> 00:04:53,850
abantaila osoa.

105
00:04:53,850 --> 00:04:57,500
Hau O of exekuzio bat sortzen du (n log n,)
1 Egin behar dugun n ken n duelako

106
00:04:57,500 --> 00:05:01,640
belaunaldi eta log bakoitzean konparazioak
zerrenda zatitzeko dugu n delako

107
00:05:01,640 --> 00:05:03,210
log n aldiz.

108
00:05:03,210 --> 00:05:06,160
Hala ere, kasu txarrenean, hau
algoritmoa benetan be O (n

109
00:05:06,160 --> 00:05:09,850
karratu.) belaunaldi bakoitzean Demagun,
pibota Beraz, zerbait gertatzen ahal izango du

110
00:05:09,850 --> 00:05:12,520
txikiena edo handiena
zenbakiak ordenatzeko ari gara.

111
00:05:12,520 --> 00:05:15,870
Hau zerrendan behera hautsi esan nahiko luke
n aldiz eta making n ken 1

112
00:05:15,870 --> 00:05:17,690
konparazioak aldi bakoitzean bakarra.

113
00:05:17,690 --> 00:05:20,490
Horrela, n o karratu.

114
00:05:20,490 --> 00:05:22,000
>> Nola daiteke metodoa hobetzen dugu?

115
00:05:22,000 --> 00:05:25,100
One modu ona metodoa hobetzen da
behera moztu probabilitatea on duten

116
00:05:25,100 --> 00:05:28,150
exekuzio da inoiz benetan
n o karratu.

117
00:05:28,150 --> 00:05:31,860
Gogoratu hau txarrena, txarrena kasuan agertokia
bakarrik gerta daiteke noiz

118
00:05:31,860 --> 00:05:35,320
aukeratu pibota da beti altuena
edo matrizearen balio baxuena.

119
00:05:35,320 --> 00:05:38,630
Hau da gutxiago gertatuko bermatzeko,
pibota aurki ditzakegu arabera

120
00:05:38,630 --> 00:05:42,610
elementu anitz eta aukeratzerakoan
mediana balioa hartuz.

121
00:05:42,610 --> 00:05:44,650
>> Nire izena Mark Grozen-Smith da,
eta hau da CS50.

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> Sinpletasunagatik, Demagun dutenak
Gauzak osokoak besterik ez dira, baina

124
00:05:50,930 --> 00:05:51,970
Ezagutzen Quicksert duten -

125
00:05:51,970 --> 00:05:53,160
Quicksert?

126
00:05:53,160 --> 00:05:55,200
Barkatu.

127
00:05:55,200 --> 00:06:02,000
>> Hemen osokoak dugu
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> SPEAKER 1: Benetan?

129
00:06:03,200 --> 00:06:04,850
>> HIZLARIA 2: Ez gelditu.

130
00:06:04,850 --> 00:06:06,100
>> HIZLARIA 1: Benetan?

131
00:06:06,100 --> 00:06:08,491