[Muzika] 

DOUG Lloyd: Pra futje lloj është një tjetër Algorithm ne mund të përdorim për të zgjidhur një grup. Ideja prapa këtij algoritmi është për të ndërtuar rrjet të renditura në vend, duke i shtyrë elemente nga mënyra si ju shkoni, që të bëjë vend. Kjo është pak më ndryshe nga lloji përzgjedhjes ose flluskë lloj, për shembull, ku ne jemi duke rregulluar vende, ku ne jemi duke bërë këmbime. 

Në këtë rast ajo që ne jemi në fakt bërë është elemente rrëshqitje mbi, nga rruga. Si e bën këtë algorithm punojnë në pseudokod? E pra le të vetëm në mënyrë arbitrare të them se Elementi i parë i vargut është e renditura. Ne jemi duke ndërtuar atë në vend. 

Ne jemi gonna të shkojnë një element në një kohë dhe ndërtuar atë, dhe kështu që gjëja e parë që ne shohim është një koleksion një element. Dhe me përkufizim, një element array është e renditura. 

Pastaj ne do të përsëris këtë proces until-- ne do të përsëris procesin në vijim deri sa të gjitha elementet janë të renditura. Shikoni në elementin e ardhshëm Unsorted dhe futur atë në pjesën e renditura, duke zhvendosur numrin e kërkuar e elementeve nga rruga. Shpresojmë se kjo vizualizimi do t'ju ndihmojë të shihni saktësisht se çfarë është ndodh me futje lloji. 

Pra, përsëri, këtu është tonë Gjithë grup Unsorted, të gjithë elementet tregohet në të kuqe. Dhe le të ndjekim Hapat e pseudokod sonë. Gjëja e parë që ne bëjmë, është që ne e quajmë Elementi i parë i vargut, të renditura. Pra, ne jemi vetëm gonna të themi pesë, ju jeni të renditura tani. 

Atëherë ne shikojmë në të ardhshëm element unsorted e vektorit dhe ne duam të futur që në pjesën e renditura, duke zhvendosur mbi elemente. Pra dy është tjetër Unsorted element i vektorit. Është e qartë se kjo i takon para se të pesë, kështu që ajo që ne jemi gonna të bëjmë është lloj i mbajë dy mënjanë për një të dytë, zhvendoset pesë mbi, dhe pastaj futur dy para pesë, ku të duhet të shkoni. Dhe tani ne mund të themi se dy është e renditura. 

Kështu si ju mund të shihni, ne kemi vetëm deri më tani shikuar në dy elemente të vektorit. Ne nuk kemi shikuar në nivel pushoni në të gjitha, por ne kemi mori këto dy elemente të renditura nga Mënyra e mekanizmit zhvendosur. 

Pra, ne përsëris procesin përsëri. Shikoni në tjetër Unsorted element, kjo është një. Le të thonë se mënjanë për një të dytë, zhvendoset gjithçka mbi, dhe të vënë një ku duhet të shkoni. 

Përsëri, ende, ne kemi vetëm ndonjëherë shikuar në një, dy dhe pesë. Ne nuk e dimë se çfarë tjetër po vjen, por ne kemi renditur këto tre elemente. 

Elementi tjetër është unsorted tre, kështu që ne do të vënë atë mënjanë. Ne do të zhvendoset mbi atë që ne nevojë për të cilën, kësaj radhe nuk është gjithçka si në mëparshme dy raste, kjo është vetëm pesë. Dhe pastaj ne do të rrinë tre në, në mes të dy dhe pesë. 

Gjashtë është tjetër Unsorted element të vektorit. Dhe në faktin gjashtë është më e madhe se pese, kështu ne as nuk duhet të bëjë ndonjë shkëmbejnë. Ne vetëm mund të litar gjashtë drejtë në të fundi i pjesës renditura. 

Së fundi, katër është Elementi i fundit unsorted. Pra, ne do të vënë atë mënjanë, ndryshim mbi elementet ne duhet të zhvendoset mbi, dhe pastaj të vënë katër ku i takon. Dhe tani shikoni, ne kemi lloj të gjithë elementeve. Vini re me futje lloj, ne nuk kemi për të shkuar mbrapa dhe me radhë nëpër rrjet. Ne vetëm shkoi nëpër rrjet një herë, dhe ne u zhvendos gjëra se ne do hasur tashmë, në mënyrë për të bërë vend për elemente të reja. 

Pra, çfarë është rasti më i keq Skenari me futje lloj? Në rastin më të keq, array është në mënyrë të kundërt. Ju duhet të zhvendoset secilin prej elementeve n deri në pozicione n, çdo herë kemi të vetme të bëjë një futje. Kjo është një shumë të zhvendosur. 

Në rastin më të mirë, The grup është renditur në mënyrë të përkryer. Dhe lloj si ajo që ka ndodhur me pesë dhe gjashtë në shembull, ku ne mund vetëm litar atë në pa pasur nevojë të bëni ndonjë zhvendosur, ne do të bëjmë që në thelb. 

Nëse ju imagjinoni se tonë array ishte një me gjashtë, ne do të nisem nga deklaruar një të tillë është e renditura. Dy vjen pas një kështu që ne mund vetëm them, OK, mirë një dhe dy janë të renditura. Tre vjen pas dy kështu, OK, një dhe dy dhe tre janë të renditura. 

Ne nuk jemi duke bërë ndonjë këmbime, ne jemi vetëm duke lëvizur këtë linjë arbitrare në mes të renditura dhe Unsorted si të shkojmë. Si në mënyrë efektive si ne e bëmë në shembull, kthyer elemente blu, si ne të vazhdojë. Pra, çfarë është rast Runtime të keq, atëherë? Mos harroni, në qoftë se ne duhet të zhvendoset secilit prej elementet n ndoshta pozicionet n, shpresojmë që ju jep një ide se rasti më i keq Runtime është Big O i n katror. 

Nëse array është krejtësisht të renditura, të gjithë ne duhet të bëjmë është të shikoni në çdo element të vetme herë, dhe pastaj ne jemi duke bërë. Pra, në rastin më të mirë, është e omega e n. 

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