[Powered by Google Translate] Tommy: Le të bëjmë një vështrim në lloj të përzgjedhjes, një algoritmi për të marrë një listë të numrave dhe zgjidhja e tyre. Një algoritëm, mbani mend, është thjesht një hap-pas-hapi Procedura për kryerjen e një detyre. Ideja themelore prapa përzgjedhjes lloj është për të ndarë Lista e jonë në dy pjesë - një pjesë të renditura dhe një pjesë unsorted. Në çdo hap të algorithm, një numër i është lëvizur nga Pjesa unsorted në pjesën renditura derisa përfundimisht Lista e tërë është renditura. Kështu që këtu është një listë e gjashtë numrave - 23, 42, 4, 16, 8, dhe 15. Tani për tani lista është konsideruar gjithë Unsorted. Edhe pse një numër si 16 Maj tashmë të jetë në korrekt i saj vendndodhjen, algorithm tonë nuk ka asnjë mënyrë për të ditur se deri në Lista e tërë është renditura. Pra, ne do të konsiderojmë çdo numër të Unsorted deri ne lloj ajo veten. Ne e dimë se ne duam lista të jetë në ngjitje qëllim. Pra, ne do të duan për të ndërtuar pjesën e renditura të listës sonë nga e majta në të djathtë, më të vogël tek më i madhi. Për ta bërë këtë, ne do të duhet për të gjetur elementin minimal Unsorted dhe e vuri atë në fund të pjesës renditura. Që nga kjo listë nuk është e renditur, e vetmja mënyrë për të bërë këtë është që të shikojmë në çdo element në pjesën Unsorted, duke kujtuar cili element është i ulët dhe krahasimin e çdo element për këtë. Pra, ne do të shikojmë të parë në 23. Ky është elementi i parë që ne kemi parë, kështu që ne do të kujtojmë atë si minimum. Ardhshëm ne do të shikojmë në 42. 42 është më e madhe se 23, kështu që 23 është ende minimale. Tjetra është 4 e cila është më pak se 23, kështu që ne do të kujtojmë 4 si minimum të ri. Tjetra është 16 e cila është më e madhe se 4, kështu që 4 është ende minimale. 8 është më e madhe se 4 dhe 15 është më e madhe se 4, kështu që duhet të jetë 4 elementi më i vogël unsorted. Pra, edhe pse si njerëzit mund të shohë menjëherë se është 4 elementi minimal, algorithm ynë ka nevojë të shohim në çdo element unsorted, edhe pasi kemi gjetur 4 - element minimale. Pra, tani që ne kemi gjetur elementin minimal, 4, ne do të duam për të lëvizur atë në pjesën e renditura të listës. Që ky është hapi i parë, kjo do të thotë që ne duam të vënë në 4 fillimi i listës. Tani për tani 23 është në fillim të listës, në mënyrë le të bie në ujdi 4 dhe 23. Deri tani lista jonë duket si ky. Ne e dimë se 4 duhet të jenë në vendin e saj përfundimtare, sepse ajo është si elementi më i vogël dhe elementi në fillim nga lista. Pra, kjo do të thotë që ne kurrë nuk duhet të lëvizin atë përsëri. Pra, le të përsëris këtë proces për të shtuar një element të pjesë të renditura nga lista. Ne e dimë se ne nuk kemi nevojë të shikojmë në 4, për shkak se është renditura tashmë. Kështu që ne mund të fillojnë në 42, të cilat ne do të kujtohet si element minimale. Kështu që herën tjetër ne do të shikojmë në të 23 i cili është më pak se 42, kështu që ne kujtohet 23 është minimumi i ri. Tjetra ne shohim 16 e cila është më pak se 23, në mënyrë që 16 është minimumi i ri. Tani ne shikojmë në 8 që është më pak se 16, në mënyrë që 8 është minimumi i ri. 8 Dhe në fund është më pak se 15, kështu që ne e dimë se është një minimum 8 element unsorted. Kështu që do të thotë ne duhet të append 8 të renditura pjesë e listës. Tani për tani 4 është elementi zgjidhet vetëm, kështu që ne duam të zhvillohet 8 tej në 4. Që nga 42 është elementi i parë në pjesën Unsorted e lista, ne do të duan të bie në ujdi 42 dhe 8. Deri tani lista jonë duket si ky. 4 dhe 8 përfaqësojnë pjesën renditura e lista, dhe Numrat e mbetura përfaqësojnë unsorted pjesë e listës. Pra, le të vazhdojmë me një tjetër përsëritje. Ne fillim me 23 këtë kohë, pasi ne nuk kemi nevojë të shohim në e 4 dhe 8 më, sepse ata kanë tashmë janë të renditura. 16 është më pak se 23, kështu që ne do të kujtojmë 16 si minimum të ri. 16 është më pak se 42, por 15 është më pak se 16, kështu që duhet të jetë 15 elementi minimal unsorted. Pra, tani ne duam të bie në ujdi 15 dhe 23 të na jep këtë listë. Pjesa renditura e listës përbëhet nga 4, 8 dhe 15, dhe këto elemente janë Unsorted ende. Por kjo ndodh pikërisht kështu që elementi tjetër unsorted, 16, është renditur tashmë. Megjithatë, nuk ka asnjë mënyrë për të algorithm tonë për të dini se 16 tashmë është në vendin e tij të saktë, kështu që ne ende nevojë për të përsëritur pikërisht procesin e njëjtë. Pra, ne shohim se është më pak se 16 42, dhe 16 është më pak se 23, në mënyrë që 16 duhet të jetë element minimale. Është e pamundur të bie në ujdi me këtë element në vetvete, kështu që ne mund të thjesht lënë atë në këtë vend. Pra, ne kemi nevojë të kalojë një shumë të algorithm tonë. 42 është më e madhe se 23, 23 kështu duhet të jetë element minimale unsorted. Pasi ne bie në ujdi 23 dhe 42, ne fund me finale tonë Lista e renditura - 4, 8, 15, 16, 23, 42. 42 Ne e dimë se duhet të jetë në vendin e duhur pasi kjo është e Elementi i vetëm u largua, dhe kjo është lloj përzgjedhje. Le tani formalizojë algorithm tonë me disa pseudokod. On line një, ne mund të shohim se ne kemi nevojë për të integruar mbi çdo element i listës. Përveç element i fundit, pasi elementi 1 Lista është renditur tashmë. On line dy, ne e konsiderojmë elementin e parë të unsorted pjesë e listës të jetë minimale, siç bëmë me tonë Për shembull, kështu që ne kemi diçka për të krahasuar të. Line tre fillon një lak të dytë në të cilën ne iterate mbi çdo element unsorted. Ne e dimë se pas kam iterations, pjesa renditura e listës sonë duhet të ketë elemente i në atë që çdo hap llojet një element. Pra, elementi i parë unsorted duhet të jetë në pozitë që unë plus 1. On line katër, ne krahasojmë elementin aktuale në minimum element që kemi parë deri tani. Nëse elementi i tanishëm është më i vogël se minimumi element, atëherë ne kujtojmë elementin e tanishme si e re minimale on line pesë. Së fundi, në linjat e gjashtë dhe shtatë, ne bie në ujdi minimum Elementi me elementin e parë Unsorted, duke duke shtuar se në pjesën e renditura të listës. Pasi ne kemi një algoritmi, një pyetje e rëndësishme që të kërkoni veten si programuesit është se sa kohë ka që marrin? Ne do të pari shtrohet pyetja se sa kohë do të marrë për këtë algorithm për të kandiduar në rastin më të keq? Kujtoj ne përfaqësojmë këtë drejtimin Ora me simbol Big O. Në mënyrë që të përcaktojë elementin minimal Unsorted, ne në thelb duhej të krahasojnë çdo element në listë për çdo element tjetër në listë. Intuitive, kjo tingëllon si një O e operimit n katror. Kërkim në pseudokod tonë, ne gjithashtu kemi një lak mbivendosur brenda tjetër loop, e cila me të vërtetë tingëllon si një O e veprimit n katror. Megjithatë, mos harroni se ne nuk duhet të shohim mbi Lista e të gjithë kur përcaktohet elementin minimal Unsorted? Pasi ne e dinim se ishte 4 renditura, për shembull, ne nuk duhet të shohim në atë përsëri. Pra, e bën këtë më të ulët kohë running? Për listën tonë të gjatësisë 6, kemi nevojë për të bërë pesë krahasimet për elementin e parë, katër krahasimet për elementi i dytë, dhe kështu në. Kjo do të thotë se numri i përgjithshëm i hapave është shuma e integers nga 1 deri në gjatësinë e listës minus 1. Ne mund të përfaqësojë këtë me një mbledhje. Ne nuk do të shkojë në summations këtu. Por rezulton se kjo përmbledhje është e barabartë me n herë n minus 1 mbi 2. Ose ekuivalente, n katror mbi 2 minus n mbi 2. Kur flasim për kohën e duhur asymptotic, ky term n katror do të dominojnë këtë term n. Pra, zgjedhja është lloj O n katror. Kujtojnë se në shembullin tonë, lloj përzgjedhje ende e nevojshme për të kontrolloni nëse një numër që është renditur tashmë nevojshme për të lëvizur. Kështu që do të thotë se në qoftë se ne u lloj përzgjedhje mbi një tashmë renditura listë, ajo do të kërkojë të njëjtin numër hapash si ajo do kur drejtimin mbi një listë krejtësisht Unsorted. Pra, ka një lloj përzgjedhje performancën më të mirë rastin e n katror, që ne përfaqësojmë me omega n katror. Dhe kjo është ajo për lloj përzgjedhjes. Vetëm një nga algoritme shumë ne mund të përdorin për të zgjidhur një listë. Emri im është Tommy, dhe kjo është CS50.