Արագ տեսակավորում. ակնարկ

Քանի որ տեսակավորելու համար օգտագործում ենք «Բաժանիր և տիրիր» ալգորիթմը, պետք է որոշենք, թե ինչպիսին պետք է լինեն մեր ենթախնդիրները։ Ամբողջական խնդիրը զանգվածը տեսակավորելն է։ Արի ասենք, որ ենթախնդիրը կլինի ենթազանգված տեսակավորելը։ Ընդհանուր առմամբ՝ ենթախնդիր է ենթազանգված տեսակավորելը, որը սկսում է $p$‍ ցուցչից մինչև $r$‍ ցուցիչը։ Լավ կլինի՝ ունենանք ենթազանգվածի նշագրում, հետևաբար արի ասենք, որ array[p..r]-ը ցույց է տալիս, որ սա array-ի ենթազանգվածն է։ Հաշվի առ, որ երկկետ նշագրումը լեգալ չէ JavaScript-ում․ մենք դա օգտագործում ենք, որ բառացի նկարագրենք ալգորիթմը, ոչ թե այդպես գրենք կոդի մեջ։ Իսկ ինչ վերաբերում է նշագրմանը, $n$‍ տարր ունեցող զանգվածի համար կարող ենք ասել, որ սկզբնական խնդիրն է տեսակավորել array[0..n-1]-ը։

Ահա, թե ինչպես է միացման տեսակավորումն օգտագործում «Բաժանիր և տիրիր» ալգորիթմը․

Մեզ պետք է առաջնային դեպք։ Առաջնային դեպքը ենթազանգված է, որն ունի երկուսից պակաս անդամ, այսինքն, երբ $p\ge r$‍, քանի որ անդամ չունեցող կամ մեկ անդամ ունեցող ենթազանգվածն արդեն տեսակավորված է։ Հետևաբար, մենք կբաժանենք-կտիրենք-կմիավորենք միայն, եթե $p<r$‍։

Արի դիտարկենք մի օրինակ։ Սկսենք array-ով, որտեղ [14, 7, 3, 12, 9, 11, 6, 2] թվերն են, հետևաբար դրա ենթազանգվածն իրականում ամբողջական զանգված է՝ array[0.,7] ($p=0$‍ և $r=7$‍)։ Այս ենթազանգվածն ունի առնվազն երկու տարր, հետևաբար այն առաջնային դեպքը չէ։

Ինչպե՞ս տեսակավորվեց array[0.,3]-ը։ Նույն կերպ։ Այն ունի երկուսից ավելի տարրեր, հետևաբար այն առաջնային դեպք չէ։ Ունենալով $p=0$‍ և $r=3$‍՝ գտնում ենք $q=1$‍, ռեկուրսիվորեն տեսակավորում array[0.,1] ([14, 7])-ը և array[2.,3] ([3, 12])-ը՝ ստանալով array[0.,3]՝ [7, 14, 3, 12], և առաջին ու երկրորդ հատվածներն իրար միավորելով ստանում [3, 7, 12, 14]։

Ինչպե՞ս տեսակավորվեց array[0.,1]-ը։ Ունենալով $p=0$‍ և $r=1$‍՝ գտնում ենք $q=0$‍, ռեկուրսիվորեն տեսակավորում array[0.,0] ([14])-ը և array[1.,1] ([7])-ը՝ ստանալով array[0.,1]՝ [14, 7], և առաջին ու երկրորդ հատվածներն իրար միավորելով ստանում [7, 14]։

array[0.,0] և array[1.,1] ենթազանգվածներն առաջնային դեպքեր են, քանի որ յուրաքանչյուրն ունի երկուսից պակաս տարր։ Ահա թե ինչպես է ամբողջ ալգորիթմն աշխատում․

Միացման տեսակավորման շատ քայլեր պարզ են։ Հեշտությամբ կարող ես ստուգել առաջնային դեպքը։ Բաժանման քայլի ժամանակ $q$‍-ն գտնելը նույնպես շատ հեշտ է։ Պետք է տիրելու քայլին կատարես ռեկուրենտ կանչեր։ Միացման քայլին պետք է միացնես երկու տեսակավորված ենթազանգված, որտեղ իսկական աշխատանքն է կատարվում։

Հաջորդ մարտահրավերում կկենտրոնանաս միացման տեսակավորում ալգորիթմն օգտագործելու վրա, որպեսզի ավելի լավ հասկանաս, թե ինչպես պետք է ռեկուրսիվորեն «Բաժանել և տիրել»։ Դա անելուց հետո մենք ավելի կխորանանք երկու տեսակավորված ենթազանգված արդյունավետ կերպով միավորելու վրա, և դու այն կօգտագործես հետագա մարտահրավերի մեջ։

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