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

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvardeko Unibertsitateko]

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

4
00:00:07,290 --> 00:00:13,060
Dezagun txertatzeko sort begirada, zenbakien zerrenda bat hartu eta hauek ordenatzeko algoritmo bat.

5
00:00:13,060 --> 00:00:18,300
Algoritmo bat, gogoratu besterik ez da, urrats-urrats bat zeregin bat lortzeko prozedura.

6
00:00:18,300 --> 00:00:23,640
Txertatzeko sort oinarrizko ideia da, gure zerrenda zatitzeko bi zatiak,

7
00:00:23,640 --> 00:00:26,580
ordenatuko zati bat eta Unsorted zati bat.

8
00:00:26,580 --> 00:00:29,290
>> Algoritmoaren urrats bakoitzean, zenbaki bat da mugitzen

9
00:00:29,290 --> 00:00:32,439
Unsorted zati ordenatuko zati

10
00:00:32,439 --> 00:00:35,680
azkenean arte zerrenda osoa ordenatuko da.

11
00:00:35,680 --> 00:00:43,340
23, 42, 4, 16, 8, eta 15 - Hemen sei zenbakiak Unsorted zerrenda da.

12
00:00:43,340 --> 00:00:47,680
Zenbaki horiek ez dira geroztik ordena gorakorrean, Unsorted ari dira.

13
00:00:47,680 --> 00:00:53,890
Dugu, oraindik ez da hasi zenetik ordenatzeko, sei elementu guztiak kontuan hartu dugu gure Unsorted zati.

14
00:00:53,890 --> 00:00:59,270
>> Behin ordenatzeko hasten gara, zenbaki horiek ordenatuko jarri dugu hauen ezkerraldean.

15
00:00:59,270 --> 00:01:03,600
Beraz, dezagun 23, gure zerrendan lehenengo elementua hasteko.

16
00:01:03,600 --> 00:01:06,930
Ez dugu oraindik gure zati ordenatuko edozein elementu,

17
00:01:06,930 --> 00:01:12,460
beraz, besterik gabe, kontuan hartu 23 gure zati ordenatuko hasiera eta amaiera izan.

18
00:01:12,460 --> 00:01:16,510
Orain, gure zati bat zenbakia, 23 ordenatuko ditu,

19
00:01:16,510 --> 00:01:20,260
eta gure Unsorted zati ditu bost zenbaki horiek.

20
00:01:20,260 --> 00:01:27,320
Dezagun gaur egun gure zati Unsorted, 42, sartu hurrengo zenbakia ordenatzen zati bihurtu.

21
00:01:27,320 --> 00:01:35,930
>> Horretarako, 42 23 konparatu behar dugu -, gure zati ordenatuko elementu bakarra orain arte.

22
00:01:35,930 --> 00:01:41,980
Berrogeita bi 23 baino handiagoa da, eta, beraz, besterik gabe, ahal izango dugu eransteko 42 amaiera

23
00:01:41,980 --> 00:01:45,420
zerrendaren zati ordenatzen. Great!

24
00:01:45,420 --> 00:01:51,850
Orain gure ordenatuko zati bi elementu ditu, eta gure Unsorted zati lau elementu ditu.

25
00:01:51,850 --> 00:01:57,200
Beraz, dezagun orain 4 mugitzeko, Unsorted zati hurrengo elementua.

26
00:01:57,200 --> 00:02:00,230
Beraz, non behar ordenatuko zati jarri?

27
00:02:00,230 --> 00:02:04,220
>> Gogoan izan, zenbaki hau jarri nahi dugu, ordena ordenatuko

28
00:02:04,220 --> 00:02:08,680
beraz, gure ordenatuko zati izaten jarraitzen du, une oro behar bezala ordenatuko.

29
00:02:08,680 --> 00:02:14,380
4 42 eskubidea jartzen dugu, eta gero, gure zerrendan izango da ordena.

30
00:02:14,380 --> 00:02:18,380
Beraz, dezagun gure sort zati eskuinetik ezkerrera mugitzen jarraituko.

31
00:02:18,380 --> 00:02:23,260
Mugitu dugun bezala, dezagun, mugitu zenbaki bakoitza gela leku bat behera egin zenbaki berria.

32
00:02:25,440 --> 00:02:31,740
Ados, 4 da 23 baino gutxiago ere, eta, beraz, ezin dugu kokatu hemen bai.

33
00:02:31,740 --> 00:02:34,480
Dezagun 23 bat eskuinera leku mugitu.

34
00:02:36,500 --> 00:02:43,120
>> Horrek esan nahi du slot sartu lehen zati ordenatzen 4 kokatu nahi genuke.

35
00:02:43,120 --> 00:02:46,300
Ohartu zerrenda espazio hau dagoeneko hutsik zen,

36
00:02:46,300 --> 00:02:51,120
dugu delako horrela antolatu elementuak mugituz jaitsiko dugu aurkitu bezala.

37
00:02:51,120 --> 00:02:52,740
Guztiak eskubidea. Beraz, erdibidean ez gara.

38
00:02:52,740 --> 00:02:57,990
Dezagun gure algoritmoa 16 txertatzeak ordenatzen zati sartu.

39
00:02:59,260 --> 00:03:03,820
Hamasei baino gutxiago 42, eta, beraz dezagun filmea 42 eskuinera.

40
00:03:05,700 --> 00:03:10,190
Hamasei ere 23 baino gutxiago da, eta, beraz dezagun ere mugitzeko elementu hori.

41
00:03:11,790 --> 00:03:20,820
>> Orain, 16 4 baino handiagoa da. Beraz, 4 eta 23 artean 16 sartu dugu gustatuko litzaidake bezala ikusten da.

42
00:03:20,820 --> 00:03:24,620
Zerrendaren zati ordenatzen bidez eskuinetik ezkerrera mugitzen ari den bitartean,

43
00:03:24,620 --> 00:03:29,160
4 ikusi dugu lehenengo zenbaki kopurua baino txikiagoa da

44
00:03:29,160 --> 00:03:31,540
txertatzeko saiatzen ari gara.

45
00:03:31,540 --> 00:03:35,820
Beraz, gaur egun 16 sartu ahal izango dugu hau hutsik zirrikituan

46
00:03:35,820 --> 00:03:40,520
gogoan, elementu hunkigarria dugu sortu sort zati baino gehiago

47
00:03:40,520 --> 00:03:43,340
Nik ez dugu aurkitu ditu.

48
00:03:43,340 --> 00:03:47,900
>> Guztiak eskubidea. Orain, lau ordenatuko elementu eta bi elementu Unsorted dugu.

49
00:03:47,900 --> 00:03:51,600
Beraz, dezagun mugitu 8 ordenatzen zati sartu.

50
00:03:51,600 --> 00:03:55,010
Zortzi 42 baino gutxiago da.

51
00:03:55,010 --> 00:03:56,940
Zortzi 23 baino gutxiago da.

52
00:03:56,940 --> 00:04:00,230
Eta 8 16 baino gutxiago da.

53
00:04:00,230 --> 00:04:03,110
Baina 8 4 baino handiagoa da.

54
00:04:03,110 --> 00:04:07,280
Beraz, 8 sartu nahi genuke, 4 eta 16 bitartean.

55
00:04:09,070 --> 00:04:13,650
Eta orain, besterik ez dugu bat elementu gehiago utzi ordenatzeko - 15.

56
00:04:13,950 --> 00:04:16,589
Hamabost baino 42 gutxiago, hau da,

57
00:04:16,589 --> 00:04:19,130
Hamabost 23 baino gutxiago da.

58
00:04:19,130 --> 00:04:21,750
Eta 15 baino gutxiago 16 urtekoa da.

59
00:04:21,750 --> 00:04:24,810
Baina 15 8 baino handiagoa da.

60
00:04:24,810 --> 00:04:27,440
>> Beraz, hemen da non gure azken txertatzeko egin nahi dugu.

61
00:04:28,770 --> 00:04:30,330
Eta Bukatutakoan dugu.

62
00:04:30,330 --> 00:04:33,540
Unsorted zati elementu gehiago ez daukagu,

63
00:04:33,540 --> 00:04:36,670
eta gure orden egokian zati ordenatuko da.

64
00:04:36,670 --> 00:04:40,270
Txikiena etatik handiena agindu zenbakiak.

65
00:04:40,270 --> 00:04:44,330
Beraz, dezagun begirada bat egin besterik ez dugu urratsak deskribatzen batzuk pseudocode.

66
00:04:46,760 --> 00:04:51,740
>> On line 1, ikus zerrendako elementu bakoitza baino gehiago batetik bestera joateko dugun behar dugu

67
00:04:51,740 --> 00:04:57,060
lehen ezik, Unsorted zati lehen elementu bihurtu baita, besterik gabe,

68
00:04:57,060 --> 00:05:00,220
ordenatzen zati lehenengo elementua.

69
00:05:00,220 --> 00:05:06,320
2 eta 3 lerro On, pista ari gara mantenduz gure uneko Unsorted zati leku.

70
00:05:06,320 --> 00:05:10,450
Element ari ordenatzen zati mugitzen zenbakia adierazten du,

71
00:05:10,450 --> 00:05:15,600
eta j gure indizea adierazten Unsorted zati batean.

72
00:05:15,600 --> 00:05:20,980
>> On line 4,, eskuinetik ezkerrera zati ordenatzen bidez ari gara errepikatzean.

73
00:05:20,980 --> 00:05:26,010
Elementu behin gure uneko posizioa ezkerreko errepikatzean geldiarazi nahi dugu

74
00:05:26,010 --> 00:05:30,050
sartu saiatzen ari gara elementu baino gutxiago.

75
00:05:30,050 --> 00:05:35,600
On line 5, elementu bakoitza espazio bat aurkituko dugu eskuinera aldatzearen ari gara.

76
00:05:35,600 --> 00:05:40,950
Horrela, argi eta garbi espazioa sartu sartu izan dugu aurreneko elementu aurkituko ditugu

77
00:05:40,950 --> 00:05:44,080
mugitzen ari gara elementu baino gutxiago.

78
00:05:44,080 --> 00:05:50,800
On line 6, gure counter eguneratzen ari gara ordenatzen zati bidez ezkerrera mugitzeko jarraitzeko.

79
00:05:50,800 --> 00:05:56,860
Azkenik, linea 7, elementu ari gara txertatzen zerrendaren zati ordenatzen sartu.

80
00:05:56,860 --> 00:06:00,020
>> Posizioa j txertatzeko dela ongi ezagutzen dugu,

81
00:06:00,020 --> 00:06:05,360
dugu dagoeneko elementu egon espazio bat eskuinera mugitu.

82
00:06:05,360 --> 00:06:09,460
Gogoratu, eskuinetik zati ordenatuko bidez ari gara ezkerrera mugitzen

83
00:06:09,460 --> 00:06:13,960
baina, ezkerretik eskuinera zati Unsorted bidez mugitzen ari gara.

84
00:06:13,960 --> 00:06:19,090
Guztiak eskubidea. Dezagun gaur egun zenbat denboraz algoritmoa izan zen exekutatzen ari begirada bat hartu.

85
00:06:19,090 --> 00:06:25,300
Eskatzen dugu lehenik eta behin galdera zenbat denbora du algoritmo hau kasurik okerrenean exekutatu.

86
00:06:25,300 --> 00:06:29,040
Gogoratu O Big notazioa ordezkatzen dugun exekutatzen ari da une honetan.

87
00:06:32,530 --> 00:06:38,500
Gure zerrenda ordenatzeko, Unsorted zati elementu batetik bestera joateko behar izan genuen,

88
00:06:38,500 --> 00:06:43,430
eta elementu horiek bakoitzaren, potentzialki ordenatzen zati elementu guztiak baino gehiago.

89
00:06:43,430 --> 00:06:47,950
Senez, bat O (n ^ 2) eragiketa bezalako soinuak hau.

90
00:06:47,950 --> 00:06:51,840
>> Gure pseudocode begira, begizta bat beste baten barruan habiaratu begizta bat dugu,

91
00:06:51,840 --> 00:06:55,290
horrek, hain zuzen ere, bat O (n ^ 2) eragiketa bezala soinuak.

92
00:06:55,290 --> 00:07:01,590
Hala eta guztiz ere, zati zerrendan ordenatuko ez du oso amaiera arte zerrenda osoa.

93
00:07:01,590 --> 00:07:06,920
Hala eta guztiz ere, potentzialki izan dugu elementu berri bat sartu ordenatzen zati hasieran

94
00:07:06,920 --> 00:07:09,320
algoritmoaren iterazio bakoitzean,

95
00:07:09,320 --> 00:07:14,500
horrek esan nahi du elementu bakoitza begiratu gaur egun zati ordenatzen dugun litzaidake.

96
00:07:14,500 --> 00:07:20,090
Beraz, horrek esan nahi du, potentzialki bigarren elementu bat konparaketa egin ahal izan genuen,

97
00:07:20,090 --> 00:07:24,660
hirugarren elementu bi konparazioak, eta abar.

98
00:07:24,660 --> 00:07:32,480
Beraz, urratsen kopuru osoa, zenbaki osoen batura 1etik zerrenda ken 1 luzera da.

99
00:07:32,480 --> 00:07:35,240
Summation bat irudikatu ahal izango dugu.

100
00:07:41,170 --> 00:07:47,270
>> Ez dugu summations sartu hemen, baina bihurtzen da summation dela berdina

101
00:07:47,270 --> 00:07:57,900
n (n - 1) 2 baino gehiago, hau da, baliokideak n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Exekuzio asymptotic buruz hitz egiten denean,

103
00:08:00,800 --> 00:08:05,170
n ^ 2 epe n epe honetan menderatzeko.

104
00:08:05,170 --> 00:08:11,430
Beraz, txertatzeko ordena Big O (n ^ 2) da.

105
00:08:11,430 --> 00:08:16,150
Zer ran txertatzeko sort dagoeneko horrela antolatu zerrendan.

106
00:08:16,150 --> 00:08:20,960
Kasu horretan, nahikoa genuke eraikitzeko zati ordenatuko ezkerretik eskuinera.

107
00:08:20,960 --> 00:08:25,050
Beraz, soilik n urratsak ordena behar dugu.

108
00:08:25,050 --> 00:08:29,740
>> Horrek esan nahi du txertatzeko sort n errendimendua best-kasu bat,

109
00:08:29,740 --> 00:08:34,130
Ω (n) dugu.

110
00:08:34,130 --> 00:08:36,190
Eta hori da txertatzeko sailkapenarentzat,

111
00:08:36,190 --> 00:08:40,429
hainbat algoritmo bat zerrenda ordenatzeko erabili ahal izango dugu.

112
00:08:40,429 --> 00:08:43,210
Nire izena Tommy da, eta hau da CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, ezin besterik ez duzu ez gelditzeko behin hasten da.

115
00:09:01,620 --> 00:09:04,760
Oh, genuen - >> Boom!