Materi Tambahan CS50 (Minggu 3, Kuliah 7 lan 8): Notasi Asimtotik, Algoritma Pengurutan lan Telusuran

Kuliah saka kursus Harvard babagan dhasar pemrograman Tugas CS50 CS50, minggu 3, bagean 1 Tugas CS50, minggu 3, bagean 2

Notasi asimtotik

Ngukur kacepetan algoritma ing wektu nyata-ing detik lan menit-ora gampang. Siji program bisa mlaku luwih alon tinimbang liyane ora amarga inefficiency dhewe, nanging amarga slowness saka sistem operasi, incompatibility karo hardware, memori komputer dikuwasani dening pangolahan liyane ... Kanggo ngukur efektifitas saka algoritma, konsep universal wis nemokke. , preduli saka lingkungan ing ngendi program lagi mlaku. Kompleksitas asimtotik saka masalah diukur nggunakake notasi Big O. Dadi f(x) lan g(x) dadi fungsi sing ditetepake ing lingkungan tartamtu saka x0, lan g ora ilang ing kono, banjur f luwih "O" tinimbang g kanggo (x -> x0) yen ana konstanta C> 0 , sing kanggo kabeh x saka sawetara tetanggan saka titik x0 ketimpangan tetep. |f(x)| <= C |g(x)| Rada kurang ketat: f "O" luwih gedhe tinimbang g yen ana konstanta C>0, kang kanggo kabeh x > x0 f(x) <= C*g(x) Aja wedi definisi formal! Ateges, iku nemtokake kenaikan asimtotik ing wektu mlaku program nalika jumlah data input mundhak menyang tanpa wates. Contone, sampeyan mbandhingake ngurutake array 1000 unsur lan 10 unsur, lan sampeyan kudu ngerti carane wektu mlaku program bakal nambah. Utawa sampeyan kudu ngetung dawa senar saka karakter dening arep karakter dening karakter lan nambah 1 kanggo saben karakter: c - 1 a - 2 t - 3 Kacepetan asimtotik sawijining = O (n), ngendi n iku nomer aksara ing tembung. Yen sampeyan ngetung miturut prinsip iki, wektu sing dibutuhake kanggo ngetung kabeh baris sebanding karo jumlah karakter. Ngetung jumlah karakter ing senar 20 karakter njupuk kaping pindho anggere ngetung jumlah karakter ing senar sepuluh karakter. Mbayangno yen ing variabel dawa sampeyan nyimpen nilai sing padha karo jumlah karakter ing senar. Contone, dawa = 1000. Kanggo entuk dawa senar, sampeyan mung butuh akses menyang variabel iki, sampeyan ora kudu ndeleng senar kasebut. Lan ora ketompo carane ngganti dawa, kita tansah bisa ngakses variabel iki. Ing kasus iki, kacepetan asimtotik = O(1). Ngganti data input ora ngganti kacepetan tugas kasebut; telusuran rampung ing wektu sing tetep. Ing kasus iki, program asymptotically konstan. kerugian: Sampeyan sampah memori komputer nyimpen variabel tambahan lan wektu tambahan nganyari Nilai. Yen sampeyan mikir yen wektu linear iku ala, kita bisa njamin sampeyan bisa dadi luwih elek. Contone, O(n ² ). Notasi iki tegese minangka n mundak akeh, wektu sing dibutuhake kanggo iterate liwat unsur (utawa tumindak liyane) bakal tuwuh liyane lan liyane banget. Nanging kanggo n cilik, algoritma kanthi kacepetan asimtotik O(n ² ) bisa luwih cepet tinimbang algoritma kanthi kacepetan asimtotik O(n). Nanging ing sawetara titik fungsi kuadrat bakal nyusul siji linear, ora ana cara watara. Kompleksitas asimtotik liyane yaiku wektu logaritma utawa O(log n). Nalika n mundhak, fungsi iki mundhak banget alon. O(log n) iku wektu mlaku saka algoritma telusuran binar klasik ing array diurutake (elinga direktori telpon ambruk ing kuliah?). Array kasebut dipérang dadi loro, banjur setengah ing ngendi unsur kasebut dipilih, lan saben wektu ngurangi area panelusuran kanthi setengah, kita nggoleki unsur kasebut. Apa sing kedadeyan yen kita langsung kesandhung apa sing kita goleki, mbagi larik data dadi setengah kanggo pisanan? Ana istilah kanggo wektu paling apik - Omega-gedhe utawa Ω (n). Ing kasus panelusuran biner = Ω(1) (nemokake ing wektu sing tetep, preduli saka ukuran array). Panelusuran linear lumaku ing wektu O(n) lan Ω(1) yen unsur sing digoleki iku sing paling dhisik. Simbol liyane yaiku theta (Θ(n)). Iki digunakake nalika pilihan sing paling apik lan paling awon padha. Iki cocok kanggo conto ing ngendi kita nyimpen dawa senar ing variabel sing kapisah, supaya dawa apa wae cukup kanggo ngrujuk marang variabel iki. Kanggo algoritma iki, kasus sing paling apik lan paling awon yaiku Ω (1) lan O (1). Iki tegese algoritma mlaku ing wektu Θ(1).

Panelusuran linear

Nalika sampeyan mbukak browser web, goleki kaca, informasi, kanca ing jaringan sosial, sampeyan lagi nggoleki, kaya nalika nyoba nemokake sepatu sing pas ing toko. Sampeyan bisa uga ngerteni manawa ketertiban duwe pengaruh gedhe babagan cara sampeyan nggoleki. Yen sampeyan duwe kabeh kaos ing lemari, iku biasane luwih gampang kanggo nemokake siji sing perlu ing antarane wong-wong mau saka ing antarane sing kasebar tanpa sistem saindhenging kamar. Panelusuran linear minangka cara nggoleki urutan, siji-siji. Nalika sampeyan mriksa asil panelusuran Google saka ndhuwur nganti ngisor, sampeyan nggunakake telusuran linear. Tuladha . Ayo dadi ngomong kita duwe dhaptar nomer: 2 4 0 5 3 7 8 1 Lan kita kudu golek 0. We ndeleng langsung, nanging program komputer ora bisa. Dheweke wiwit ing wiwitan dhaptar lan ndeleng nomer 2. Banjur dheweke mriksa, 2 = 0? Ora, dadi dheweke terus lan pindhah menyang karakter kapindho. Gagal uga nunggu dheweke, lan mung ing posisi katelu algoritma nemokake nomer sing dibutuhake. Pseudo-code kanggo telusuran linear: Fungsi linearSearch nampa rong argumen minangka input - tombol tombol lan array array []. Tombol kasebut minangka nilai sing dikarepake, ing tombol conto sadurunge = 0. Array minangka dhaptar nomer sing kita butuhake. bakal katon liwat. Yen kita ora nemokake apa-apa, fungsi bakal bali -1 (posisi sing ora ana ing array). Yen telusuran linear nemokake unsur sing dikarepake, fungsi kasebut bakal ngasilake posisi ing ngendi unsur sing dikarepake dumunung ing array. Sing apik babagan telusuran linear yaiku bisa digunakake kanggo array apa wae, preduli saka urutan unsur: kita isih bakal ngliwati kabeh array. Iki uga kelemahane. Yen sampeyan kudu golek nomer 198 ing Uploaded 200 nomer diurutake supaya, kanggo daur ulang bakal liwat 198 langkah. Sampeyan mbokmenawa wis ngira cara apa sing luwih apik kanggo array sing diurutake?

Panelusuran binar lan wit

Bayangake sampeyan duwe dhaptar karakter Disney sing diurutake miturut abjad lan sampeyan kudu nemokake Mickey Mouse. Linear bakal njupuk wektu dawa. Lan yen kita nggunakake "metode nyuwek direktori ing setengah," kita langsung menyang Jasmine, lan kita bisa kanthi aman mbuang separo pisanan saka dhaftar, éling sing Mickey ora bisa ana. Nggunakake prinsip sing padha, kita mbuwang kolom kapindho. Terus strategi iki, kita bakal nemokake Mickey mung sawetara langkah. Ayo goleki nomer 144. Kita dibagi daftar dadi setengah, lan kita tekan nomer 13. Kita ngevaluasi apa nomer sing digoleki luwih gedhe utawa kurang saka 13. 13 < 144, supaya kita bisa nglirwakake kabeh sing ana ing sisih kiwa. 13 lan nomer iki dhewe. Saiki dhaptar telusuran kita katon kaya iki: Ana sawetara unsur, mula kita milih prinsip sing kita pilih "tengah" (nyedhaki wiwitan utawa pungkasan). Ayo kita ngomong yen kita milih strategi sing cedhak karo wiwitan. Ing kasus iki, kita "tengah" = 55. 55 < 144. Kita mbuwang setengah kiwa dhaptar maneh. Untunge kanggo kita, nomer rata-rata sabanjure yaiku 144. Kita nemokake 144 ing array 13-elemen nggunakake panelusuran binar mung telung langkah. Panelusuran linear bakal nangani kahanan sing padha ing 12 langkah. Wiwit algoritma iki nyuda jumlah unsur ing Uploaded dening setengah ing saben langkah, bakal nemokake siji sing dibutuhake ing wektu asimtotik O (log n), ngendi n iku nomer unsur ing dhaftar. Yaiku, ing kasus kita, wektu asimtotik = O(log 13) (iki luwih saka telu). Pseudocode saka fungsi telusuran binar: Fungsi kasebut njupuk 4 argumen minangka input: tombol sing dikarepake, array array data [], ing ngendi sing dipengini dumunung, min lan max minangka penunjuk menyang nomer maksimum lan minimal ing array, sing kita ndeleng ing langkah iki saka algoritma. Contone, gambar ing ngisor iki pisanan diwenehi: Ayo analisa kode luwih lanjut. midpoint punika tengah kita Uploaded. Iku gumantung ing titik nemen lan tengah ing antarane. Sawise kita nemokake tengah, kita mriksa yen kurang saka nomer kunci. Yen mangkono, banjur tombol uga luwih gedhe tinimbang nomer ing sisih kiwa tengah, lan kita bisa nelpon maneh fungsi binar, mung saiki min = titik tengah + 1. Yen ternyata tombol <titik tengah, kita bisa mbuwang. nomer kasebut dhewe lan kabeh nomer , dumunung ing sisih tengen. Lan kita nelpon telusuran binar liwat array saka nomer min lan nganti nilai (titik tengah - 1). Pungkasan, cabang katelu: yen nilai ing titik tengah ora luwih gedhe utawa kurang saka tombol, ora ana pilihan nanging dadi nomer sing dikarepake. Ing kasus iki, kita bali lan rampung program. Pungkasan, bisa uga nomer sing sampeyan goleki ora ana ing array. Kanggo njupuk kasus iki, kita nindakake mriksa ing ngisor iki: Lan kita bali (-1) kanggo nuduhake yen kita ora nemu apa-apa. Sampeyan wis ngerti yen telusuran binar mbutuhake array supaya diurutake. Dadi, yen kita duwe array sing ora diurutake sing kudu golek unsur tartamtu, kita duwe rong pilihan:

1. Urut dhaptar lan aplikasi telusuran binar
2. Tansah dhaftar tansah diurutake nalika bebarengan nambah lan mbusak unsur saka iku.

Salah siji cara supaya dhaptar diurutake yaiku nggunakake wit telusuran binar. Wit telusuran binar minangka struktur data sing nyukupi syarat ing ngisor iki:

• Iku wit (struktur data sing niru struktur wit - duwe oyod lan simpul liyane (godhong) sing disambungake dening "cabang" utawa pinggir tanpa siklus)
• Saben simpul duwe 0, 1 utawa 2 anak
• Subtree kiwa lan tengen minangka wit telusuran binar.
• Kabeh simpul subtree kiwa saka simpul X sing sewenang-wenang nduweni nilai kunci data sing kurang saka nilai kunci data simpul X dhewe.
• Kabeh simpul ing subtree sisih tengen simpul X duwe nilai kunci data sing luwih gedhe tinimbang utawa padha karo nilai kunci data simpul X dhewe.

Manungsa waé: oyod saka wit "programmer", ora kaya sing asli, ana ing sisih ndhuwur. Saben sel diarani vertex, lan vertex disambungake kanthi pinggir. Oyod wit iku nomer sel 13. Subtree kiwa vertex 3 disorot warna ing gambar ing ngisor iki: Wit kita nyukupi kabeh syarat kanggo wit binar. Iki tegese saben subtree kiwa mung ngemot nilai sing kurang saka utawa padha karo nilai vertex, dene subtree tengen mung ngemot nilai sing luwih gedhe tinimbang utawa padha karo nilai vertex. Loro-lorone subtree kiwa lan tengen minangka subtree binar. Cara mbangun wit binar ora mung siji-sijine: ing gambar ing ngisor iki sampeyan ndeleng pilihan liyane kanggo nomer sing padha, lan bisa uga ana akeh ing praktik. Struktur iki mbantu nindakake telusuran: kita nemokake nilai minimal kanthi mindhah saka ndhuwur menyang kiwa lan mudhun saben wektu. Yen sampeyan perlu kanggo golek nomer maksimum, kita pindhah saka ndhuwur mudhun lan nengen. Nemokake nomer sing ora minimal utawa maksimum uga cukup prasaja. Kita mudhun saka oyod ngiwa utawa nengen, gumantung apa vertex kita luwih gedhe utawa luwih cilik tinimbang sing kita goleki. Dadi, yen kita kudu golek nomer 89, kita liwat dalan iki: Sampeyan uga bisa nampilake nomer ing urutan ngurutake. Contone, yen kita kudu nampilake kabeh nomer ing urutan munggah, kita njupuk subtree kiwa lan, miwiti saka vertex paling kiwa, munggah. Nambahake soko ing wit uga gampang. Wangsulan utama sing kudu dielingake yaiku struktur. Ayo dadi ngomong kita kudu nambah nilai 7 kanggo wit. Ayo menyang ROOT lan mriksa. Nomer 7 < 13, dadi ngiwa. Kita ndeleng 5 ana, lan kita pindhah menyang sisih tengen, wiwit 7> 5. Salajengipun, wiwit 7> 8 lan 8 ora duwe turunan, kita mbangun cabang saka 8 ing sisih kiwa lan masang 7. Sampeyan uga bisa mbusak simpul saka wit, nanging iki rada luwih rumit. Ana telung skenario pambusakan sing beda-beda sing kudu digatekake.

1. Pilihan sing paling gampang: kita kudu mbusak vertex sing ora duwe anak. Contone, nomer 7 kita mung ditambahake. Ing kasus iki, kita mung tindakake path menyang vertex karo nomer iki lan mbusak.
2. A vertex duwe siji anak vertex. Ing kasus iki, sampeyan bisa mbusak vertex sing dikarepake, nanging turunane kudu disambungake menyang "mbah", yaiku, vertex saka ngendi leluhure langsung tuwuh. Contone, saka wit sing padha kita kudu mbusak nomer 3. Ing kasus iki, kita gabung karo turunane, siji, bebarengan karo kabeh subtree kanggo 5. Iki rampung mung, amarga kabeh vertex ing sisih kiwa 5 bakal kurang saka nomer iki (lan kurang saka telung remot).
3. Kasus sing paling angel yaiku nalika vertex sing dibusak duwe anak loro. Saiki bab pisanan sing kudu ditindakake yaiku nemokake vertex sing didhelikake nilai sing luwih gedhe, kita kudu ngganti, banjur mbusak vertex sing dikarepake. Elinga yen vertex nilai paling dhuwur sabanjure ora bisa duwe anak loro, banjur anak kiwa bakal dadi calon paling apik kanggo nilai sabanjure. Ayo mbusak simpul ROOT saka wit kita 13. Kaping pisanan, goleki nomer sing paling cedhak karo 13, sing luwih gedhe tinimbang. Iki 21. Ganti 21 lan 13 lan mbusak 13.

Ana macem-macem cara kanggo mbangun wit binar, sawetara apik, liyane ora apik. Apa sing kedadeyan yen kita nyoba mbangun wit binar saka dhaptar sing diurutake? Kabeh nomer mung bakal ditambahake menyang cabang tengen sing sadurunge. Yen kita pengin golek nomer, kita ora duwe pilihan nanging mung tindakake chain mudhun. Iku ora luwih apik tinimbang panelusuran linear. Ana struktur data liyane sing luwih rumit. Nanging kita ora bakal nganggep dheweke saiki. Ayo ngomong yen kanggo ngatasi masalah mbangun wit saka dhaptar sing diurutake, sampeyan bisa nyampur data input kanthi acak.

Algoritma ngurutake

Ana macem-macem nomer. Kita kudu ngurutake. Kanggo gamblang, kita bakal nganggep yen kita ngurutake integer ing urutan munggah (saka paling cilik nganti paling gedhe). Ana sawetara cara sing dikenal kanggo ngrampungake proses iki. Kajaba iku, sampeyan bisa tansah ngimpi topik lan nggawe modifikasi algoritma.

Ngurutake miturut pilihan

Ide utama yaiku pamisah dhaptar kita dadi rong bagean, diurut lan ora diurut. Ing saben langkah algoritma, nomer anyar dipindhah saka bagean sing ora diurut menyang bagean sing diurutake, lan sateruse nganti kabeh nomer ana ing bagean sing diurutake.

1. Golek nilai unsorted minimal.
2. Kita ngganti nilai iki karo nilai unsorted pisanan, mangkono manggonke ing mburi Uploaded diurutake.
3. Yen isih ana nilai sing ora diurut, bali menyang langkah 1.

Ing langkah pisanan, kabeh nilai ora diurutake. Ayo disebut bagean unsorted Unsorted, lan bagean diurutake Urut (iki mung tembung Inggris, lan kita nindakake iki mung amarga Diurutake luwih cendhek tinimbang "Diurutake bagean" lan bakal katon luwih apik ing gambar). Kita nemokake nomer minimal ing bagean unsorted array (yaiku, ing langkah iki - ing kabeh array). Iki nomer 2. Saiki kita ngganti karo pisanan antarane unsorted lan sijine iku ing mburi Uploaded diurutake (ing langkah iki - ing Panggonan pisanan). Ing langkah iki, iki nomer pisanan ing array, yaiku 3. Langkah loro. Kita ora ndeleng nomer 2; wis ana ing subarray sing diurutake. Kita miwiti nggoleki minimal, wiwit saka unsur kapindho, iki 5. Kita priksa manawa 3 iku minimal antarane unsorted, 5 pisanan antarane unsorted. Kita ngganti lan nambah 3 menyang subarray sing diurutake. Ing langkah katelu , kita weruh yen nomer paling cilik ing subarray sing ora diurutake yaiku 4. Kita ngganti karo nomer pisanan ing antarane sing ora diurutake - 5. Ing langkah kaping papat, kita nemokake yen ing array sing ora diurutake nomer paling cilik yaiku 5. Kita ngganti saka 6 lan nambah menyang subbarray diurutake. Nalika mung siji nomer tetep antarane unsorted gedhe-gedhe (paling gedhe), iki tegese kabeh Uploaded wis diurutake! Iki minangka implementasine array ing kode. Coba gawe dhewe. Ing kasus paling apik lan paling awon, kanggo nemokake unsur unsorted minimal, kita kudu mbandhingaké saben unsur karo saben unsur saka Uploaded unsorted, lan kita bakal nindakake iki ing saben pengulangan. Nanging kita ora perlu kanggo ndeleng kabeh dhaftar, nanging mung bagean unsorted. Apa iki ngganti kacepetan algoritma? Ing langkah pisanan, kanggo Uploaded 5 unsur, kita nggawe 4 bandingaken, ing kaloro - 3, ing katelu - 2. Kanggo njaluk nomer mbandhingaké, kita kudu nambah munggah kabeh nomer iki. We njaluk jumlah Dadi, kacepetan samesthine saka algoritma ing kasus paling apik lan paling awon punika Θ(n ² ). Ora algoritma sing paling efisien! Nanging, kanggo tujuan pendhidhikan lan kanggo set data cilik, cukup ditrapake.

Urut gelembung

Algoritma ngurutake gelembung minangka salah sawijining sing paling gampang. We pindhah bebarengan kabeh Uploaded lan mbandhingaké 2 unsur tetanggan. Yen ana ing urutan sing salah, kita ngganti. Ing pass pisanan, unsur paling cilik bakal katon ("ngambang") ing pungkasan (yen diurutake ing urutan mudhun). Baleni langkah pisanan yen paling ora siji ijol-ijolan wis rampung ing langkah sadurunge. Ayo ngurutake array. Langkah 1: pindhah liwat array. Algoritma kasebut diwiwiti kanthi rong unsur pisanan, 8 lan 6, lan mriksa manawa ana ing urutan sing bener. 8> 6, supaya kita ngganti. Sabanjure kita katon ing unsur kapindho lan katelu, saiki iki 8 lan 4. Kanggo alasan sing padha, kita ngganti. Kanggo kaping telune kita mbandhingake 8 lan 2. Secara total, kita nggawe telung ijol-ijolan (8, 6), (8, 4), (8, 2). Nilai 8 "ngambang" nganti pungkasan dhaptar ing posisi sing bener. Langkah 2: swap (6,4) lan (6,2). 6 saiki ana ing posisi penultimate, lan ora perlu mbandhingake karo "buntut" sing wis diurutake saka dhaptar. Langkah 3: swap 4 lan 2. Papat "ngambang" menyang panggonan sing bener. Langkah 4: kita ngliwati array, nanging ora ana sing kudu diganti. Iki sinyal sing Uploaded rampung diurutake. Lan iki kode algoritma. Coba terapake ing C! Gelembung Urut njupuk O (n ² ) wektu ing kasus paling awon (kabeh nomer salah), awit kita kudu njupuk n langkah ing saben pengulangan, kang ana uga n. Ing kasunyatan, kaya ing kasus algoritma ngurutake pilihan, wektu bakal rada kurang (n ² / 2 - n / 2), nanging iki bisa diabaikan. Ing kasus paling apik (yen kabeh unsur wis ing Panggonan), kita bisa nindakake ing n langkah, i.e. Ω(n), amarga kita mung kudu ngulang array sapisan lan priksa manawa kabeh unsur ana ing panggonane (yaiku unsur n-1).

Urut sisipan

Ide utama algoritma iki yaiku kanggo mbagi array kita dadi rong bagean, diurut lan ora diurut. Ing saben langkah algoritma, nomer pindhah saka unsorted menyang bagean diurutake. Ayo goleki kepiye cara ngurutake sisipan nggunakake conto ing ngisor iki. Sadurunge kita miwiti, kabeh unsur dianggep unsorted. Langkah 1: Njupuk nilai unsorted pisanan (3) lan lebokake menyang subbarray diurutake. Ing langkah iki, kabeh subarray sing diurutake, wiwitan lan pungkasane bakal dadi telu. Langkah 2: Wiwit 3> 5, kita bakal nglebokake 5 menyang subarray sing diurut ing sisih tengen 3. Langkah 3: Saiki kita bisa nglebokake nomer 2 menyang array sing diurutake. Kita mbandhingake 2 karo nilai saka tengen ngiwa kanggo nemokake posisi sing bener. Wiwit 2 < 5 lan 2 < 3 lan kita wis tekan wiwitan subbarray sing diurutake. Mulane, kita kudu nglebokake 2 ing sisih kiwa 3. Kanggo nindakake iki, mindhah 3 lan 5 ing sisih tengen supaya ana papan kanggo 2 lan lebokake ing wiwitan array. Langkah 4. Kita begja: 6 > 5, supaya kita bisa nglebokake nomer kasebut sakwise nomer 5. Langkah 5. 4 < 6 lan 4 < 5, nanging 4 > 3. Mulane, kita ngerti yen 4 kudu dilebokake menyang tengenipun 3. Maneh, kita dipeksa kanggo mindhah 5 lan 6 ing sisih tengen kanggo nggawe longkangan kanggo 4. Rampung! Algoritma Umum: Njupuk saben unsur unsorted saka n lan mbandhingaké karo nilai ing subbarray diurutake saka tengen ngiwa nganti kita nemokake posisi cocok kanggo n (yaiku, nalika kita nemokake nomer pisanan sing kurang saka n) . Banjur kita ngalih kabeh unsur diurutake sing ana ing sisih tengen nomer iki ing sisih tengen kanggo nggawe kamar kanggo n, lan kita masang ana, mangkono nggedhekake bagean diurutake saka Uploaded. Kanggo saben unsur unsorted n sampeyan kudu:

2. Nemtokake lokasi ing bagean diurutake saka Uploaded ngendi n kudu dilebokake
3. Nggeser unsur diurutake menyang tengen kanggo nggawe longkangan kanggo n
4. Lebokake n menyang longkangan asil ing bagean diurutake saka Uploaded.

Lan iki kode! Disaranake nulis versi program ngurutake sampeyan dhewe.

Kacepetan asimtotik saka algoritma

Ing kasus paling awon, kita bakal nggawe siji comparison karo unsur kapindho, loro bandingaken karo katelu, lan ing. Dadi kecepatan kita yaiku O(n ² ). Paling apik, kita bakal nggarap array sing wis diurutake. Bagian sing diurutake, sing dibangun saka kiwa menyang tengen tanpa sisipan lan obahe unsur, bakal mbutuhake wektu Ω(n).

Gabung urut

Algoritma iki rekursif; iki ngilangi siji masalah ngurutake gedhe dadi subtugas, eksekusi sing ndadekake luwih cedhak kanggo ngrampungake masalah gedhe asli. Ide utama yaiku pamisah array sing ora diurut dadi rong bagean lan ngurutake bagian individu kanthi rekursif. Ayo dadi ngomong kita duwe n unsur kanggo Ngurutake. Yen n < 2, kita rampung ngurutake, yen ora, kita ngurutake bagean kiwa lan tengen array kanthi kapisah, banjur gabungke. Ayo diurutake array, dibagi dadi rong bagean, terus dibagi nganti entuk subbarray ukuran 1, sing jelas diurutake. Loro subarray sing diurutake bisa digabung ing wektu O(n) nggunakake algoritma sing prasaja: mbusak angka sing luwih cilik ing wiwitan saben subarray lan lebokake menyang array gabungan. Baleni nganti kabeh unsur ilang. Gabung urut njupuk wektu O(nlog n) kanggo kabeh kasus. Nalika kita misahake susunan dadi setengah ing saben tingkat rekursi, kita entuk log n. Banjur, nggabungake subarrays mung mbutuhake n mbandhingake. Mulane O(nlog n). Kasus sing paling apik lan paling awon kanggo ngurutake gabungan padha, wektu mlaku algoritma = Θ(nlog n). Algoritma iki paling efektif ing antarane sing dianggep.