Quicksort njengoba indlela izinhlelo

Ngo-1960, K. A. Hoar basungula indlela ukuze ekuhlungeni okusheshayo ulwazi, baba edume kunazo. Namuhla abantu abaningi elisetshenziswa izinhlelo, njengoba has a lot of izakhiwo ezinhle: ingasetshenziswa amacala jikelele, kudingeka nje ukwenyuka kancane imemori ezengeziwe, iyahambisana izinhlobo ezahlukene uhlu kulula ukuba kusebenze. Kodwa zikhona nemiphumela ethile engathandeki, esesikhundleni Quicksort: usebenzisa umsebenzi avunyelwe eziningi amaphutha, futhi Kuthi engazinzile.

Nokho, kuyinto version okucwaningwa ngawo kakhulu. Ngemva Hoare zokukhokha kuqala, abaningi benze ucwaningo yayo aminyene. isizinda esikhulu yasungulwa imibuzo theory lokuthola isikhathi esichithwa umsebenzi, okuyinto isekelwa ubufakazi enokwehla. Kwakukhona iziphakamiso ukuthuthuka algorithm eziyisisekelo nesivinini anda.

Quicksort kuvamile kakhulu, kungatholakala yonke indawo. On osekelwe kuyo indlela luyasetshenziswa TList.Sort, esihlupha bonke izinguqulo (ngaphandle 1) Delphi, umsebenzi umtapo isikhathi kwathatha ukuqedela, qsort e C ++.

Isimiso esiyisisekelo wokusebenza kukwazi ukwakhiwa njengendlela "uhlukanise futhi nqoba". It kwenzeka breaking uhlu ngamaqembu amabili futhi ihlelwa ngoba ingxenye ngawodwana. Lokho kusho ukuthi ukunakekela ngaphezulu kumele zikhokhelwe inqubo ngokuhlukana, phakathi kwesikhathi lapho elandelayo kwenzeka: kunqunywa isici isizinda futhi kuqhathaniswa ihlelwe kabusha uhlu yakhe yonke. Yakhelwe kwesokunxele iqembu ukhetho, ukubaluleka okuyinto esingaphansi zonke ezinye izimiso yokudlulisa. It kuvela ukuthi element main ohlwini ihlelwa endaweni yalo efanele. Esigabeni esilandelayo - inselele recursive ekuhlungeni imisebenzi zombili izingxenye isihlobo kuya base. It ugcina inqubo isebenza kuphela uma Uhlu luqukethe elementi eyodwa kuphela, okungukuthi ezohlungwa. Ngakho, ukuze balukhulume umsebenzi izinhlelo njengohlobo oluthile esheshayo, kubalulekile ukwazi umsebenzi ezincane ezingeni algorithm: a) kukhethwa ilungu isizinda; b) uhlu permutation ephumelela kunazo ukukhiqiza amasethi amabili amanani amancane futhi emikhulu.

Zijwayeze nezimiso kuqala. Lapho ukhetha ilungu isizinda, kufanele kuhle ekhethiwe kusukela uhlu isilinganiso. Khona-ke phezu break ihlukaniswe halves ezimbili alinganayo. Vele ukubala inani eliyisilinganiso ohlwini kunzima kakhulu, ngakho ngisho ekuhlungeni esheshayo Bypasses nganeno calculus. Kodwa kukhethwa isici esiyisisekelo anenani elikhulu kakhulu noma ubuncane - futhi ukhetho best. Uma uzimisele ukwenza okufanayo eyodwa kudala uhlu ezingenalutho uzobe ayiqinisekile, futhi ngokugcwele yesibili. Yingakho esiphethweni sokuthi njengoba ilungu base kufanele nguye eduze isilinganiso ekhethiwe, kodwa esiphezulu kanye esincane.

Kanye ukukhetha kunqunywa, ungakwazi uqhubekele algorithm yokubola. Lokhu okuthiwa izihibe kwangaphakathi uhlobo okusheshayo. Konke lusekelwe ezimbili Rapid Finyelela izinkomba: kuqala hamba phezu izakhi kusuka kwesokunxele kuya kwesokudla, kwesibili, kunalokho, kusuka kwesokudla kuya kwesokunxele. Ucala operation ukubulawa kwesokudla: Inkomba ohlwini bese uqhathanisa wonke amagugu main. Umjikelezo kuqedile lapho isici esingaphansi noma ilingane kwegciwane. Okungukuthi, kukhona ukuqhathanisa kunciphe ukubaluleka index. Ngakolunye uhlangothi kwesokunxele uma umsebenzi usuphelile okungaphezulu kophawu noma elilingana. Lapha, lesi sifaniso Inani senyukile.

Kulesi sigaba of partitioning algorithm okuyindawo ehlanganisa quicksort ukuthi kungase kuphakame izimo ezimbili. Esokuqala siwukuthi index ngakwesokunxele lingaphansi kuka kwesokudla. Lokhu kubonisa nephutha-ke kukhona izakhi ngawo kushiwo ohlwini kukhona ngokulandelana okungalungile. Lokukhipha - ukushintsha izindawo zabo. Isimo sesibili yilapho zombili ikholomu esilingana noma zihlangene. Lokhu kubonisa ngokwahlukana ngempumelelo ohlwini, okungukuthi, umsebenzi seliphelele.