1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Batu Sort]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Harvard Unibertsitatea]

3
00:00:04,000 --> 00:00:07,000
[Hau CS50 da. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Dezagun merge sort buruz hitz egiteko.

5
00:00:09,000 --> 00:00:14,000
Orain arte ikusi duzun burbuila ordenatu, txertatzeko, ordenatu, eta aukeraketa sort.

6
00:00:14,000 --> 00:00:17,000
Zer esan nahi hobea dut nire eskua uhin mota dut arren,

7
00:00:17,000 --> 00:00:21,000
batu sort, oro har, 3 mota horietako edozein baino hobea egiten du.

8
00:00:22,000 --> 00:00:27,000
>> Baina merge sort buruz hitz egin baino lehen, dezagun 2 ordenatuko zerrendak batuz buruz hitz egiteko.

9
00:00:27,000 --> 00:00:31,000
2 ordenatuko zerrendak hartzeko prozesua deitu dugu, horrelako

10
00:00:31,000 --> 00:00:35,000
eta zerrenda bakar batean ordenatuko horietako zerrendak batuz.

11
00:00:35,000 --> 00:00:37,750
Nola egin dezakegu hori?

12
00:00:37,750 --> 00:00:41,290
Beno, ideia bat da, besterik gabe itsasten zerrenda bat beste zerrenda amaiera aldera

13
00:00:41,290 --> 00:00:43,830
eta, ondoren, ordenatzeko sortutako zerrenda.

14
00:00:43,830 --> 00:00:47,220
>> Honetan lan egiten ari den bitartean, alferrikako lan asko da.

15
00:00:47,220 --> 00:00:49,900
Egin ahal izango dugu azkarrago besterik ez ordenatzeko baino.

16
00:00:49,900 --> 00:00:54,100
Iragarki bat okerreko ideia hori hartu txandakatuz cups zerrenda bakoitzaren.

17
00:00:54,100 --> 00:00:56,460
Obrak bezala bitartean, badirudi lehen,

18
00:00:56,460 --> 00:01:05,760
oharra, 16 eta 23 leku daude amaituko dugun, 4, 8, 15, 23, 16 egiten ari dira.

19
00:01:05,760 --> 00:01:09,380
Hau da, 2 partiduko agertzen zerrendan batu behar elementu delako

20
00:01:09,380 --> 00:01:11,720
hasierako zerrendan daude.

21
00:01:11,720 --> 00:01:14,850
Biak 15 eta 16 ezkerreko zerrendan daude.

22
00:01:14,850 --> 00:01:19,810
Trick da aprobetxatu Izan ere, zerrendak, bai ordenatuko dira dagoeneko.

23
00:01:19,810 --> 00:01:23,320
Horrek esan nahi du besterik ez dugu zerrendak bi elementu lehenengo bada itxura -

24
00:01:23,320 --> 00:01:29,580
Hemen, 4 eta 8 - horietako bat ere batu zerrendaren lehenengo elementua izan behar du.

25
00:01:29,580 --> 00:01:31,620
Beno, zergatik da hori?

26
00:01:31,620 --> 00:01:33,520
Bi zerrenda horiek jada ordenatuta,

27
00:01:33,520 --> 00:01:38,410
eta, beraz, bai 4 edo 8 elementu txikiena izan behar du, 2 zerrendak konbinatzen ditugu.

28
00:01:38,410 --> 00:01:41,770
Kasu honetan, txikiena 4 da,

29
00:01:41,770 --> 00:01:46,370
beraz, atera ahal izango dugu 4 eta egiteko, gure zerrendan batu lehenengo elementua.

30
00:01:46,370 --> 00:01:50,710
Orain 3 lehenengo zerrendako gainerako elementuak batuz jarraitzen dugu

31
00:01:50,710 --> 00:01:52,920
Bigarren zerrenda 4 elementuak.

32
00:01:52,920 --> 00:01:57,150
>> Berriro ere, zerrendak, bai lehen elementu begiratu besterik ez dugu behar.

33
00:01:57,150 --> 00:02:01,060
2 txikiagoa batu gure zerrendan bigarren elementua izan behar du.

34
00:02:01,060 --> 00:02:05,440
Oraingo honetan, 8 eta 15 artean txikiena 8 izango da, eta gu sartu

35
00:02:05,440 --> 00:02:09,240
gure zerrendan ordenatuko bigarren elementu gisa.

36
00:02:09,240 --> 00:02:12,180
Zerrendak bi elementu lehenengo alderatzen jarraituko dugu

37
00:02:12,180 --> 00:02:14,420
eta 2 txikiagoa kendu.

38
00:02:14,420 --> 00:02:19,460
15 eta 23, 15 alderatuz txikiagoa da eta, beraz, hori da gure hirugarren elementu.

39
00:02:21,000 --> 00:02:23,910
Orain 16 alderatuz, eta 23, 16 txikiagoa da.

40
00:02:23,910 --> 00:02:26,820
Beraz, laugarren elementua da.

41
00:02:26,820 --> 00:02:30,390
>> Hasiera 2 elementu zerrenda berean errenkadan etorri ziren.

42
00:02:30,390 --> 00:02:34,400
Hau da, zergatik batu zerrenda ezin 2 zerrendak elementu ordezko.

43
00:02:34,400 --> 00:02:40,020
, 23, 50 eta 23. Alderatuz txikiagoa da eta, beraz, aukeratuko dugu.

44
00:02:40,770 --> 00:02:44,070
50 eta 42 urte bitartean, 42 txikiagoa da.

45
00:02:44,070 --> 00:02:48,290
50 eta 108 bitartean, 50 txikiagoa da.

46
00:02:48,290 --> 00:02:52,330
Eta, azkenik, besterik ez dugu 108, beraz, gure zerrendaren amaieran behar da.

47
00:02:53,750 --> 00:02:56,180
Iragarki polit bat, zerrenda ordenatuko ditugu.

48
00:02:56,180 --> 00:02:59,040
2 2 zerrendak lehen elementuak alderatu dugu denbora bakoitza

49
00:02:59,040 --> 00:03:02,730
Batutako zerrenda hurrengo elementua zehazteko gai izan ginen.

50
00:03:02,730 --> 00:03:08,070
Horrek esan nahi du, bada behin betiko zerrenda hori du n zenbakiak, non n hemen, 8,

51
00:03:08,070 --> 00:03:12,610
ondoren n gehien konparaketak behar dugu zenbaki horiek guztiak leku egokian.

52
00:03:13,230 --> 00:03:16,230
Algoritmo bat, besteak beste, esan duenez, denbora lineal exekutatu,

53
00:03:16,230 --> 00:03:18,090
baina ez kezkatu horregatik.

54
00:03:18,570 --> 00:03:22,810
>> Konbinatzeko gure algoritmoa erabiliz, azkar merge sort algoritmoa egin ahal izango dugu.

55
00:03:22,810 --> 00:03:25,170
Beraz, dezagun berrezarri gure zerrendak.

56
00:03:35,210 --> 00:03:37,750
2 merge sort prozesuan urrats handiak daude.

57
00:03:37,750 --> 00:03:41,500
Lehenik eta behin, etengabe zatitu cups zerrenda halves sartu

58
00:03:41,500 --> 00:03:44,860
horietan kopa 1 besterik ez dugu zerrendak sorta bat arte.

59
00:03:44,860 --> 00:03:47,350
Ez kezkatu zerrenda batean bakoitiak zenbaki bat badu

60
00:03:47,350 --> 00:03:49,880
eta ezin duzu haien arteko ebaki primeran garbi bat egiteko.

61
00:03:49,880 --> 00:03:53,750
Just arbitrarioki hautatzeko zerrenda extra kopa sartu, besteak beste

62
00:03:53,750 --> 00:03:56,240
Beraz, dezagun zatitu, zerrenda horiek.

63
00:03:58,140 --> 00:04:01,310
Orain 2 zerrendak dugu.

64
00:04:04,120 --> 00:04:06,570
Orain 4 zerrendak dugu.

65
00:04:10,350 --> 00:04:13,870
>> Eta orain, 8 zerrendak dugu zerrenda bakoitzean kopa bakar bat.

66
00:04:13,870 --> 00:04:16,630
Beraz, urrats 1.

67
00:04:16,630 --> 00:04:22,230
Urratsa 2, behin eta berriz batu ditugu bikote zerrendak merge aurretik ikasi dugu algoritmoa erabiliz.

68
00:04:22,230 --> 00:04:29,160
108 eta 15 biltzen, amaituko dugu zerrendan 15, 108.

69
00:04:30,330 --> 00:04:36,250
50 eta 4 biltzen, 4, 50 amaituko dugu.

70
00:04:36,960 --> 00:04:41,400
8 eta 42 biltzen, amaituko dugu 8, 42.

71
00:04:42,790 --> 00:04:48,130
Eta 23 eta 16 batuz, azkenean 16, 23.

72
00:04:49,740 --> 00:04:52,450
Orain gure zerrendak tamaina 2.

73
00:04:53,020 --> 00:04:56,180
Iragarki 4 zerrendak ordenatuko bakoitza.

74
00:04:56,180 --> 00:04:59,160
>> Beraz, zerrendak bikoteak batuz berriro hasi ahal izango dugu.

75
00:04:59,160 --> 00:05:03,240
15 eta 108 eta 4 eta 50 biltzen

76
00:05:03,240 --> 00:05:11,170
4 lehenengo hartu eta, ondoren, 15, eta gero 50, gero, 108.

77
00:05:11,170 --> 00:05:15,120
8, 42 eta 16, 23 biltzen

78
00:05:15,120 --> 00:05:22,440
lehen aldiz hartu dugu 8, ondoren, 16, 23, eta gero 42.

79
00:05:22,440 --> 00:05:27,370
Beraz, orain 2 tamaina 4 zerrendak besterik ez ditugu, eta bakoitzak bere ordenatuko da.

80
00:05:27,370 --> 00:05:30,980
Beraz, gaur egun, 2, zerrenda horiek batu ditugu.

81
00:05:30,980 --> 00:05:33,440
Lehenik eta behin, 4 hartuko dugu.

82
00:05:33,440 --> 00:05:36,580
Ondoren, 8 hartuko dugu.

83
00:05:36,580 --> 00:05:50,700
Ondoren, 15 eta 16, eta gero 23, gero 42, gero 50, gero 108 hartuko dugu.

84
00:05:50,700 --> 00:05:52,220
Eta Bukatutakoan dugu.

85
00:05:52,220 --> 00:05:54,900
Zerrenda ordenatuko dugu.

86
00:05:54,900 --> 00:05:57,890
Beraz, nola azkar izan zen hau, zehazki?

87
00:05:57,890 --> 00:06:02,000
Termino tekniko, merge sort O (n log n),

88
00:06:02,000 --> 00:06:07,380
burbuila ordenatu, txertatzeko, ordenatu, eta aukeraketa sort guztiak ez dira, berriz,: O (n ²).

89
00:06:07,380 --> 00:06:11,120
Izan ere, laster ikasi dugu, ez da izango duzu ahal izango moduko bat etorri

90
00:06:11,120 --> 00:06:14,820
egiten O (n log n) baino hobeto kasu orokorra.

91
00:06:14,820 --> 00:06:19,120
Berriz ere, ez kezkatu O big notazioa ikusi ez baduzu oraindik.

92
00:06:19,120 --> 00:06:23,490
>> Just jakin nahi izan dugu, horrek esan nahi du benetan big zerrenda ordenatzeko nahi izanez gero

93
00:06:23,490 --> 00:06:26,820
burbuila ordenatu, txertatzeko, ordenatu, eta aukeraketa sort izan potentzialki hartu

94
00:06:26,820 --> 00:06:29,500
nabarmen longer batu baino sort.

95
00:06:29,500 --> 00:06:33,210
Horrek ez du esan nahi merge sort azkarrago zerrenda guztietan izango da

96
00:06:33,210 --> 00:06:36,220
edo nahiz eta tamaina jakin batekin edozein zerrenda bakarrean.

97
00:06:36,220 --> 00:06:41,950
Esate baterako, txertatzeko ordena zerrenda guztietan 5 elementu baino txikiagoa sort azkarrena izan daiteke.

98
00:06:41,950 --> 00:06:47,360
Praktikan, merge sort 50 elementu gisa txiki gisa zerrendak izan ohi da azkarrago.

99
00:06:47,360 --> 00:06:51,120
>> Hala ere, abiadura hau gehigarria ez du prezio bat gabe iritsi da.

100
00:06:51,120 --> 00:06:54,770
Gure ordenatzen beste ez bezala, zerrenda bat hartu eta leku zerrenda aldatu

101
00:06:54,770 --> 00:06:58,740
ordenatuko zerrenda bat lortu arte, merge sort lekua behar du osagarria

102
00:06:58,740 --> 00:07:00,900
2 zerrendak batu elkarrekin.

103
00:07:00,900 --> 00:07:04,690
Ezin dugu berehala erabiltzen ari diren zerrendak fusionatuko Batutako zerrenda gordetzeko

104
00:07:04,690 --> 00:07:08,880
oraindik behar duten elementuak fusionatzen behar dugu gainidatz dezake geroztik.

105
00:07:08,880 --> 00:07:13,540
Espazio hau prezio bat pixka bat da, baina normalean ez da arrazoizkoa.

106
00:07:13,540 --> 00:07:15,330
Eta hori merge sort.

107
00:07:15,330 --> 00:07:18,490
>> Nire izena Rob Bowden da, eta hau da CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
Eta aukeraketa sort.

110
00:07:24,000 --> 00:07:25,880
[Barreak]

111
00:07:25,880 --> 00:07:31,480
Oh, baina hori atera ere pizten dut nola nengoen aurkezten duelako.

112
00:07:31,480 --> 00:07:35,680
Ezkerreko zerrendan. Hori typo izan zen.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] izorratu I -

114
00:07:39,290 --> 00:07:41,190
[Barreak]

115
00:07:41,190 --> 00:07:44,190
Ez dakit zer