Հիմնական նյութ
Դասընթաց․ (Համակարգչային գիտություն) > Բաժին 1
Դաս 9: Արագ տեսակավորումԱրագ տեսակավորում. ակնարկ
Ինչպես միացման տեսակավորումը, արագ տեսակավորումը նույնպես օգտագործում է «Բաժանիր և տիրիր» ալգորիթմը, հետևաբար այն ռեկուրենտ ալգորիթմ է։ Արագ տեսակավորումը «Բաժանիր և տիրիր» օգտագործում է միացման տեսակավորումից մի փոքր տարբեր ձևով։ Միացման տեսակավորման ժամանակ բաժանելու քայլը համարյա ոչինչ չի անում, և իրական գործը կատարվում է միացման ժամանակ։ Արագ տեսակավորումը հակառակն է․ ամբողջ իրական գործը կատարվում է բաժանելու ժամանակ։ Եվ իրականում արագ տեսակավորման միավորելու քայլն ընդհանրապես ոչինչ չի անում։
Արագ տեսակավորումն ունի միացման տեսակավորման հետ ևս մի քանի տարբերություններ։ Արագ տեսակավորումն աշխատում է տեղում։ Դրա աշխատելու ժամանակի վատագույն դեպքն այնքան է, որքան ընտրական տեսակավորմանն ու ներդրման տեսակավորմանը՝
Ահա, թե ինչպես է արագ տեսակավորումն օգտագործում «Բաժանիր և տիրիր»։ Ինչպես միացման տեսակավորման մեջ, վերցրու
array[p..r] ենթազանգվածն ու փորձիր տեսակավորել այն, երբ սկզբում ենթազանգվածը array[0..n-1] է։- Բաժանիր՝ ընտրելով
array[p..r]ենթազանգվածի կամայական տարր։ Դա կլինի հենակետը։ Տարրերըarray[p..r]-ում դասավորիր այնպես, որarray[p..r]-ում հենակետին փոքր կամ հավասար բոլոր տարրերը դրանից ձախ են, իսկ բոլոր մեծերը՝ դրանից աջ։ Այս գործողությունը կոչվում է բաժանում։ Այս դեպքում կարևոր չէ ուշադիր լինել, թե ինչ դասավորվածություն կունենան հենակետից ձախ կամ աջ գտնվող տարրերը։ Մենք միայն պետք է ուշադիր լինենք, որ տարրը լինի հենակետի ճիշտ կողմում՝ ձախ, եթե փոքր կամ հավասար է, և աջ, եթե մեծ է։Օրինակներում միշտ կընտրենքarray[r]ենթազանգվածի ամենաաջ տարրը որպես հենակետ։ Հետևաբար, եթե վերցնենք [9, 7, 5, 11, 12, 2, 14, 3, 10, 6] ենթազանգվածը, ապա 6-ը կլինի մեր հենակետը։ Բաժանումից հետո մեր ենթազանգվածն այսպիսի տեսքի կլինի՝ [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]։ Արիq-ով նշանակենք այն ցուցիչը, որը կլինի հենակետի վերջնական ցուցիչը։ - Տիրիր՝ ռեկուրսիվորեն տեսակավորելով
array[p..q-1](հենակետից ձախ բոլոր տարրերը, այսինքն՝ հենակետից փոքր կամ հավասարները) ևarray[q+1..r](հենակետից աջ բոլոր տարրերը, այսինքն՝ հենակետից մեծերը) ենթազանգվածները։ - Միավորիր․ ոչինչ մի արա։ Երբ վերջացնում ենք «տիրիր» քայլով ռեկուրսիվորեն տեսակավորելը, մեր գործն ավարտված է։ Ինչո՞ւ։
array[p..q-1]-ում հենակետից ձախ բոլոր տարրերն են, որոնք փոքր կամ հավասար են հենակետին և տեսակավորված են։ Իսկarray[q+1..r]-ում հենակետից ձախ բոլոր տարրերն են, որոնք մեծ են հենակետից և տեսակավորված են։ Հետևաբար,array[p..r]-ում բոլոր տարրերն արդեն տեսակավորված են։Վերցնենք մեր օրինակը։ Ենթազանգվածները հենակետից ձախ ու աջ կողմերում ռեկուրսիվորեն տեսակավորելուց հետո հենակետից ձախ ենթազանգվածը դառնում է [2, 3, 5], իսկ հենակետից աջ ենթազանգվածը դառնում է [7, 9, 10, 11, 12, 14]։ Հետևաբար, ենթազանգվածն ունի [2, 3, 5], հետո՝ 6, հետո՝ [7, 9, 10, 11, 12, 14]։ Ենթազանգվածը տեսակավորված է։
Առաջնային դեպքերը երկուսից պակաս տարր ունեցող ենթազանգվածներն են, միացման տեսակավորման պես։ Միացման տեսակավորման մեջ չես տեսնի տարր չունեցող ենթազանգված, բայց արագ տեսակավորման մեջ կարող ես, եթե ենթազանգվածի մյուս տարրերը բոլորը փոքր կամ մեծ են հենակետից։
Արի վերադառնանք «տիրիր» քայլին և անցնենք ենթազանգվածները ռեկուրսիվորեն տեսակավորելու վրայով։ Առաջին բաժանումից հետո ունենք [5, 2, 3] և [12, 7, 14, 9, 10, 11], իսկ 6-ը հենակետն է։
[5, 2, 3] ենթազանգվածը տեսակավորելու համար 3-ն ընտրում ենք որպես հենակետ։ Բաժանումից հետո ունենք [2, 3, 5]։ [2] ենթազանգվածը, որը հենակետից ձախ է, առաջնային դեպք է, հենակետից աջ գտնվող [5]-ը՝ նույնպես։
[12, 7, 14, 9, 10, 11] ենթազանգվածը տեսակավորելու համար 11-ն ընտրում ենք որպես հենակետ՝ ստանալով հենակետից ձախ [7, 9, 10] ենթազանգվածը և հենակետից աջ՝ [14, 12] ենթազանգվածը։ Այս զանգվածները տեսակավորելուց հետո ունենք [7, 9, 10], հետո՝ 11, հետո՝ [12, 14]։
Ահա ամբողջ արագ տեսակավորում ալգորիթմի գաղափարը։ Կապույտով նշվածները նախորդ ռեկուրենտ կանչերի հենակետերն են, հետևաբար այս դիրքերի արժեքները չեն դիտարկվում կամ տեղափոխվում․
Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։
Ուզո՞ւմ ես միանալ խոսակցությանը։
Առայժմ հրապարակումներ չկան։