[Muzika] DOUG Lloyd: Përzgjedhja lloj është një algorithm që, si ju mund të presin, klasifikon një grup elementesh. Dhe algorithm risjell është një grup hap-pas-hapi Udhëzimet për plotësimin e një detyre. 

Në përzgjedhjen lloj Ideja themelore është kjo, gjeni elementin më të vogël Unsorted dhe shtoni atë në fund të listës renditura. Efektivisht Çfarë kjo nuk është ndërtuar një listë të renditura, një element në një kohë. Thyer atë poshtë për pseudokod ne mund të deklarojë këtë algorithm si më poshtë, të përsëritur këtë deri ka elemente Unsorted mbeten. Kërko përmes Unsorted të dhënat për të gjetur vlerën më të vogël, pastaj të bie në ujdi vlerën më të vogël me elementi i parë i pjesës pandara. 

Kjo mund të ndihmojë të kujtoj këtë, kështu që le të marrin një vështrim në këtë. Pra kjo, unë luftoj, është një array Unsorted dhe unë kam treguar atë duke treguar se të gjitha nga elementet janë të ngjyrosura kuqe, ata nuk janë të renditura ende. Kjo është e gjithë pjesë Unsorted e vektorit. 

Pra, le të shkojnë nëpër hapat e Zgjedhja lloj për të zgjidhur këtë koleksion. Pra, përsëri, ne jemi gonna përsëritje derisa ka elemente Unsorted mbeten. Ne jemi gonna të kërkuar përmes të dhënat për të gjetur vlerën më të vogël, dhe pastaj të bie në ujdi se vlera me të elementi i parë i pjesës pandara. 

Tani për tani, përsëri, të gjithë array është pjesa Unsorted. Të gjitha elementet e kuqe janë Unsorted. Kështu që ne të kërkuar përmes dhe ne gjejmë vlerën më të vogël. Ne të fillojë në fillim, ne do të shkojmë deri në fund, ne gjejmë vlera më të vogël është, një. Pra, kjo është pjesa e parë. Dhe pastaj pjesa e dytë, bie në ujdi se vlera me elementi i parë i pjesës pandara, ose elementi i parë të kuqe. 

Në këtë rast që do të jetë pesë, kështu që ne bie në ujdi një dhe pesë. Kur e bëjmë këtë, ne mund të vizualisht të shihni se ne kemi lëvizur elementin më të vogël me vlerë e array, në fillim. Efektivisht klasifikim atë element. 

Dhe kështu që ne me të vërtetë mund të konfirmojmë dhe shtet që një, është e renditura. Dhe kështu që ne do të tregojnë pjesën e renditura e array tonë, duke e ngjyrosur blu. 

Tani ne vetëm përsëris procesin përsëri. Ne kërko nëpër pjesën e paklasifikuara të array për të gjetur elementin më të vogël. Në këtë rast, është dy. 

Ne shkëmbim se me parë element i pjesës pandara. Në këtë rast dy gjithashtu ndodh të jetë elementi i parë i pjesës pandara. Pra, ne të bie në ujdi dy me vete, e cila me të vërtetë vetëm lë dy ku është, dhe është e renditura. Duke vazhduar më, ne të kërkuar përmes për të gjetur elementin më të vogël. Është e tre. Ne shkëmbim me parë element, që është pesë. Dhe tani tre është e renditura. 

Ne kërkoni përmes përsëri, dhe ne gjetur elementi më i vogël është katër. Ne të bie në ujdi atë me elementin e parë të pjesë Unsorted, dhe tani katër është e renditura. 

Ne gjejmë se pesë është elementi më i vogël. Ne shkëmbim me parë element i pjesës pandara. Dhe tani pesë është e renditura. 

Dhe pastaj në fund, tonë Pjesa Unsorted përbëhet e vetëm një element të vetëm, kështu që ne të kërkuar nëpër dhe ne gjejmë se gjashtë është më i vogël, dhe në fakt, vetëm element. Dhe pastaj ne mund të themi se ajo është e renditura. Dhe tani ne kemi ndezur koleksion tonë nga të qenit Unsorted plotësisht në të kuqe, të zgjidhet plotësisht në ngjyrë blu, duke përdorur përzgjedhjes lloj. 

Pra, çfarë është skenari më i keq këtu? Edhe në absolut më të keq rast, ne duhet të shikojmë gjatë të gjitha elementet e vektorit të gjeni elementin më të vogël Unsorted, dhe ne kemi për të përsëritur ky proces n herë. Një herë për çdo element të vektorit sepse ne vetëm, në këtë algorithm, lloj një element në kohë. 

Çfarë është skenari më i mirë? E pra kjo është saktësisht e njëjtë, e drejtë? Ne fakt duhet të ende hap përmes çdo element i vetëm i vektorit në mënyrë që të konfirmoj që ajo është, në fakt, elementi më i vogël. 

Pra rast Runtime e keqja, ne duhet të përsëris një proces n herë, herë për secilin prej elementeve n. Dhe në rastin më të mirë, ne duhet të bëjmë të njëjtën gjë. 

Pra duke menduar përsëri për tonë Toolbox kompjuterike kompleksiteti, çfarë mendoni se është më e keqja Rasti Runtime të përzgjedhjes lloj? Çfarë mendoni se është më e mira Rasti Runtime të përzgjedhjes lloj? 

A ju me mend Big O i n katror, dhe Big Omega i n katror? Ju do të jetë e drejtë. Ata janë, në fakt, Rasti më i keq dhe rastit të drejtuar mirë herë, për zgjedhjen lloji. 

Unë jam Doug Lloyd. Kjo është CS50.