[Powered by Google Translate] [Rendit futjes]
[Tommy MacWilliam] [Universiteti i Harvardit]
[Kjo është CS50.TV]
Le të marrin një vështrim në lloj futje, 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 procedurat për kryerjen e një detyre.
Ideja themelore pas lloj futje, është që të ndajë listën tonë 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 tek pjesën renditura
deri në fund listën tërë renditura.
Këtu është lista e gjashtë numrave klasifikuara - 23, 42, 4, 16, 8, dhe 15.
Që këto shifra nuk janë të gjitha në ngjitje qëllim, ata janë Unsorted.
Që ne nuk kemi filluar ende klasifikim, ne do të konsiderojnë të gjitha gjashtë elemente pjesën tonë Unsorted.
>> Sapo ne fillojmë klasifikim, ne do të vënë këto numra të renditura në të majtë të tyre.
Pra, le të fillojë me 23, elementi i parë në listën tonë.
Ne nuk kemi ndonjë elemente në pjesën tonë të renditura ende,
kështu që le të konsiderojmë thjesht 23 të jetë fillimi dhe fundi i pjesës tonë të renditura.
Tani, pjesa jonë ka renditur një numër, 23,
dhe pjesa jonë unsorted ka këto pesë numra.
Le tani futni numrin e ardhshëm në pjesën tonë Unsorted, 42, në pjesën e renditura.
>> Për ta bërë këtë, ne do të duhet të krahasojnë 42 për 23 - i vetmi element në pjesën tonë të renditura deri tani.
Dyzet e dy është më i madh se 23, kështu që ne thjesht mund të append 42 deri në fund
i pjesës renditura e lista. E madhe!
Tani pjesa jonë renditura ka dy elemente, dhe pjesa jonë unsorted ka katër elemente.
Pra, le të lëvizë tani në 4, elementi tjetër në pjesën Unsorted.
Pra, ku kjo duhet të vendoset në pjesën e renditura?
>> Mos harroni, ne duam të vendosni këtë numër, në mënyrë renditura
kështu që pjesa jonë renditura mbetet renditura saktë në të gjitha kohët.
Nëse ne vendin e 4 për të drejtën e 42, pastaj lista jonë do të jetë jashtë rendit.
Pra, le të vazhdojë të lëvizur drejtë të majtë në pjesën tonë të renditjes.
Si ne shkojmë, le të zhvendoset çdo numër poshtë një vend për të bërë vend për numrin e ri.
Mirë, 4 është edhe më pak se 23, kështu që ne nuk mund të zhvillohet këtu ose.
Le të lëvizë drejtë vendin e 23 një.
>> Kjo do të thotë që ne do të donim për të vendosur 4 në slot parë në pjesën e renditura.
Vini re se si kjo hapësirë ​​në listën tashmë ishte bosh,
sepse ne kemi qenë duke lëvizur elementet e renditura poshtë si ne kemi hasur ato.
Dakord. Pra, ne jemi në gjysmë të rrugës atje.
Le të vazhdojmë algorithm tonë, duke futur 16 në pjesën e renditura.
Gjashtëmbëdhjetë është më pak se 42, kështu që le të zhvendoset e 42 në të djathtë.
Gjashtëmbëdhjetë është edhe më pak se 23, kështu që le të zhvendoset atë element.
>> Tani, 16 është më i madh se 4. Pra, kjo duket si ne do të donim për të futur 16 mes 4 dhe 23.
Ndërsa lëvizin nëpër pjesën e renditura të listës nga e djathta në të majtë,
4 është numri i parë ne kemi parë se është më i vogël se numri i
ne jemi duke u përpjekur për të futur.
Pra, tani ne mund të futur 16 në këtë slot bosh,
i cili, mos harroni, ne kemi krijuar nga elementet lëvizin në pjesën e renditjes gjatë
si ne kemi hasur ato.
>> Dakord. Tani, ne kemi katër elemente të renditura dhe Unsorted dy elemente.
Pra, le të lëvizë 8 në pjesën e renditura.
Tetë është më pak se 42.
Tetë është më pak se 23.
Dhe 8 është më pak se 16.
Por është më i madh se 8 4.
Pra, ne do të donim për të futur 8 mes 4 dhe 16.
Dhe tani ne vetëm kemi lënë një element më shumë për të zgjidhur - e 15.
Pesëmbëdhjetë është më pak se 42,
Pesëmbëdhjetë është më pak se 23.
Dhe 15 është më pak se 16.
Por 15 është më e madhe se 8.
>> Pra, këtu është vendi ku ne duam të bërë futjen tonë përfundimtar.
Dhe ne jemi duke bërë.
Ne nuk kemi elemente shumë në pjesën Unsorted,
dhe pjesa jonë është të renditura në mënyrë korrekte.
Numrat janë urdhëruar nga më i vogli tek më i madhi.
Pra, le të marrin një vështrim në disa pseudokod që përshkruan hapat që sapo kryera.
>> On line 1, ne mund të shohim se ne do të duhet të iterate mbi çdo element në listë
përveç parë, pasi elementin e parë në pjesën Unsorted thjesht do të bëhet
Elementi i parë në pjesën e renditura.
Në linjat e 2 dhe 3, ne jemi mbajtja e vendit tonë aktuale në pjesën Unsorted.
Element paraqet numrin ne jemi duke lëvizur në pjesën renditura,
dhe j paraqet indeksin tonë në pjesën Unsorted.
>> On line 4, ne jemi iterating përmes pjesës renditura nga e djathta në të majtë.
Ne duam të ndaluar iterating herë elementin në të majtë të pozicionit tonë aktual
është më pak se ne jemi duke u përpjekur element të futur.
On line 5, ne jemi zhvendosur çdo element hasim një hapësirë ​​në të djathtë.
Në këtë mënyrë, ne do të kemi një hapësirë ​​të qartë për të futur në kur kemi gjetur elementin e parë
më pak se elementi që ne jemi duke shkuar.
On line 6, ne jemi përditësimin counter tonë për të vazhduar për të lëvizur majtë nëpër pjesën e renditura.
Së fundi, në përputhje 7, ne jemi duke futur elementin në pjesën e renditura të listës.
>> Ne e dimë se kjo është në rregull për të futur në j pozicion,
sepse ne kemi lëvizur tashmë element që përdoret për të jetë atje një hapësirë ​​në të djathtë.
Mos harroni, ne jemi duke lëvizur nëpër pjesën e renditura nga djathta në të majtë,
por ne jemi duke lëvizur nëpër pjesën Unsorted nga e majta në të djathtë.
Dakord. Le të marrë tani një vështrim në sa kohë drejtimin që mori algorithm.
Ne do të pari shtrohet pyetja se sa kohë do të marrë për këtë algoritëm për të kandiduar në rastin më të keq.
Kujtojnë se ne përfaqësojmë këtë kohë running me simbol Big O.
Në mënyrë për të zgjidhur listën tonë, ne kishim për të iterate mbi elementet në pjesën Unsorted,
dhe për secilin nga këto elemente, potencialisht mbi të gjitha elementet në pjesën e renditura.
Intuitive, kjo tingëllon si një operacion (n ^ 2) O.
>> Kërkim në pseudokod tonë, ne kemi një lak mbivendosur brenda një tjetër lak,
të cilat, në të vërtetë, tingëllon si një operacion (n ^ 2) O.
Megjithatë, pjesa renditur i listës nuk përmbajnë të gjithë listën deri në fund.
Megjithatë, ne mund të potencialisht të futur një element të ri në fillim të pjesës renditura
në çdo ripërsëritje e algoritmi,
që do të thotë se ne do të duhet të shikojmë në çdo element aktualisht në pjesën e renditura.
Pra, kjo do të thotë që ne mund të potencialisht të bëjë një krahasim për elementin e dytë,
dy krahasime për elementin e tretë, dhe kështu me radhë.
Kështu, numri i përgjithshëm i hapave është shuma e numrave të plotë 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 (n - 1) mbi 2, e cila është n ekuivalent ^ 2/2 - n / 2.
Kur flasim për kohën e duhur asymptotic,
kjo ^ n 2 Termi do të dominojë këtë term n.
Pra, lloj futje është Big O (n ^ 2).
Çfarë ndodh nëse ne u lloj futje në një listë të renditura tashmë.
Në këtë rast, ne do të thjesht të ndërtuar pjesën e renditura nga e majta në të djathtë.
Pra, ne vetëm do të duhet në mënyrë të hapave n.
>> Kjo do të thotë se lloj futje ka një performancë të mirë-rasti i n,
që ne përfaqësojmë me Ω (n).
Dhe kjo është ajo për lloj futje,
vetëm një nga algoritme shumë ne mund të përdorim për të zgjidhur një listë.
Emri im është Tommy, dhe kjo është CS50.
[CS50.TV]
Oh, ju thjesht nuk mund të ndalet se sapo ajo fillon.
Oh, ne e bëmë që - Boom >>!