[Powered by Google Translate] [Insertion-uri-uriin ang] [Tommy MacWilliam] [Harvard University] [Ito ay CS50.TV] Natin ang isang pagtingin sa pagpapasok ng-uuri, isang algorithm para sa paglalaan ng isang listahan ng mga numero at pag-uuri-uri ang mga ito. Isang algorithm, tandaan, simpleng step-by-step na pamamaraan para sa accomplishing isang gawain. Ang pangunahing ideya sa likod ng pagpapasok ng-uuri, ay hatiin ang aming listahan sa dalawang bahagi, isang pinagsunod-sunod na bahagi at unsorted bahagi. 

Sa bawat hakbang ng algorithm, ang bilang ay inilipat mula sa unsorted bahagi sa pinagsunod-sunod bahagi hanggang sa kalaunan ang buong listahan ay pinagsunod-sunod. Narito ang listahan ng anim unsorted numero - 23, 42, 4, 16, 8, at 15. Dahil ang mga numero ay hindi lahat sa pataas na pagkakasunod-sunod, sila ay unsorted. Dahil hindi pa namin na nagsimula ang pag-uuri-uri pa, makikita namin isaalang-alang ang lahat ng anim na mga elemento sa aming unsorted bahagi. 

Sa sandaling simulan namin ang pag-uuri-uri, maglalagay kami ng mga pinagsunod-sunod numero sa kaliwa sa mga ito. Kaya, ipaalam sa magsimula sa 23, ang unang elemento sa aming listahan. Wala kaming anumang mga elemento sa aming pinagsunod-sunod na bahagi, kaya sabihin lamang isaalang-alang ang 23 sa pagsisimula at pagtatapos ng aming pinagsunod-sunod na bahagi. Ngayon, ang aming pinagsunod-sunod na bahagi ay may isang numero, 23, at ang aming unsorted bahagi ay ang limang numero. Natin ngayon ipasok ang susunod na bilang sa aming unsorted bahagi, 42, sa ang pinagsunod-sunod na bahagi. 

Upang gawin ito, makikita namin kailangan upang ihambing ang 42 sa 23 - ang tanging elemento sa aming pinagsunod-sunod bahagi sa ngayon. Apatnapu't-dalawang mas malaki kaysa sa 23, upang maaari naming lamang ikabit ang 42 sa dulo ng pinagsunod-sunod na bahagi ng listahan. Magaling! Ngayon ang aming pinagsunod-sunod na bahagi ay may dalawang mga elemento, at ang aming unsorted bahagi ay may apat na mga elemento. Kaya, sabihin ngayon lumipat sa 4, ang susunod na elemento sa unsorted bahagi. Kaya, kung saan dapat ito ilagay sa ang pinagsunod-sunod na bahagi? 

Tandaan, gusto namin na ilagay ang numero sa pinagsunod-sunod pagkakasunod-sunod kaya ang aming pinagsunod-sunod na bahagi ay nananatiling tama pinagsunod-sunod sa lahat ng oras. Kung inilagay namin ang 4 sa kanan ng 42, ang aming listahan ay sira. Kaya, sabihin magpatuloy sa paglipat kanan-papuntang-kaliwa sa aming bahagi sa-uuri. Bilang namin ilipat, sabihin shift bawat bilang down sa isang lugar upang gumawa ng room para sa mga bagong numero. Okay, 4 din mas mababa sa 23, kaya hindi namin ilagay ito dito alinman. Natin ilipat ang 23 kanang isang lugar. 

Ibig sabihin nito ay nais naming ilagay ang 4 sa unang slot sa ang pinagsunod-sunod na bahagi. Pansinin kung paano ang puwang na ito sa listahan ay na walang laman, dahil kami ay gumagalaw pinagsunod-sunod elemento bilang Nakaranas kami ng mga ito. Ayos lang. Kaya, hindi namin kalahatian doon. Natin ipagpatuloy ang aming algorithm sa pamamagitan ng pagpapasok ng 16 sa ang pinagsunod-sunod na bahagi. Labing-anim ay mas mababa sa 42, kaya sabihin shift ang 42 sa kanan. Labing-anim ay din mas mababa sa 23, kaya sabihin din shift na elemento. 

Ngayon, 16 ay mas malaki kaysa sa 4. Kaya, mukhang nais naming upang ipasok ang 16 sa pagitan ng 4 at ang 23. Habang nililipat sa pamamagitan ng pinagsunod-sunod na bahagi ng listahan mula sa karapatan sa kaliwa, 4 ay ang unang numero na iyong nakita namin na mas maliit kaysa sa bilang kami ay sinusubukan upang ipasok. Kaya, ngayon maaari naming ipasok ang 16 sa ito walang laman na slot, kung saan, Tandaan, kami nilikha ng gumalaw elemento sa bahagi-uuri sa Nakaranas kami ng mga ito. 

Ayos lang. Ngayon, kami ay may apat na pinagsunod-sunod na mga elemento at dalawang unsorted elemento. Kaya, sabihin ilipat ang 8 sa ang pinagsunod-sunod na bahagi. Walong ay mas mababa sa 42. Walong ay mas mababa sa 23. At 8 ay mas mababa sa 16. Ngunit 8 ay mas malaki kaysa sa 4. Kaya, nais naming upang ipasok ang 8 sa pagitan ng 4 at ang 16. At ngayon lang namin ng isa pang elemento sa kaliwa upang ayusin - ang 15. Labinlimang ay mas mababa sa 42, Labinlimang ay mas mababa sa 23. At 15 ay mas mababa sa 16. Ngunit 15 ay mas malaki kaysa sa 8. 

Kaya, dito ay kung saan nais namin upang gawing ang aming panghuling pagpapasok ng. At tapos na kami. Wala kaming higit pang mga elemento sa unsorted bahagi, at ang aming pinagsunod-sunod na bahagi ay sa tamang pagkakasunod-sunod. Ang mga numero ay order mula sa pinakamaliit sa pinakamalaking. Kaya, sabihin tingnan sa ilang pseudocode na naglalarawan sa mga hakbang na lang namin ginanap. 

Sa ika-1 linya, maaari naming makita na kakailanganin naming upang umulit sa paglipas ng bawat elemento sa listahan maliban sa unang, dahil ang unang elemento sa unsorted bahagi ay lamang maging sa unang elemento sa ang pinagsunod-sunod na bahagi. Sa linya 2 at 3, Pinananatili namin ang track ng aming kasalukuyang lugar sa unsorted bahagi. Element kumakatawan sa bilang kasalukuyan naming ay gumagalaw sa ang pinagsunod-sunod na bahagi, at j ay kumakatawan sa aming index sa unsorted bahagi. 

Sa linya 4, kami ay iterating sa pamamagitan ng ang pinagsunod-sunod bahagi mula sa karapatan sa kaliwa. Gusto naming itigil iterating sa sandaling ang elemento sa kaliwa ng aming kasalukuyang posisyon ay mas mababa kaysa sa elemento kami ay sinusubukan upang ipasok. Sa ika-5 linya, namin ang paglilipat ng bawat elemento kami nakatagpo ng isang espasyo sa kanan. Sa ganoong paraan, mayroon kaming isang malinaw na espasyo upang ipasok sa kapag nakita namin ang unang elemento mas mababa kaysa sa elemento na namin ang paglipat. Sa linya 6, kami ay ina-update ang aming counter upang magpatuloy upang ilipat sa kaliwa sa pamamagitan ng pinagsunod-sunod bahagi. Sa wakas, sa linya 7, kami ay pagpasok ng elemento sa pinagsunod-sunod na bahagi ng listahan. 

Alam namin na ito ay okay upang ipasok sa posisyon j, dahil Inilipat namin ang elemento na ginamit na doon isang espasyo sa kanan. Tandaan, kami ay gumagalaw sa pamamagitan ng pinagsunod-sunod bahagi mula sa karapatan sa kaliwa, ngunit kami ay gumagalaw sa pamamagitan ng unsorted bahagi mula kaliwa papuntang kanan. Ayos lang. Natin na ngayong kumuha ng isang pagtingin sa kung gaano katagal tumatakbo na algorithm kinuha. Ipapakita muna namin tanungin ang tanong kung gaano katagal aabutin para sa algorithm na ito upang tumakbo sa ang pinakamasama kaso. Manariwa sa diwa na kumakatawan namin ito tumatakbo oras may Big O pagtatanda. Upang ayusin ang aming listahan, nagkaroon kami upang umulit sa ibabaw ng mga elemento sa unsorted bahagi, at para sa bawat isa sa mga elemento, potensyal na higit sa lahat ng mga elemento sa ang pinagsunod-sunod na bahagi. Intuitively, ito tunog tulad ng isang operasyon ng O (n ^ 2). 

Naghahanap sa aming pseudocode, mayroon kaming isang loop na nested sa loob ng isa pang loop, kung saan, sa katunayan, tunog tulad ng isang operasyon ng O (n ^ 2). Gayunpaman, ang pinagsunod-sunod na bahagi ng listahan ay hindi naglalaman ang buong listahan ng hanggang sa pinakadulo. Pa rin, maaari naming potensyal na magpasok ng isang bagong elemento sa pinakadulo simula ng ang pinagsunod-sunod na bahagi sa bawat pag-ulit ng algorithm, na nangangahulugan na nais namin upang tumingin sa bawat elemento kasalukuyang sa ang pinagsunod-sunod na bahagi. Kaya, na nangangahulugang kami maaaring potensyal na gumawa ng isang paghahambing para sa pangalawang elemento, dalawang paghahambing para sa ikatlong elemento, at iba pa. Kaya, ang kabuuang bilang ng mga hakbang ay ang kabuuan ng integer mula sa 1 sa haba ng listahan minus 1. Maaari naming kumatawan ang mga ito gamit ang isang kabuuan. 

Hindi namin pumunta sa summations dito, ngunit ito lumiliko out na ang kabuuan na ito ay katumbas ng n (n - 1) sa 2, na kung saan ay katumbas n ^ 2/2 - n / 2. Kapag pakikipag-usap tungkol sa asymptotic runtime, ito n ^ 2 termino sa dominahin ito n termino. Kaya, pagpapasok ng-uuri ay Big O (n ^ 2). Paano kung tumakbo namin ang pagpapasok ng uri sa isang na pinagsunod-sunod sa listahan. Sa kasong iyon, nais lamang namin bumuo ng ang bahagi na pinagsunod-sunod mula kaliwa papuntang kanan. Kaya, kailangan lamang namin sa pagkakasunud-sunod ng mga hakbang sa n. 

Iyon ay nangangahulugang ang pagpapasok ng-uuri ay may pinakamahusay na-case na pagganap ng n, na kinakatawan namin sa Ω (n). At na ito para sa pagpapasok ng-uuri, isa lamang sa maraming mga na mga algorithm na maaari naming gamitin upang pag-uri-uriin ang isang listahan. Ang pangalan ko ay Tommy, at ito ay CS50. [CS50.TV] Oh, mo lamang ay hindi maaaring itigil na kapag nagsimula na itong. Oh, ginawa namin na - >> Boom!