Գծային ժամանակով բաժանում

Արագ տեսակավորման իրական աշխատանքը կատարվում է բաժանման քայլին, երբ ենթազանգված array[p..r]-ը մասնատվում է հենակետի շուրջը։ Չնայած որ կարող ենք ընտրել ենթազանգվածի յուրաքանչյուր տարր՝ որպես հենակետ, հեշտ է կիրառել մասնատումը, եթե ընտրում ենք ենթազանգվածի ամենաաջ տարրը՝ A[r]-ը, որպես հենակետ։

Հենակետ ընտրելուց հետո ենթազանգվածը բաժանում ենք՝ դրա վրայով անցնելով և բոլոր տարրերը հենակետի հետ համեմատելով։ Ստանում ենք երկու ցուցիչ՝ q և j, որոնցով ենթազանգվածը բաժանում ենք չորս խմբի։ q-ն օգտագործում ենք, որ ցուցիչն ի վերջո ցույց տա հենակետի վրա։ j-ն օգտագործում ենք, քանի որ այն հաշվիչ փոփոխականի անուն է, և վերջացնելուց հետո այն կանտեսենք։

Սկզբում q-ն ու j-ն հավասար են p-ին։ Յուրաքանչյուր քայլին համեմատում ենք A[j]-ն՝ U խմբի ամենաձախ անդամը, հենակետի հետ։ Եթե A[j]-ն մեծ է հենակետից, j-ն մեծացնում ենք 1-ով այնպես, որ G և U խմբերի միջև գիծը մեկով գա դեպի աջ․

Եթե A[j]-ը փոքր է կամ հավասար հենակետին, A[j]-ը A[q]-ի հետ տեղերով փոխում ենք (G խմբի ամենաձախ տարրը), j-ը մեծացնում 1-ով, q-ն մեծացնում 1-ով այնպես, որ L և G խմբերի միջև ու G և U խմբերի միջև գծերը մեկով գան դեպի աջ․

Երբ հասնում ենք հենակետին, U խումբը դառնում է դատարկ։ Հենակետը G խմբի ամենաձախ տարրի հետ տեղերով փոխում ենք՝ A[r]-ն A[q]-ի հետ։ Այս փոխարինումը հենակետը դնում է L ու G խմբերի միջև, և դա ճիշտ կաշխատի, եթե նույնիսկ L կամ G խումբը դատարկ լինի (Եթե L խումբն է դատարկ, ապա q-ն երբեք իր սկզբնական p արժեքից չի մեծացել, հետևաբար հենակետը տեղափոխվում է դեպի ենթազանգվածի ամենաձախ հատված։ Եթե G խումբն է դատարկ, ապա q-ն ամեն անգամ մեծացել էր 1-ով այնպես, ինչպես j-ն, և հետևաբար երբ j-ն հասավ հենակետի r ցուցիչ, q-ն նույնպես հավասար կդառնա r-ին, ու հենակետը կմնա այնտեղ, որտեղ մինչ այդ էր՝ ամենաաջ մասում)։ partition ֆունկցիան, որը կատարում է այս գործողությունները, վերադարձնում է q, որը ցույց է տալիս հենակետի դիրքը, որպեսզի quicksort ֆունկցիան, որ կանչում է դա, իմանա, թե որտեղ են մասնատումները։ Ահա [12, 7, 14, 9, 10, 11] ենթազանգվածը մասնատելու քայլերը array[4.,9]-ում․

$n$n տարրերով ենթազանգվածը մասնատելու ժամանակը $\Theta(n)$\Theta, left parenthesis, n, right parenthesis է։ Յուրաքանչյուր տարրը՝ A[j]-ը, համեմատում ենք հենակետի հետ։ A[j]-ը կփոխարինվի կամ չի փոխարինվի A[q]-ի հետ, q-ն կմեծանա կամ չի մեծանա 1-ով, իսկ j-ը միշտ մեծանում է 1-ով։ Ենթազանգվածում աշխատող տողերի քանակը, ըստ տարրերի, հաստատուն թիվ է։ Քանի որ ենթազանգվածն ունի $n$n տարր, մասնատելու ժամանակը $\Theta(n)$\Theta, left parenthesis, n, right parenthesis է՝ գծային ժամանակով մասնատում։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։