Հիմնական նյութ
Համակարգչային գիտություն
Դասընթաց․ (Համակարգչային գիտություն) > Բաժին 1
Դաս 9: Արագ տեսակավորումԳծային ժամանակով բաժանում
Արագ տեսակավորման իրական աշխատանքը կատարվում է բաժանման քայլին, երբ ենթազանգված
array[p..r]
-ը մասնատվում է հենակետի շուրջը։ Չնայած որ կարող ենք ընտրել ենթազանգվածի յուրաքանչյուր տարր՝ որպես հենակետ, հեշտ է կիրառել մասնատումը, եթե ընտրում ենք ենթազանգվածի ամենաաջ տարրը՝ A[r]
-ը, որպես հենակետ։Հենակետ ընտրելուց հետո ենթազանգվածը բաժանում ենք՝ դրա վրայով անցնելով և բոլոր տարրերը հենակետի հետ համեմատելով։ Ստանում ենք երկու ցուցիչ՝
q
և j
, որոնցով ենթազանգվածը բաժանում ենք չորս խմբի։ q
-ն օգտագործում ենք, որ ցուցիչն ի վերջո ցույց տա հենակետի վրա։ j
-ն օգտագործում ենք, քանի որ այն հաշվիչ փոփոխականի անուն է, և վերջացնելուց հետո այն կանտեսենք։array[p..q-1]
-ի տարրերը «L խումբն են», որոնք հենակետից փոքր կամ հավասար են։array[q..j-1]
-ի տարրերը «G խումբն են», որոնք հենակետից մեծ են։array[j..r-1]
-ի տարրերը «U խումբ են», որոնց հարաբերակցությունը հենակետի հետ անհայտ է, քանի որ դեռ չենք համեմատել։- Եվ վերջում
array[r]
-ը «P խումբն է»՝ հենակետը։
Սկզբում
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 տարրերով ենթազանգվածը մասնատելու ժամանակը \Theta, left parenthesis, n, right parenthesis է։ Յուրաքանչյուր տարրը՝
A[j]
-ը, համեմատում ենք հենակետի հետ։ A[j]
-ը կփոխարինվի կամ չի փոխարինվի A[q]
-ի հետ, q
-ն կմեծանա կամ չի մեծանա 1-ով, իսկ j
-ը միշտ մեծանում է 1-ով։ Ենթազանգվածում աշխատող տողերի քանակը, ըստ տարրերի, հաստատուն թիվ է։ Քանի որ ենթազանգվածն ունի n տարր, մասնատելու ժամանակը \Theta, left parenthesis, n, right parenthesis է՝ գծային ժամանակով մասնատում։Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։
Ուզո՞ւմ ես միանալ խոսակցությանը։
Առայժմ հրապարակումներ չկան։