Quicksort monga njira mapulogalamu

Mu 1960, K. A. Hoar njira ina kwa kusanja mofulumira zambiri, anakhala wotchuka kwambiri. Lero chimagwiritsidwa ntchito mapulogalamu, monga ali zambiri katundu zabwino: zikhoza kugwiritsidwa ntchito kwa milandu onse, pamafunika kuwonjezeka yaing'ono kukumbukira zina, n'zogwirizana ndi osiyanasiyana mndandanda ndi zovuta kuzitsatira. Koma pali zovuta, amene ali Quicksort: pogwiritsa ntchito analola kwambiri cha zolakwa, ndipo penapake osakhazikika.

Komabe, Baibulo ambiri kuphunzira. Pambuyo malipiro oyamba Hoare, ambiri kuchita kafukufuku wake wandiweyani. chachikulu m'munsi unakhazikitsidwa pa mafunso ongolankhula kupeza nthawi imene ntchito, amene underpinned ndi umboni wazotsatira. Panali maganizo kwenikweni kusintha aligorivimu zikuluzikulu ndi kuchuluka liwiro.

Quicksort sizachilendo, angapezeke kulikonse. Pa maziko ake njira akuyendera TList.Sort, pano mu Mabaibulo onse (kupatula 1) Delphi, laibulale ntchito kwa nthawi anatenga kumaliza, qsort mu C ++.

Mfundo zikuluzikulu za ntchito akhoza kukonza monga "kugawaniza ndi kugonjetsa". Zimachitika kuswa mndandanda m'magulu awiri ndipo zosankhidwa kwa mbali palokha. Tidziwanso kuti kwambiri ziperekedwe kwa ndondomeko kupatukana, imene zotsatirazi kumachitika: anatsimikiza ndi chinthu m'munsi ndipo ndi kuwayalanso mndandanda wake wonse. Anamanga kumanzere kwa gulu ofuna, phindu lake zosakwana malamulo ena onse kutengerapo. Iwo likukhalira kuti mbali yaikulu mu mndandanda zosankhidwa ndi mu malo ake oyenera. Siteji yotsatira - kovuta recursive kusanja ntchito kwa mbali zonse za zinthu wachibale maziko a. Izo zikutsiriza zimachitika pokhapokha ngati mndandanda uli kokha chinthu chimodzi, chimene chiri kuti zosankhidwa. Motero, kuti kuchidziwa ndi mapulogalamu ntchito monga mtundu mofulumira, m'pofunika kudziwa ntchito ya ma aligorivimu m'munsi mlingo: a) kusankha membala m'munsi; b) mndandanda wa permutation yabwino kwambiri kubala miyeso iwiri ndi mfundo zing'onozing'ono ndiponso zikuluzikulu.

Dziŵani ndi zoyamba. Posankha membala m'munsi, ayenera Choncho anasankha kuchokera pa ndandanda wa pafupifupi. Pamenepo kuswa lagawidwa amachepetsa awiri ofanana. Monga kuwerengera phindu pafupifupi mu mndandanda ndi zovuta, kotero ngakhale kusanja yachangu bypasses ili mbali kakyulasi. Koma kusankha zinthu zofunika ndi mtengo pazipita kapena osachepera - komanso si njira yabwino. Pankhaniyi mwatsimikiza mtima kuchita zimenezi wa munthu amalenga mndandanda kanthu adzakhala kungakupatseni ndi wachiwiri zonse. Choncho mapeto kuti membala m'munsi ayenera wosankhidwa kuti uli pafupi ndi pafupifupi, koma pa pazipita ndi osachepera.

Kamodzi kusankha anatsimikiza, mukhoza chitani kuwonongeka aligorivimu. Izi otchedwa zingwe zopota mkati mtundu mwamsanga. Zonse wamangidwa pa awiri Access zolozera Rapid: woyamba kupita pa zinthu kuchokera kumanzere, wachiwiri M'malo mwake, kuyambira kumanja kupita kumanzere. Ayamba ntchito kuphedwa lamanja: zosonyezera ndi pa mndandanda ndipo yerekezani makhalidwe onse waukulu. The mkombero uli wangwiro pamene amafotokozera ndi zosakwana kapena wolingana ndi m'mene ziriri pano ndi. Kuti pali poyerekeza ndi amachepetsa mtengo wa index lapansi. Kudzanja lamanzere pamene ntchito yatha kuposa kapena ofanana. Apa, kufanizitsa mtengo ukuwonjezeka.

Pa nthawi imeneyi a partitioning aligorivimu amene limapangidwa quicksort, zinthu ziwiri angakhalepo. Loyamba ndilochokera kuti index kumanzere ndi zosakwana bwino. Izi zikusonyeza kulakwitsa, ndiye pali zinthu zomwe zinafotokozedwa mu mndandanda ali mu dongosolo cholakwika. Linanena bungwe - kusintha malo awo. The vuto lachiwiri ndi pamene onse a mzati ndi wofanana kapena anawoloka. Izi zikusonyeza kulekanitsa kwa mndandanda bwino, ndiye kuti ntchito ya kumapeto.