Quicksort njengendlela lokuprograma

Ngowe-1960, K. A. izimvi liphuhlise indlela ukulungiselela ukuhlela olukhawulezayo lolwazi, yaba edumileyo. Namhlanje lisetyenziswa kwi lwenkqubo, njengoko has a lot of iipropati entle: zingasetyenziswa ngenxa amatyala ngokubanzi, yona ifuna ukwanda encinane kwimemori ezongezelelweyo, ehambelanayo oluneentlobo ezahlukeneyo izintlu kwaye kulula ukuba kusebenze. Kodwa kukho ethile, nto leyo eye Quicksort: ukusebenzisa umsebenzi zavumela ezininzi iimpazamo, yaye ngandlel ezingazinzanga.

Noko ke, oko luguqulelo kakhulu kufundwa. Emva kokuba Hoare intlawulo yokuqala, abaninzi ufundisiso bayo. isiseko esikhulu yamiselwa ngemibuzo theoretical ukufumana ixesha elichithwa emsebenzini, nto leyo oluxhaswa bubungqina enokwehla. Kwakukho izindululo wokwenene ukuphucula algorithm esisiseko kunye nesantya zanda.

Quicksort kuqhelekile kakhulu, ingafunyanwa yonke. Kwi ineziseko zayo indlela iphunyezwa TList.Sort, ngoku kuzo zonke iinguqulelo (ngaphandle 1) Ugcino, umsebenzi kwithala bexesha wathabatha ukugqiba, qsort kwi C ++.

Umgaqo ezisisiseko msebenzi ukwakhiwa njenge "Yahlula kwaye woyise". Kwenzeka laphula uluhlu ibe ngamaqela amabini kwaye ezibekwe okuyingxenye nganye iyodwa. Oku kulandela ukuba ingqalelo engakumbi kufuneka ihlawulwe inkqubo yokuzahlula, apho kwenzeka oku kulandelayo: umiselwa element isiseko kwaye kakhulu ngokutsha uluhlu yakhe yonke. Kwakhelwa ekhohlo yeqela labaviwa, xabiso lazo elo ke ngaphantsi kunabo bonke abanye imithetho transfer. Kubonakala ukuba le nkalo iphambili kuluhlu ezibekwe ngayo kwindawo yayo efanelekileyo. Inqanaba elilandelayo - mngeni recursive lokhetho imisebenzi omabini amacala eziqalelo kuthelekiswa isiseko. Igcina inkqubo isebenza kuphela ukuba uluhlu iqulethe element omnye kuphela, oko kukuthi ukuba zinokulungiswa ngayo. Ngoko ke, ukuze uyoyiswa umsebenzi iprogram njenge uhlobo ekhawulezayo, kuyimfuneko ukwazi umsebenzi algorithms-kumgangatho osezantsi: a) ezikhethiweyo ilungu isiseko; b) uluhlu lobeko isebenzayo ukuvelisa iiseti ezimbini kunye neenqobo ezincinane ezinkulu.

Ziqhelanise nemigaqo kuqala. Xa ukhetha ilungu isiseko, mababe olukhethwe ukusuka kuluhlu lwe-avareji. Emva koko kwi ikhefu wahlulwa ube ziziqingatha ezibini ngokulinganayo. ukubala nje ixabiso avareji kuluhlu kunzima kakhulu, ngoko nkqu ukuhlela fastest bypasses nganeno calculus. Kodwa ke okukhethekileyo element ezisisiseko kunye ixabiso elikhulu okanye ubuncinane - nayo azikhethekanga kakuhle. Xa uzimisele enjalo omnye kudala uluhlu engenanto ziya akunakuqinisekiswa, kwaye eyesibini ngokupheleleyo. Ngoko ke kwisigqibo sokuba njengoko ilungu isiseko kufuneka kukhethwe lowo kufutshane ngumlinganiselo, kodwa kwelona qondo.

Xa ukhetho imiselwa, uyakwazi ukuqhubeka ukuya algorithm yokubola. Oku njalo kuxokwa-kweziporo ngaphakathi uhlobo ngokukhawuleza. Yonke yakhiwa nezalathiso ezimbini Ukufikelela ngokukhawuleza: kuqala, khe ndiye phezu izinto ukusuka ekhohlo ukuya ekunene, owesibini, phezu koko, ukusuka ekunene ukuya ekhohlo. Iqala ilungelo operation abulawe: isalathisi yi kuluhlu uze uthelekise onke amaxabiso elikhulu. Umjikelo lugqityiwe xa sakhi ngaphantsi kune okanye ilingana lokwaNdlalela. Oko kukuthi, kukho uthelekiso sehlise ixabiso index. Kwelinye icala lasekhohlo xa umsebenzi ugqityiwe mkhulu okanye ixabiso ngokulinganayo. Apha, i ukunyuka ixabiso uthelekiso.

Kweli nqanaba izahlulelo algorithm esiqulethe quicksort, iimeko ezimbini ezinokuvela. Eyokuqala kukuba i index ekhohlo lingaphantsi kwe ngasekunene. Oku kubonisa imposiso, ngoko kukho izinto apho bekutshiwo luhlu ngendlela engalunganga. Imveliso - ukutshintsha iindawo zabo. Imeko yesibini xa nobabini kumhlathi ilingana okanye bawela. Oku kubonisa ukwahlukana ngempumelelo kuluhlu, oko kukuthi, lo msebenzi ngoku ngokupheleleyo.