>> [Musika jotzen]
DOUG LLOYD: Hautaketa moduko bat da Algoritmo hori, agian, espero bezala,
elementu multzo bat ordenatzen du.
Eta algoritmoa abisuaren Urrats-urrats multzo bat da
zeregin bat betetzeko argibideak ere.
>> Aukeraketa horrelakorik Oinarrizko ideia hau da,
Unsorted elementu txikiena aurkitu eta gehitu du antolatu zerrenda amaierara arte.
Eraginkortasunez zer honek eraikitze da ordenatuko da zerrenda bat, aldi berean, elementu bat.
Banatzea pseudocode den Algoritmo hau baiezta genezake
honela, errepikatu arte no Sailkatu elementu geratzen.
Sailkatu bidez bilatzeko Datu balio txikiena aurkitu,
ondoren trukatu balio txikiena batera Unsorted zatia lehenengo elementua.
>> Hau ikusteko programak lagundu ahal izango da, beraz dezagun begirada bat.
Beraz, hau, nire asmoa, da Sailkatu array eta dut
Adierazitako hori guztia adieraziz elementuetako kolore gorria ematen zaie,
azken horiek ez dira oraindik ordenatuta.
Hau osoa da array zati Unsorted.
>> Beraz, goazen urrats bidez aukeraketa ordenatu array hau ordenatzeko.
Beraz, berriro ere, gonna errepikatu gaude no Sailkatu elementu geratzen den arte.
Gonna bilaketa bidez ari gara Datu balio txikiena aurkitu,
eta ondoren, trukatu batera balio duten Unsorted zatia lehenengo elementua.
>> Oraintxe bertan, berriro, osoa array Unsorted zati da.
Elementu gorri guztiak Sailkatu dira.
Beraz bilatu bidez dugu eta balio txikiena aurkitu dugu.
Hasteko hasieran gaude, Amaieran joan ginen,
aurkitu dugu balio txikiena da, bat.
Beraz, hori zati bat da.
Eta gero, bi zati, trukatu dituzten balio duten Unsorted zatia lehenengo elementua,
edo lehen elementu gorria.
>> Kasu honetan izango litzateke bost, beraz, bat eta bost trukatzeko.
Hori egiten dugunean, ezin ditugu ikusmen ikusi ditudan dugu
txikiena baloratzen elementu mugitu Array, hasieratik nahi.
Eraginkortasunez ordenatzen den elementu hori.
>> Eta beraz, dugu, hain zuzen ere, baieztatu daiteke eta egoera hori, ordenatuko da.
Eta horrela adierazi beharko dugu ordenatzen zati gure array, urdin margotu.
>> Orain errepikatu besterik ez dugu prozesua berriro.
Bilatu zati Unsorted bidez dugu array elementu txikiena aurkitu.
Kasu honetan, bi da.
>> Trukatu dugun lehenengo batera Unsorted zati elementu.
Kasu honetan bi ere gertatzen den izan Unsorted zatia lehenengo elementua.
Beraz, bi berez trukatu dugu, horrek benetan bi hostoak
Non da, eta ordenatuko da.
Etengabeko on, bidez bilatzen dugu elementu txikiena aurkitu.
It hiru da.
Egiten dugu trukatu lehenengoarekin elementu, bost da.
Eta orain hiru ordenatuko da.
>> Non bilatzen dugu bidez berriro, eta guk aurkituko elementu txikiena lau da.
Bertan trukatu dugu lehen elementu batera Sailkatu parte, eta, orain, lau ordenatuko da.
>> Aurkituko dugu, bost da elementu txikiena.
Egiten dugu trukatu lehenengoarekin Unsorted zati elementu.
Eta orain bost ordenatuko da.
>> Eta gero, azkenik, gure Sailkatu parte osatzen
elementu bakar bat besterik ez da, beraz bilatu bidez dugu
eta aurkitu ditugun sei da txikiena, eta hain zuzen ere, soilik elementu.
Eta gero, esan daiteke dela ordenatuko da.
Eta orain, gure array pizten ditugu Ari erabat Unsorted bertatik
Gorriz, erabat ordenatuko urdina, hautaketa ordena erabiliz.
>> Beraz, zein da kasu okerrena hemen?
Beno absolutua txarrenean Kasu, baino gehiago begiratu behar dugu
array elementu den guztia Unsorted elementu txikiena aurkitu,
eta errepikatu behar dugu Prozesu honek n aldiz.
Array elementu bakoitzeko behin dugun bakarra delako, algoritmo honetan,
moduko elementu bat aldi berean.
>> Zer da kasurik onenean?
Beno berdin da, ezta?
Benetan daukagu ​​bidez oraindik zapalduta array elementu bakar behin
ordena dela baieztatzeko, hain zuzen ere, elementu txikiena.
>> Beraz, kasu exekuzio txarrena, dugu Prozesu n aldiz errepikatu behar,
n elementu bakoitzari behin.
Eta kasurik onenean ere, Gauza bera egin behar dugu.
>> Beraz, atzera pentsatzen gure konputazional konplexutasunaren laukitik,
zer uste duzu dela txarrena Kasu aukeraketa sort exekuzio?
Zure ustez, zer da onena Kasu aukeraketa sort exekuzio?
>> Ba asmatzen duzu Big n O karratu, eta Big Omega n karratu?
Eskubidea litzaidake.
Horiek dira, hain zuzen ere, txarrena kasuan eta onena kasu run
aldiz, hautaketa ordena da.
>> Naiz Doug Lloyd.
Hau CS50 da.