Quicksort որպես ծրագրավորման մեթոդով

1960 թ.-ին, Կ. Ա. Hoar մշակել է մեթոդ արագ տեսակավորման տեղեկատվության, դարձավ առավել հայտնի: Այսօր այն լայնորեն օգտագործվում է ծրագրավորման, քանի որ այն ունի շատ դրական հատկությունների. Այն կարող է օգտագործվել ընդհանուր դեպքերի, դա պահանջում է մի փոքր աճ է լրացուցիչ հիշողության, համատեղելի է տարբեր տեսակի ցուցակների եւ հեշտ է իրականացնել. Բայց կան թերություններ, որն ունի Quicksort: օգտագործելով աշխատանքներ թույլատրվում է շատ սխալներ, եւ դա ինչ-որ չափով անկայուն:

Սակայն, դա առավել ուսումնասիրվել տարբերակը: Հետո առաջին վճարման Hoare, շատերը դրա խիտ ուսումնասիրությունը: մեծ բազան ստեղծվել է տեսական հարցերին գտնելու ժամանակը ծախսել է աշխատանքից, որը ամրապնդվում է էմպիրիկ ապացույցներ: Կային իրական առաջարկներ է բարելավել հիմնական ալգորիթմը եւ ավելացել արագությունը.

Quicksort շատ տարածված է, այն կարելի է գտնել ամենուր: Դրա հիման վրա մեթոդը իրականացվում TList.Sort, առկա է բոլոր տարբերակները (բացառությամբ 1) Delphi, գրադարանային ժամանակի ֆունկցիա, այն տեղի է լրացնել, qsort է C ++.

Հիմնական սկզբունքը գործում կարելի է ձեւակերպել որպես «բաժանիր, որ տիրես». Այն տեղի է ունենում խախտելու ցուցակը են երկու խմբի եւ տեսակավորվում են յուրաքանչյուր մասի ինքնին. Սրանից հետեւում է, որ ավելի մեծ ուշադրություն պետք է դարձվի բաժանման գործընթացին, որի ընթացքում հետեւյալ տեղի է ունենում: որոշվում է բազային տարր եւ համեմատաբար փոխեց իր ամբողջ ցուցակը. Կառուցվել է ձախ մի խումբ թեկնածուների, որի արժեքը պակաս է, քան մյուս բոլոր տրանսֆերտային կանոնների: Ստացվում է, որ հիմնական տարր է դասավորված ցանկում է իր օրինական տեղը. Հաջորդ փուլը - մի մարտահրավեր ռեկուրսիվ տեսակավորման գործառույթները երկու կողմերում տարրերի հարաբերական է բազայի. Այն ավարտվում է գործընթացը աշխատում է միայն այն դեպքում, եթե ցուցակը պարունակում է միայն մեկ տարր, որը պետք է տեսակավորված: Այսպիսով, որպեսզի յուրացնի ծրագրավորման գործառույթը, որպես արագ տեսակ, դա անհրաժեշտ է իմանալ, թե աշխատանքը ցածր մակարդակի ալգորիթմների `ա) ընտրությունը բազային անդամի բ) ցանկը առավել արդյունավետ վերադասավորումից արտադրել երկու սարքեր փոքր եւ ավելի մեծ արժեքների:

Ծանոթանալ առաջին սկզբունքներին. Երբ ընտրելով բազային անդամ, պետք է իդեալապես ընտրված ցանկից միջին. Ապա ընդմիջման բաժանվում է երկու հավասար մասի: Պարզապես հաշվարկել միջին արժեքը է ցուցակում շատ դժվար է, այնպես որ, նույնիսկ ամենաարագ տեսակավորման շրջանցի այս քար կողմը: Բայց ընտրությունը բազային տարրի հետ առավելագույն կամ նվազագույն արժեքին - նաեւ, որ լավագույն տարբերակն է: Դեպքում նման որոշումը մեկի ստեղծում դատարկ ցուցակները երաշխավորված կլինի, իսկ երկրորդը լրիվ. Այստեղից հետեւություն, որ, որպես բազային անդամ պետք է ընտրվեն, որը ավելի մոտ է միջինին, բայց առավելագույն եւ նվազագույնի.

Մի անգամ մի ընտրություն որոշվում է, որ դուք կարող եք անցնել տարրալուծման ալգորիթմի. Սա, այսպես կոչված, ներքին loops արագ տեսակ: Ամեն ինչ կառուցված է երկու արագ օգտվելու ցուցանիշների: նախ գնում են տարրերի ձախից աջ, երկրորդ, ընդհակառակը, աջից ձախ: Սկսվում գործողությունը կատարման իրավունք: այդ ցուցանիշը գտնվում է ցուցակում եւ համեմատում է բոլոր արժեքները հիմնական: Ցիկլը ավարտված է, երբ տարր որ պակաս է կամ հավասար է բազային: Այսինքն, կա մի համեմատություն եւ նվազեցնում արժեքը ցուցանիշից: Վրա ձախ ձեռքը, երբ աշխատանքը ավարտված է ավելի, քան կամ հավասար արժեք: Այստեղ է, որ համեմատությունը արժեքը ավելանում է:

Այս փուլում Պատնեշների ալգորիթմի, որը ներառում է quicksort, երկու իրավիճակները կարող են առաջանալ: Առաջինն այն է, որ այդ ցուցանիշը վրա ձախ պակաս է ճիշտ: Սա ցույց է տալիս մի սխալ, ապա կան տարրեր, որոնց վրա նշված է, որ ցանկում են սխալ հերթականությամբ: Արդյունք - փոխել են իրենց տեղերը: Երկրորդը վիճակն է, երբ երկուսն էլ սյունակում հավասար է կամ անցել. Սա ցույց է տալիս հաջող տարանջատումը ցուցակում, այսինքն, այդ աշխատանքը այժմ ավարտված է: