>> DOUG LLOYD: Beraz CS50 buruz ikasi dugu sailkatzeko eta bilaketak barietate
algoritmoak.
Eta batzuetan izan daiteke apur bat delikatua mantentzeko
zer algoritmo jarraipena egiten duenari.
Benetan besterik ez dugu azalera gaingabetuak gehiegi,
Han, beste hainbat irizpide horiek dira eta algoritmoen arabera ordenatzeko.
Beraz, bideo honetan goazen besterik minutu batzuk hartu
saiatu eta destila algoritmoa bakoitzeko bere core elements behera
beraz, gehien gogoratzen duzu haiei buruzko informazio garrantzitsua
eta izan artikulatzeko gai desberdintasunak, beharrezkoa izanez gero.
>> Lehena hautaketa ordenatu.
Oinarrizko ideia hautaketa ordena atzean Unsorted elementu txikiena aurkitu da
sorta bat eta trukatu egiten dituzten Array horretan lehenengo elementua Sailkatu.
Esan dugu kasurik txarrenaren dagoela n karratu zela garai exekutatu.
Eta gogoratzen zergatik nahi baduzu, hartu a hautaketa ordena bideoa begiratzeko.
Best-kasuan run garai halaber karratu n.
>> Burbuila ordenatu, horren atzean ideia da ondoko bikote trukatzeko.
Beraz, hori gakoa laguntzen duen da Gogoratzen aldea hemen.
Aukeraketa ordenatu, hau da, orain arte, the smallest-- burbuila aurkitu
moduko da trukatu ondoko bikoteak.
Ondoko bikote trukatu dugu elementuen badute
ordenatik kanpo daude, eta eraginkortasunez eskubidea elementu handiagoak burbuila,
eta, aldi berean hasten da, gainera, ezkerreko elementu txikiagoak mugitzeko.
Kasurik txarrenaren kasuan run garai burbuila sort karratu n.
Best-kasuan run garai burbuila moduko da n.
Zeren eta egoera horretan ez dugu, egia esan,
Agian ez dugu behar trukeak edozein egiteko guztietan.
Bat egiteko besterik ez dugu n elementu guztietan zehar pasatzen.
>> Txertatzeko ordenatu batean, Oinarrizko ideia hemen aldatzearen da.
Txertatzeko ordenatu for keyword da.
Behin urratsera bidez goaz array ezkerretik eskuinera.
Eta egin dugun bezala, ez gara elementu filmea joan
Dagoeneko ikusi dugu gelan egiteko nonbait egokitzeko behar txikiago
ordenatuko zati horretan atzera.
Beraz ordenatzen array eraikitzen dugu bat aldi berean elementu, ezkerretik eskuinera,
eta gauza gela egiteko filmea dugu.
Kasurik txarrenaren run garai txertatzeko ordenatu karratu n.
Best-kasuan exekutatu ordua ez da n.
>> Bateratu hitzarekin orain arte bezala Hemen zatitu eta batzea.
Array osoa zatitu dugu, ala Sei elementu, zortzi elementu da,
10.000 elementuen zatitu dugu behera erdia, erdia, erdia,
array azpian daukagun arte elementu arrayak n bat.
Elementu arrayak n inork multzoa.
Beraz, hasi batez dugu 1.000-elementu array,
eta harira dugu non gauden 1.000 bat-elementu array izan.
Ondoren sub arrayak horiek batzea hasiko dugu itzuli batera zuzena izateko.
Beraz, bi bat-elementu arrayak hartuko dugu eta bi elementu array bat sortzeko.
Bi bi elementu arrayak hartu dugu eta lau elementu sorta bat sortu
eta abar eta abar izan ditugu arte Berriro n elementu array bat berreraiki.
>> Kasurik txarrenaren run garai Batu sort-n aldiz log n.
N elementu ditugu, baina gurutzagarria prozesu honetan
hartzen log n urratsak iristeko multzo osoa bat itzuli.
Halaber, denbora exekutatu Kasu onena da n log n Prozesu honek ez du benetan delako
Laguntza array ote zen ordenatuko edo ez hasteko.
Prozesua bera da, ez dago Zirkuitu gauzak labur modurik.
Beraz, n log txarrena kasuan n, n log onena kasuan n.
>> Hitz egin dugu bi buruz algoritmoak bilatzen.
Beraz, bilaketa lineala errepikatzean ingurukoa da.
Jarraitu dugu array zehar behin, ezkerretik eskuinera,
zenbakia aurkitu nahian ari garela bila.
Kasurik txarrenaren exekutatu denboraren n O big da.
Baliteke gurekin eraman errepikatzean elementu bakar guztietan zehar
elementua begira ari gara aurkitu Ba, bai, azken postuan kokatu,
edo ez guztietan.
Baina ezin dugu baieztatu duten arte Guztia begiratu dugu.
M-kasuan onena, berehala aurkituko dugu.
Best-kasuan run garai Bilaketa lineala 1 omega da.
>> Azkenik, ez zen bilaketa bitarra, bertan askotariko array eskatzen du.
Gogoratu hori oso bat consideración garrantzitsua
bilaketa bitarra lan egiten denean.
Aurrebaldintza bat da it erabiliz It horren baitan bilatzen ari zaren array
banatu behar dira.
Bestela, hitzarekin Banatu eta agindu da.
Zatitu array erdia sartu eta elementuak erdia kentzeko
aldi bakoitzean jarraitu bitartez.
Honegatik arraila hau eta konkistatzeko eta splitting hurbilketa zatian gauzak,
kasurik txarrenaren run ordua bilaketa bitarra da
log n, hau da, nabarmen Bilaketa-en lineala n baino hobea.
Best-kasuan exekutatu ordua ez da oraindik.
>> Baliteke berehala aurkituko dugu Lehen aldiz zatiketa bat egin dugu, baina,
Berriro, gogoratu nahiz bitar bilaketa
funtsean bilaketa lineala baino hobea log izatearen arabera n versus n,
den lanaren bidez joan behar duzu agian sailkatuz, zure array lehen, zein
hain eraginkorra da arabera egin liteke ordenatuko errepikatzean tamaina gainean.
>> Naiz Doug Lloyd, hau CS50 da.