If you're seeing this message, it means we're having trouble loading external resources on our website.

Եթե գտնվում ես վեբ զտիչի հետևում, խնդրում ենք համոզվել, որ *.kastatic.org և *.kasandbox.org տիրույթները հանված են արգելափակումից։

Հիմնական նյութ

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

Արագ տեսակավորման իրական աշխատանքը կատարվում է բաժանման քայլին, երբ ենթազանգված 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-ի կողմից։

Ուզո՞ւմ ես միանալ խոսակցությանը։

Առայժմ հրապարակումներ չկան։
Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում: