Quicksort a matsayin shirye-shirye Hanyar

A shekarar 1960, K. A. Hoar ɓullo da wani Hanyar ga m kasawa na bayanai, ya zama mafi shahara. Yau an yadu amfani da shirye-shirye, kamar yadda yana da yawa tabbatacce Properties: shi za a iya amfani da janar lokuta, shi bukatar wani kananan karuwa a cikin ƙarin memory, jituwa tare da daban-daban na lists da kuma sauki yi. Amma akwai drawbacks, wanda yana da Quicksort: ta yin amfani da aikin yarda da yawa kuskure, kuma shi ne da ɗan m.

Duk da haka, shi ne mafi karatu version. Bayan na farko biyan bashin Hoare, da yawa yi ta m binciken. manyan tushe da aka kafa a kan msar tambayar tambayoyi na gano lokacin da ciyar a kan aikin, wanda aka underpinned da empirical shaida. Akwai hakikanin shawarwari don inganta asali algorithm kuma Ya ƙãra gudun.

Quicksort ne sosai na kowa, shi za a iya samu a ko'ina. A ta da asali da hanyar da aka aiwatar da TList.Sort, ba a duk versions (sai dai 1) Delphi, da library aiki na lokaci shi ya dauki don kammala, qsort a C ++.

Babbar ka'idar aiki za a iya tsara a matsayin "rabawa da nasara". Yana auku keta jerin cikin kungiyoyin biyu da kuma ana ana jerawa ga kowane bangare da kanta. Yana bi da cewa mafi hankali ya kamata a biya su rabuwa tsari, a lokacin da wadannan na faruwa: ne m da wani tushe kashi da ya gwada da rearranged da dukan jerin. Gina zuwa hagu na wani rukuni na 'yan takara, da darajar da yake kasa da duk sauran canja dokoki. Sai dai itace cewa babban kashi a cikin jerawa jerin ne a cikin rightful wuri. A na gaba mataki - wani kalubale recursive kasawa ayyuka ga bangarorin biyu na abubuwa dangi da tushe. Ya ƙare aiwatar aiki ne kawai idan jerin ƙunshi daya kawai kashi, cewa shi ne za a ana jerawa. Saboda haka, domin Master wani shirye-shirye da aiki a matsayin mai sauri raba, shi wajibi ne su san aikin ƙananan-matakin lissafi mai tsauri: a) da zabi na da tushe memba. b) a jerin mafi tasiri permutation don samar biyu sets da karami da ya fi girma dabi'u.

Familiarize da farko ka'idojin. A lokacin da zabar tushe memba, ya kamata fi dacewa a zabi daga jerin talakawan. Sa'an nan a lokacin hutu ne zuwa kashi biyu daidai halves. Just lissafi da talakawan darajar a cikin jerin ne da wuya sosai, saboda haka ko da ya fi sauri kasawa bypasses wannan ilimin lissafi gefe. Amma ya zabi na asali kashi tare da matsakaicin ko m darajar - kuma ba da mafi kyaun zaɓi. A hali irin wannan da dalilin da daya halitta komai lists za a tabbace, da kuma na biyu da cikakken. Saboda haka Tsayawa akan matsayin cewa matsayin tushe memba ya kamata a zaba daya, da yake kusa da talakawan, amma a kan iyakar da m.

Da zarar wani zabi ne m, za ka iya ci gaba da bazuwar algorithm. Wannan ake kira ciki madaukai sauri warware. Duk abin da aka gina a kan biyu Rapid Access fihirisa: na farko tafi a kan abubuwa daga hagu zuwa dama, na biyu, a maimakon haka, daga dama zuwa hagu. Fara aiki kisa dama: da index ne a cikin jerin kuma kwatanta duk dabi'u ga babban. A sake zagayowar ne cikakken lokacin da rabi ne kasa da ko ta daidaita da baseline. Wannan shi ne, akwai wani kwatanta da rage-rage darajar da index. A kan hagu a lokacin da aikin da aka gama fi ko daidai darajar. A nan, da kwatanta darajar ƙaruwa.

A wannan mataki na partitioning algorithm wanda qunshi quicksort, biyu yanayi na iya tashi. Na farko shi ne cewa index a kan hagu ne kasa da dama. Wannan ya nuna wani kuskure, to, akwai abubuwa a kan abin da aka bayyana a cikin jerin ne a daidai ba domin. Output - canza su wuraren. A halin da ake ciki na biyu shi ne a lokacin da biyu na shafi ne daidai, ko ya haye. Wannan ya nuna a nasarar rabuwa da jerin, wato, da aikin cika.