Mga Karagdagang Materyal ng CS50 (Linggo 3, Mga Lektura 7 at 8): Asymptotic Notation, Sorting at Search Algorithms

Mga lektura mula sa kursong Harvard sa programming fundamentals CS50 CS50 assignments, week 3, part 1 CS50 assignments, week 3, part 2

Asymptotic notation

Ang pagsukat ng bilis ng isang algorithm sa real time—sa mga segundo at minuto—ay hindi madali. Ang isang programa ay maaaring tumakbo nang mas mabagal kaysa sa isa pa hindi dahil sa sarili nitong kawalan ng kakayahan, ngunit dahil sa kabagalan ng operating system, hindi pagkakatugma sa hardware, memorya ng computer na inookupahan ng iba pang mga proseso... Upang sukatin ang pagiging epektibo ng mga algorithm, ang mga unibersal na konsepto ay naimbento. , anuman ang kapaligiran kung saan tumatakbo ang programa. Ang asymptotic complexity ng isang problema ay sinusukat gamit ang Big O notation. Hayaang ang f(x) at g(x) ay mga function na tinukoy sa isang partikular na kapitbahayan ng x0, at ang g ay hindi nawawala doon. Pagkatapos ang f ay “O” na mas malaki kaysa sa g para sa (x -> x0) kung mayroong pare-parehong C> 0 , na para sa lahat ng x mula sa ilang kapitbahayan ng puntong x0 ang hindi pagkakapantay-pantay. |f(x)| <= C |g(x)| Bahagyang hindi gaanong mahigpit: ang f ay “O” na mas malaki kaysa sa g kung mayroong pare-parehong C>0, na para sa lahat ng x > x0 f(x) <= C*g(x) Huwag matakot sa ang pormal na kahulugan! Sa esensya, tinutukoy nito ang asymptotic na pagtaas sa oras ng pagpapatakbo ng program kapag ang dami ng iyong input data ay lumalaki patungo sa infinity. Halimbawa, inihahambing mo ang pag-uuri ng isang hanay ng 1000 elemento at 10 elemento, at kailangan mong maunawaan kung paano tataas ang oras ng pagpapatakbo ng programa. O kailangan mong kalkulahin ang haba ng isang string ng mga character sa pamamagitan ng pagpunta sa character sa pamamagitan ng character at pagdaragdag ng 1 para sa bawat character: Ang c - 1 a - 2 t - 3 asymptotic na bilis nito = O(n), kung saan ang n ay ang bilang ng mga titik sa salita. Kung magbibilang ka ayon sa prinsipyong ito, ang oras na kinakailangan upang mabilang ang buong linya ay proporsyonal sa bilang ng mga character. Ang pagbibilang ng bilang ng mga character sa isang 20-character na string ay tumatagal ng dalawang beses kaysa sa pagbibilang ng bilang ng mga character sa isang sampung-character na string. Isipin na sa variable ng haba ay nag-imbak ka ng isang halaga na katumbas ng bilang ng mga character sa string. Halimbawa, haba = 1000. Upang makuha ang haba ng isang string, kailangan mo lang ng access sa variable na ito; hindi mo na kailangang tingnan ang string mismo. At kahit paano natin baguhin ang haba, palagi nating maa-access ang variable na ito. Sa kasong ito, asymptotic speed = O(1). Ang pagbabago ng data ng input ay hindi nagbabago sa bilis ng naturang gawain; ang paghahanap ay nakumpleto sa isang pare-parehong oras. Sa kasong ito, ang programa ay asymptotically pare-pareho. Disadvantage: Nag-aaksaya ka ng memorya ng computer sa pag-iimbak ng karagdagang variable at karagdagang oras sa pag-update ng halaga nito. Kung sa tingin mo ay masama ang linear time, masisiguro namin sa iyo na maaari itong maging mas masahol pa. Halimbawa, O(n ² ). Nangangahulugan ang notasyong ito na habang lumalaki ang n, ang oras na kinakailangan upang umulit sa pamamagitan ng mga elemento (o isa pang aksyon) ay lalago nang higit at mas matindi. Ngunit para sa maliit na n, ang mga algorithm na may asymptotic na bilis O(n ² ) ay maaaring gumana nang mas mabilis kaysa sa mga algorithm na may asymptotic na bilis O(n). Ngunit sa ilang mga punto ay aabutan ng quadratic function ang linear, walang paraan sa paligid nito. Ang isa pang asymptotic complexity ay logarithmic time o O(log n). Habang tumataas ang n, ang function na ito ay tumataas nang napakabagal. Ang O(log n) ay ang oras ng pagtakbo ng classic na binary search algorithm sa isang sorted array (tandaan ang punit na direktoryo ng telepono sa lecture?). Ang array ay nahahati sa dalawa, pagkatapos ay ang kalahati kung saan matatagpuan ang elemento ay napili, at sa gayon, sa bawat oras na binabawasan ang lugar ng paghahanap ng kalahati, hinahanap namin ang elemento. Ano ang mangyayari kung natitisod tayo kaagad sa hinahanap natin, na hinati sa kalahati ang array ng data natin sa unang pagkakataon? May termino para sa pinakamagandang oras - Omega-large o Ω(n). Sa kaso ng binary search = Ω(1) (naghahanap sa pare-parehong oras, anuman ang laki ng array). Ang linear na paghahanap ay tumatakbo sa oras na O(n) at Ω(1) kung ang elementong hinahanap ay ang pinakaunang isa. Ang isa pang simbolo ay theta (Θ(n)). Ito ay ginagamit kapag ang pinakamahusay at pinakamasamang mga pagpipilian ay pareho. Ito ay angkop para sa isang halimbawa kung saan inimbak namin ang haba ng isang string sa isang hiwalay na variable, kaya para sa anumang haba sapat na upang sumangguni sa variable na ito. Para sa algorithm na ito, ang pinakamahusay at pinakamasamang kaso ay Ω(1) at O(1), ayon sa pagkakabanggit. Nangangahulugan ito na ang algorithm ay tumatakbo sa oras Θ(1).

Linear na paghahanap

Kapag nagbukas ka ng web browser, maghanap ng page, impormasyon, mga kaibigan sa mga social network, nagsasagawa ka ng paghahanap, tulad ng kapag sinusubukan mong hanapin ang tamang pares ng sapatos sa isang tindahan. Marahil ay napansin mo na ang kaayusan ay may malaking epekto sa kung paano ka naghahanap. Kung nasa closet mo ang lahat ng iyong kamiseta, kadalasan ay mas madaling mahanap ang kailangan mo sa kanila kaysa sa mga nakakalat na walang sistema sa buong silid. Ang linear na paghahanap ay isang paraan ng sunud-sunod na paghahanap, isa-isa. Kapag sinuri mo ang mga resulta ng paghahanap sa Google mula sa itaas hanggang sa ibaba, gumagamit ka ng linear na paghahanap. Halimbawa . Sabihin nating mayroon tayong listahan ng mga numero: 2 4 0 5 3 7 8 1 At kailangan nating hanapin ang 0. Nakikita natin ito kaagad, ngunit ang isang computer program ay hindi gumagana sa ganoong paraan. Nagsisimula siya sa simula ng listahan at nakikita ang numero 2. Pagkatapos ay nag-check siya, 2=0? Hindi naman, so she continues and moves on to the second character. Ang pagkabigo ay naghihintay din sa kanya doon, at sa ikatlong posisyon lamang nahanap ng algorithm ang kinakailangang numero. Pseudo-code para sa linear na paghahanap: Ang linearSearch function ay tumatanggap ng dalawang argumento bilang input - ang key key at array array[]. Ang susi ay ang gustong halaga, sa nakaraang halimbawang key = 0. Ang array ay isang listahan ng mga numero na aming titingnan. Kung wala kaming mahanap, babalik ang function -1 (isang posisyon na wala sa array). Kung nahanap ng linear na paghahanap ang gustong elemento, ibabalik ng function ang posisyon kung saan matatagpuan ang gustong elemento sa array. Ang magandang bagay tungkol sa linear na paghahanap ay gagana ito para sa anumang array, anuman ang pagkakasunud-sunod ng mga elemento: dadaan pa rin tayo sa buong array. Ito rin ang kahinaan niya. Kung kailangan mong hanapin ang numerong 198 sa hanay ng 200 numero na pinagsunod-sunod, ang for loop ay dadaan sa 198 na hakbang. Marahil ay nahulaan mo na kung aling paraan ang gumagana nang mas mahusay para sa isang pinagsunod-sunod na hanay?

Binary na paghahanap at mga puno

Isipin na mayroon kang isang listahan ng mga karakter sa Disney na pinagsunod-sunod ayon sa alpabeto at kailangan mong hanapin si Mickey Mouse. Linearly magtatagal ito. At kung gagamitin natin ang "paraan ng paghati sa direktoryo sa kalahati," dumiretso tayo kay Jasmine, at maaari nating ligtas na itapon ang unang kalahati ng listahan, na napagtatanto na hindi naroroon si Mickey. Gamit ang parehong prinsipyo, itinatapon namin ang pangalawang haligi. Sa pagpapatuloy ng diskarteng ito, mahahanap natin si Mickey sa ilang hakbang lang. Hanapin natin ang numerong 144. Hinahati natin ang listahan sa kalahati, at makarating tayo sa numerong 13. Sinusuri natin kung ang numerong hinahanap natin ay mas malaki o mas mababa sa 13. 13 < 144, upang hindi natin balewalain ang lahat sa kaliwa ng 13 at ang numerong ito mismo. Ngayon, ganito ang hitsura ng aming listahan ng paghahanap: Mayroong pantay na bilang ng mga elemento, kaya pipiliin namin ang prinsipyo kung saan pipiliin namin ang "gitna" (mas malapit sa simula o dulo). Sabihin nating pinili natin ang diskarte ng malapit sa simula. Sa kasong ito, ang aming "gitna" = 55. 55 < 144. Muli naming itinatapon ang kaliwang kalahati ng listahan. Sa kabutihang-palad para sa amin, ang susunod na average na numero ay 144. Nakakita kami ng 144 sa isang 13-element array gamit ang binary search sa tatlong hakbang lang. Ang isang linear na paghahanap ay hahawak sa parehong sitwasyon sa kasing dami ng 12 hakbang. Dahil binabawasan ng algorithm na ito ang bilang ng mga elemento sa array ng kalahati sa bawat hakbang, makikita nito ang kinakailangang isa sa asymptotic time O(log n), kung saan ang n ay ang bilang ng mga elemento sa listahan. Iyon ay, sa aming kaso, ang asymptotic time = O(log 13) (ito ay higit pa sa tatlo). Pseudocode ng binary search function: Ang function ay tumatagal ng 4 na argumento bilang input: ang gustong key, ang array array ng data [], kung saan matatagpuan ang ninanais, ang min at max ay mga pointer sa maximum at minimum na numero sa array, na tinitingnan namin ang hakbang na ito ng algorithm. Para sa aming halimbawa, ang sumusunod na larawan ay unang ibinigay: Pag-aralan pa natin ang code. midpoint ay ang aming gitna ng array. Depende ito sa mga matinding punto at nakasentro sa pagitan nila. Pagkatapos naming mahanap ang gitna, tinitingnan namin kung mas mababa ito sa aming key number. Kung gayon, kung gayon ang key ay mas malaki rin kaysa sa alinman sa mga numero sa kaliwa ng gitna, at maaari nating tawagan muli ang binary function, ngayon lamang ang ating min = midpoint + 1. Kung lumabas na ang key na iyon < midpoint, maaari nating itapon ang numerong iyon mismo at ang lahat ng mga numero , na nakahiga sa kanyang kanan. At tinawag namin ang isang binary na paghahanap sa pamamagitan ng array mula sa numero min at hanggang sa halaga (gitnang punto - 1). Panghuli, ang pangatlong sangay: kung ang halaga sa midpoint ay hindi mas malaki o mas mababa kaysa sa key, wala itong pagpipilian kundi ang maging ang gustong numero. Sa kasong ito, ibinabalik namin ito at tapusin ang programa. Sa wakas, maaaring mangyari na ang numero na iyong hinahanap ay wala sa array. Upang isaalang-alang ang kasong ito, ginagawa namin ang sumusunod na pagsusuri: At bumalik kami (-1) upang ipahiwatig na wala kaming nahanap. Alam mo na na ang binary search ay nangangailangan ng array na pagbukud-bukurin. Kaya, kung mayroon kaming isang hindi pinagsunod-sunod na array kung saan kailangan naming maghanap ng isang partikular na elemento, mayroon kaming dalawang pagpipilian:

1. Pagbukud-bukurin ang listahan at ilapat ang binary na paghahanap
2. Panatilihing laging nakaayos ang listahan habang sabay na nagdaragdag at nag-aalis ng mga elemento mula dito.

Ang isang paraan upang panatilihing nakaayos ang mga listahan ay ang paggamit ng binary search tree. Ang binary search tree ay isang istraktura ng data na nakakatugon sa mga sumusunod na kinakailangan:

• Ito ay isang puno (isang istraktura ng data na tumutulad sa isang istraktura ng puno - mayroon itong ugat at iba pang mga node (dahon) na konektado ng "mga sanga" o mga gilid na walang mga cycle)
• Ang bawat node ay may 0, 1 o 2 anak
• Parehong kaliwa at kanang subtree ay binary search tree.
• Ang lahat ng mga node ng kaliwang subtree ng isang arbitrary na node X ay may mga halaga ng data key na mas mababa kaysa sa halaga ng data key ng node X mismo.
• Ang lahat ng mga node sa kanang subtree ng isang arbitrary na node X ay may mga data key value na mas malaki kaysa o katumbas ng halaga ng data key ng node X mismo.

Pansin: ang ugat ng puno ng "programmer", hindi katulad ng tunay, ay nasa tuktok. Ang bawat cell ay tinatawag na vertex, at ang mga vertex ay konektado sa pamamagitan ng mga gilid. Ang ugat ng puno ay cell number 13. Ang kaliwang subtree ng vertex 3 ay naka-highlight sa kulay sa larawan sa ibaba: Ang aming puno ay nakakatugon sa lahat ng mga kinakailangan para sa mga binary tree. Nangangahulugan ito na ang bawat kaliwang subtree nito ay naglalaman lamang ng mga halaga na mas mababa sa o katumbas ng halaga ng vertex, habang ang kanang subtree ay naglalaman lamang ng mga halaga na mas malaki kaysa o katumbas ng halaga ng vertex. Parehong kaliwa at kanang subtree ay binary subtree mismo. Ang paraan ng pagbuo ng isang binary tree ay hindi lamang isa: sa ibaba sa larawan ay makikita mo ang isa pang opsyon para sa parehong hanay ng mga numero, at maaaring mayroong maraming mga ito sa pagsasanay. Nakakatulong ang istrukturang ito upang maisagawa ang paghahanap: hinahanap namin ang pinakamababang halaga sa pamamagitan ng paglipat mula sa itaas papunta sa kaliwa at pababa sa bawat oras. Kung kailangan mong hanapin ang maximum na numero, pumunta kami mula sa itaas pababa at sa kanan. Ang paghahanap ng isang numero na hindi ang minimum o maximum ay medyo simple din. Bumababa tayo mula sa ugat papunta sa kaliwa o sa kanan, depende kung ang ating vertex ay mas malaki o mas maliit kaysa sa hinahanap natin. Kaya, kung kailangan nating hanapin ang numerong 89, dumaan tayo sa landas na ito: Maaari mo ring ipakita ang mga numero sa pagkakasunud-sunod ng pag-uuri. Halimbawa, kung kailangan naming ipakita ang lahat ng mga numero sa pataas na pagkakasunud-sunod, kunin namin ang kaliwang subtree at, simula sa pinakakaliwang tuktok, umakyat. Ang pagdaragdag ng isang bagay sa puno ay madali din. Ang pangunahing bagay na dapat tandaan ay ang istraktura. Sabihin nating kailangan nating idagdag ang halaga 7 sa puno. Pumunta tayo sa ugat at suriin. Ang numero 7 < 13, kaya pumunta kami sa kaliwa. Nakikita namin ang 5 doon, at pumunta kami sa kanan, dahil ang 7 > 5. Dagdag pa, dahil ang 7 > 8 at 8 ay walang mga inapo, gumagawa kami ng isang sangay mula 8 sa kaliwa at ikinakabit ang 7 dito. Maaari mo ring alisin ang mga vertex mula sa ang puno, ngunit ito ay medyo mas kumplikado. Mayroong tatlong magkakaibang mga senaryo sa pagtanggal na kailangan nating isaalang-alang.

1. Ang pinakasimpleng opsyon: kailangan nating tanggalin ang isang vertex na walang mga anak. Halimbawa, ang numero 7 na idinagdag namin. Sa kasong ito, sinusundan lang namin ang landas patungo sa vertex gamit ang numerong ito at tanggalin ito.
2. Ang vertex ay may isang child vertex. Sa kasong ito, maaari mong tanggalin ang nais na vertex, ngunit ang inapo nito ay dapat na konektado sa "lolo", iyon ay, ang vertex kung saan lumaki ang agarang ninuno nito. Halimbawa, mula sa parehong puno kailangan nating alisin ang numero 3. Sa kasong ito, isasama natin ang inapo nito, isa, kasama ang buong subtree hanggang 5. Ginagawa ito nang simple, dahil ang lahat ng mga vertices sa kaliwa ng 5 ay magiging mas mababa sa numerong ito (at mas mababa sa remote triple).
3. Ang pinakamahirap na kaso ay kapag ang vertex na tinatanggal ay may dalawang anak. Ngayon ang unang bagay na kailangan nating gawin ay hanapin ang vertex kung saan nakatago ang susunod na mas malaking halaga, kailangan nating palitan ang mga ito, at pagkatapos ay tanggalin ang nais na vertex. Tandaan na ang susunod na pinakamataas na halaga ng vertex ay hindi maaaring magkaroon ng dalawang anak, kung gayon ang kaliwang anak nito ang magiging pinakamahusay na kandidato para sa susunod na halaga. Alisin natin ang root node 13 sa ating puno. Una, hahanapin natin ang numerong pinakamalapit sa 13, na mas malaki kaysa rito. Ito ay 21. Pagpalitin ang 21 at 13 at tanggalin ang 13.

Mayroong iba't ibang mga paraan upang bumuo ng mga binary tree, ang ilan ay mabuti, ang iba ay hindi masyadong mahusay. Ano ang mangyayari kung susubukan naming bumuo ng isang binary tree mula sa isang pinagsunod-sunod na listahan? Ang lahat ng mga numero ay idadagdag lamang sa kanang sangay ng nauna. Kung gusto nating makahanap ng numero, wala tayong magagawa kundi sundin na lang ang kadena pababa. Ito ay hindi mas mahusay kaysa sa linear na paghahanap. Mayroong iba pang mga istruktura ng data na mas kumplikado. Ngunit hindi namin isasaalang-alang ang mga ito sa ngayon. Sabihin na lang natin na upang malutas ang problema ng pagbuo ng isang puno mula sa isang pinagsunod-sunod na listahan, maaari mong random na paghaluin ang data ng input.

Pag-uuri ng mga algorithm

Mayroong isang hanay ng mga numero. Kailangan nating ayusin ito. Para sa pagiging simple, ipagpalagay namin na pinag-uuri-uriin namin ang mga integer sa pataas na pagkakasunud-sunod (mula sa pinakamaliit hanggang sa pinakamalaki). Mayroong ilang mga kilalang paraan upang maisakatuparan ang prosesong ito. Dagdag pa, maaari mong laging pangarapin ang paksa at magkaroon ng pagbabago ng algorithm.

Pag-uuri ayon sa pagpili

Ang pangunahing ideya ay hatiin ang aming listahan sa dalawang bahagi, pinagsunod-sunod at hindi pinagsunod-sunod. Sa bawat hakbang ng algorithm, ang isang bagong numero ay inililipat mula sa hindi pinagsunod-sunod na bahagi patungo sa pinagsunod-sunod na bahagi, at iba pa hanggang ang lahat ng mga numero ay nasa pinagsunod-sunod na bahagi.

1. Hanapin ang minimum na unsorted value.
2. Ipinagpalit namin ang halagang ito sa unang hindi na-sort na halaga, kaya inilalagay ito sa dulo ng pinagsunod-sunod na hanay.
3. Kung may natitira pang mga hindi naayos na halaga, bumalik sa hakbang 1.

Sa unang hakbang, ang lahat ng mga halaga ay hindi naayos. Tawagin natin ang unsorted part na Unsorted, at ang sorted part Sorted (ito ay mga salitang English lang, at ginagawa lang natin ito dahil mas maikli ang Sorted kaysa sa "Sorted part" at magiging mas maganda sa mga larawan). Nahanap namin ang pinakamababang numero sa hindi naayos na bahagi ng array (iyon ay, sa hakbang na ito - sa buong array). Ang numerong ito ay 2. Ngayon ay pinapalitan namin ito ng una sa mga hindi naayos at inilalagay ito sa dulo ng pinagsunod-sunod na hanay (sa hakbang na ito - sa unang lugar). Sa hakbang na ito, ito ang unang numero sa array, iyon ay, 3. Ikalawang hakbang. Hindi natin tinitingnan ang numero 2; nasa sorted subbarray na ito. Nagsisimula kaming maghanap para sa pinakamababa, simula sa pangalawang elemento, ito ay 5. Tinitiyak namin na ang 3 ay ang pinakamababa sa mga hindi pinagsunod-sunod, 5 ang una sa mga hindi pinagsunod-sunod. Ipinagpalit namin ang mga ito at nagdaragdag ng 3 sa pinagsunod-sunod na subarray. Sa ikatlong hakbang , nakita namin na ang pinakamaliit na numero sa unsorted subarray ay 4. Binago namin ito sa unang numero sa mga hindi nasort - 5. Sa ikaapat na hakbang, nakita namin na sa unsorted array ang pinakamaliit na numero ay 5. Binago namin ito mula sa 6 at idagdag ito sa pinagsunod-sunod na subarray . Kapag isang numero na lang ang natitira sa mga hindi naayos (ang pinakamalaki), nangangahulugan ito na ang buong array ay pinagsunod-sunod! Ito ang hitsura ng pagpapatupad ng array sa code. Subukan mong gawin ito sa iyong sarili. Sa parehong pinakamaganda at pinakamasamang kaso, upang mahanap ang pinakamababang hindi na-sort na elemento, dapat nating ikumpara ang bawat elemento sa bawat elemento ng unsorted array, at gagawin natin ito sa bawat pag-ulit. Ngunit hindi namin kailangang tingnan ang buong listahan, ngunit ang unsorted na bahagi lamang. Binabago ba nito ang bilis ng algorithm? Sa unang hakbang, para sa hanay ng 5 elemento, gumawa kami ng 4 na paghahambing, sa pangalawa - 3, sa pangatlo - 2. Upang makuha ang bilang ng mga paghahambing, kailangan nating pagsamahin ang lahat ng mga numerong ito. Nakukuha namin ang kabuuan Kaya, ang inaasahang bilis ng algorithm sa pinakamaganda at pinakamasamang kaso ay Θ(n ² ). Hindi ang pinaka mahusay na algorithm! Gayunpaman, para sa mga layuning pang-edukasyon at para sa maliliit na set ng data ito ay lubos na naaangkop.

Bubble sort

Ang bubble sort algorithm ay isa sa pinakasimpleng. Sumasabay kami sa buong hanay at naghahambing ng 2 kalapit na elemento. Kung sila ay nasa maling pagkakasunud-sunod, pinapalitan namin sila. Sa unang pass, lalabas ang pinakamaliit na elemento (“float”) sa dulo (kung pag-uuri-uriin natin sa pababang pagkakasunud-sunod). Ulitin ang unang hakbang kung nakumpleto ang kahit isang palitan sa nakaraang hakbang. Ayusin natin ang array. Hakbang 1: dumaan sa array. Nagsisimula ang algorithm sa unang dalawang elemento, 8 at 6, at sinusuri kung nasa tamang pagkakasunud-sunod ang mga ito. 8 > 6, kaya pinapalitan namin sila. Susunod na titingnan natin ang pangalawa at pangatlong elemento, ngayon ito ay 8 at 4. Para sa parehong mga kadahilanan, pinapalitan natin ang mga ito. Sa pangatlong pagkakataon ay inihambing namin ang 8 at 2. Sa kabuuan, gumawa kami ng tatlong palitan (8, 6), (8, 4), (8, 2). Ang value 8 ay "lumulutang" hanggang sa dulo ng listahan sa tamang posisyon. Hakbang 2: magpalit (6,4) at (6,2). 6 ay nasa penultimate na posisyon na ngayon, at hindi na kailangang ihambing ito sa nakaayos na "buntot" ng listahan. Hakbang 3: swap 4 at 2. Ang apat ay "lumulutang" sa nararapat na lugar nito. Hakbang 4: dumaan tayo sa array, ngunit wala tayong mababago. Ito ay nagpapahiwatig na ang array ay ganap na pinagsunod-sunod. At ito ang algorithm code. Subukang ipatupad ito sa C! Ang bubble sort ay tumatagal ng O(n ² ) na oras sa pinakamasamang kaso (lahat ng mga numero ay mali), dahil kailangan nating gumawa ng n hakbang sa bawat pag-ulit, kung saan mayroon ding n. Sa katunayan, tulad ng sa kaso ng algorithm ng pag-uuri ng pagpili, ang oras ay magiging mas kaunti (n ² / 2 - n / 2), ngunit ito ay maaaring mapabayaan. Sa pinakamahusay na kaso (kung ang lahat ng mga elemento ay nasa lugar na), magagawa natin ito sa n hakbang, i.e. Ω(n), dahil kailangan lang nating umulit sa array nang isang beses at tiyaking nasa lugar ang lahat ng elemento (i.e. kahit n-1 na elemento).

Pag-uuri ng pagpapasok

Ang pangunahing ideya ng algorithm na ito ay upang hatiin ang aming array sa dalawang bahagi, pinagsunod-sunod at hindi pinagsunod-sunod. Sa bawat hakbang ng algorithm, ang numero ay gumagalaw mula sa unsorted patungo sa pinagsunod-sunod na bahagi. Tingnan natin kung paano gumagana ang insertion sort gamit ang halimbawa sa ibaba. Bago tayo magsimula, ang lahat ng mga elemento ay itinuturing na hindi pinagsunod-sunod. Hakbang 1: Kunin ang unang unsorted value (3) at ipasok ito sa pinagsunod-sunod na subarray. Sa hakbang na ito, ang buong pinagsunod-sunod na subbarray, ang simula at wakas nito ay magiging tatlong ito. Hakbang 2: Mula noong 3 > 5, ilalagay namin ang 5 sa pinagsunod-sunod na subarray sa kanan ng 3. Hakbang 3: Ngayon ay nagtatrabaho kami sa pagpasok ng numero 2 sa aming pinagsunod-sunod na hanay. Inihahambing namin ang 2 sa mga halaga mula kanan hanggang kaliwa upang mahanap ang tamang posisyon. Mula noong 2 < 5 at 2 < 3 at narating na namin ang simula ng pinagsunod-sunod na subbarray. Samakatuwid, dapat nating ipasok ang 2 sa kaliwa ng 3. Upang gawin ito, ilipat ang 3 at 5 sa kanan upang magkaroon ng puwang para sa 2 at ipasok ito sa simula ng array. Hakbang 4. Maswerte tayo: 6 > 5, para maipasok natin ang numerong iyon pagkatapos mismo ng numero 5. Hakbang 5. 4 < 6 at 4 < 5, ngunit 4 > 3. Samakatuwid, alam natin na dapat ipasok ang 4 sa ang karapatan ng 3. Muli, napipilitan kaming ilipat ang 5 at 6 sa kanan upang lumikha ng puwang para sa 4. Tapos na! Generalized Algorithm: Kunin ang bawat unsorted na elemento ng n at ihambing ito sa mga halaga sa pinagsunod-sunod na subarray mula kanan pakaliwa hanggang sa makakita tayo ng angkop na posisyon para sa n (iyon ay, sa sandaling mahanap natin ang unang numero na mas mababa sa n) . Pagkatapos ay inililipat namin ang lahat ng mga pinagsunod-sunod na elemento na nasa kanan ng numerong ito sa kanan upang magbigay ng puwang para sa aming n, at ipinasok namin ito doon, at sa gayon ay pinalawak ang pinagsunod-sunod na bahagi ng array. Para sa bawat unsorted na elemento n kailangan mo:

2. Tukuyin ang lokasyon sa pinagsunod-sunod na bahagi ng array kung saan dapat ipasok ang n
3. Ilipat ang mga pinagsunod-sunod na elemento sa kanan upang lumikha ng puwang para sa n
4. Ipasok ang n sa nagresultang puwang sa pinagsunod-sunod na bahagi ng array.

At narito ang code! Inirerekomenda namin ang pagsulat ng iyong sariling bersyon ng programa sa pag-uuri.

Asymptotic na bilis ng algorithm

Sa pinakamasamang kaso, gagawa kami ng isang paghahambing sa pangalawang elemento, dalawang paghahambing sa pangatlo, at iba pa. Kaya ang ating bilis ay O(n ² ). Sa pinakamainam, gagawa kami ng isang nakaayos na array. Ang pinagsunod-sunod na bahagi, na binubuo natin mula kaliwa hanggang kanan nang walang mga pagpapasok at paggalaw ng mga elemento, ay magtatagal ng Ω(n).

Sumanib-uuri

Ang algorithm na ito ay recursive; hinahati nito ang isang malaking problema sa pag-uuri sa mga subtask, ang pagpapatupad nito ay ginagawang mas malapit sa paglutas ng orihinal na malaking problema. Ang pangunahing ideya ay hatiin ang isang hindi pinagsunod-sunod na hanay sa dalawang bahagi at pag-uri-uriin ang mga indibidwal na halves nang recursively. Sabihin nating mayroon tayong mga elementong pag-uri-uriin. Kung n < 2, natapos namin ang pag-uuri, kung hindi, pag-uuri-uriin namin ang kaliwa at kanang bahagi ng array nang hiwalay, at pagkatapos ay pagsamahin ang mga ito. Pagbukud-bukurin natin ang array. Hatiin ito sa dalawang bahagi, at ipagpatuloy ang paghahati hanggang sa makakuha tayo ng mga subarray na may sukat na 1, na malinaw na pinagsunod-sunod. Dalawang pinagsunod-sunod na subarray ay maaaring pagsamahin sa O(n) oras gamit ang isang simpleng algorithm: alisin ang mas maliit na numero sa simula ng bawat subarray at ipasok ito sa pinagsamang array. Ulitin hanggang mawala ang lahat ng elemento. Ang merge sort ay tumatagal ng O(nlog n) na oras para sa lahat ng kaso. Habang hinahati namin ang mga arrays sa kalahati sa bawat antas ng recursion nakakakuha kami ng log n. Pagkatapos, ang pagsasama-sama ng mga subarray ay nangangailangan lamang ng n paghahambing. Samakatuwid O(nlog n). Ang pinakamaganda at pinakamasamang kaso para sa merge sort ay pareho, ang inaasahang oras ng pagpapatakbo ng algorithm = Θ(nlog n). Ang algorithm na ito ay ang pinaka-epektibo sa mga isinasaalang-alang.