Merge sort-ը համակարգչային գիտության հիմնական ալգորիթմներից մեկն է, որը ձևակերպվել է դեռևս 1945 թվականին մեծ մաթեմատիկոս Ջոն ֆոն Նեյմանի կողմից: Մանհեթենի նախագծին մասնակցելիս Նեյմանը բախվեց հսկայական քանակությամբ տվյալների արդյունավետ մշակման անհրաժեշտության հետ: Նրա մշակած մեթոդը օգտագործում էր «բաժանիր և նվաճիր» սկզբունքը, որը զգալիորեն նվազեցրեց աշխատանքի համար պահանջվող ժամանակը։
Ալգորիթմի սկզբունքը և օգտագործումը
Միաձուլման տեսակավորման մեթոդն օգտագործվում է այնպիսի կառուցվածքների տեսակավորման խնդիրներում, որոնք պատվիրված են մուտք դեպի տարրեր, ինչպիսիք են զանգվածները, ցուցակները, հոսքերը:
Մշակման ընթացքում նախնական տվյալների բլոկը բաժանվում է փոքր բաղադրիչների, մինչև մեկ տարր, որն իրականում արդեն տեսակավորված ցուցակ է։ Այնուհետև այն նորից հավաքվում է ճիշտ հերթականությամբ։
Որոշակի երկարությամբ զանգվածի տեսակավորումը պահանջում է նույն չափի լրացուցիչ հիշողության տարածք, որում տեսակավորված զանգվածը հավաքվում է մասերով:
Մեթոդը կարող է օգտագործվել ցանկացած համադրելի տվյալների տեսակ պատվիրելու համար, ինչպիսիք են թվերը կամ տողերը:
Միաձուլումը տեսակավորված էհողամասեր
Ալգորիթմը հասկանալու համար դրա վերլուծությունը սկսենք վերջից՝ տեսակավորված բլոկների միաձուլման մեխանիզմից։
Եկեք պատկերացնենք, որ մենք ունենք թվերի երկու զանգված, որոնք տեսակավորված են ցանկացած ձևով, որոնք պետք է համակցվեն միմյանց հետ, որպեսզի տեսակավորումը չխախտվի: Պարզության համար մենք թվերը կդասավորենք աճման կարգով։
Տարրական օրինակ. երկու զանգվածները բաղկացած են մեկ տարրից:
int arr1={31}; int arr2={18};
Դրանք միավորելու համար անհրաժեշտ է վերցնել առաջին զանգվածի զրոյական տարրը (մի մոռացեք, որ համարակալումը սկսվում է զրոյից) և երկրորդ զանգվածի զրոյական տարրը։ Դրանք, համապատասխանաբար, 31-ն են և 18-ը։ Ըստ տեսակավորման պայմանի՝ առաջինը պետք է լինի 18 թիվը, քանի որ այն ավելի քիչ է։ Պարզապես տեղադրեք թվերը ճիշտ հերթականությամբ՝
int արդյունք={18, 31};
Դիտարկենք ավելի բարդ օրինակ, որտեղ յուրաքանչյուր զանգված բաղկացած է մի քանի տարրերից.
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Միաձուլման ալգորիթմը բաղկացած է լինելու փոքր տարրերի հաջորդական համեմատությունից և դրանք ստացված զանգվածում ճիշտ հերթականությամբ տեղադրելուց: Ընթացիկ ցուցանիշներին հետևելու համար ներկայացնենք երկու փոփոխական՝ index1 և index2: Սկզբում մենք դրանք սահմանեցինք զրոյի, քանի որ զանգվածները դասավորված են, իսկ ամենափոքր տարրերը սկզբում են:
int index1=0; int index2=0;
Եկեք գրենք ամբողջ միաձուլման գործընթացը քայլ առ քայլ:
- Վերցրեք index1-ով տարրը arr1 զանգվածից, իսկ index2-ով տարրը arr2 զանգվածից:
- Համեմատե՛ք, ընտրե՛ք դրանցից ամենափոքրը և դրե՛քստացված զանգված։
- Ավելացրե՛ք փոքր տարրի ընթացիկ ինդեքսը 1-ով։
- Շարունակեք առաջին քայլից։
Առաջին ուղեծրում իրավիճակն այսպիսի տեսք կունենա՝
index1=0; ինդեքս 2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; ինդեքս 1++; արդյունք[0]=arr1[0]; // արդյունք=[2]
Երկրորդ շրջադարձում՝
index1=1; ինդեքս 2=0; arr1 [1]=17; arr2[0]=5; arr1 [1] > arr2 [0]; ինդեքս 2++; արդյունք[1]=arr2[0]; // արդյունք=[2, 5]
Երրորդ:
index1=1; ինդեքս 2=1; arr1 [1]=17; arr2 [1]=6; arr1 [1] > arr2 [1]; ինդեքս 2++; արդյունք[2]=arr2 [1]; // արդյունք=[2, 5, 6]
Եվ այսպես շարունակ, մինչև արդյունքը լինի ամբողջովին դասավորված զանգված՝ {2, 5, 6, 17, 21, 19, 30, 45}։
Որոշակի դժվարություններ կարող են առաջանալ, եթե տարբեր երկարություններ ունեցող զանգվածները միաձուլվեն: Իսկ եթե ընթացիկ ինդեքսներից մեկը հասել է վերջին տարրին, և դեռ անդամներ են մնացել երկրորդ զանգվածում:
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 քայլ ինդեքս1=0, ինդեքս2=0; 1 2 արդյունք={1, 2}; // 3 քայլ ինդեքս1=1, ինդեքս2=1; 4 < 5 արդյունք={1, 2, 4}; //4 քայլ ինդեքս 1=2, ինդեքս 2=1 ??
Index1 փոփոխականը հասել է 2-ի արժեքին, սակայն arr1 զանգվածն այդ ինդեքսով տարր չունի: Այստեղ ամեն ինչ պարզ է. պարզապես երկրորդ զանգվածի մնացած տարրերը փոխանցեք ստացվածին` պահպանելով դրանց հերթականությունը:
արդյունք={1, 2, 4, 5, 6, 7, 9};
Այս իրավիճակը ցույց է տալիս մեզ անհրաժեշտությունըհամապատասխանեցնել ընթացիկ ստուգման ինդեքսը միավորվող զանգվածի երկարությամբ:
Միաձուլման սխեման տարբեր երկարությունների պատվիրված հաջորդականությունների (A և B) համար.
- Եթե երկու հաջորդականությունների երկարությունը 0-ից մեծ է, համեմատեք A[0] և B[0] և տեղափոխեք փոքրը դեպի բուֆեր:
- Եթե հաջորդականություններից մեկի երկարությունը 0 է, վերցրեք երկրորդ հաջորդականության մնացած տարրերը և առանց դրանց հերթականությունը փոխելու տեղափոխեք բուֆերի վերջ։
Երկրորդ փուլի իրականացում
Java-ում երկու տեսակավորված զանգվածների միացման օրինակ տրված է ստորև:
int a1=նոր int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=նոր int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=նոր int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.length-1) {int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) {int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }
Այստեղ՝
- a1 և a2 սկզբնական տեսակավորված զանգվածներն են, որոնք պետք է միավորվեն;
- a3 – վերջնական զանգված;
- i և j-ն ընթացիկ տարրերի ինդեքսներն են a1 և a2 զանգվածների համար:
Առաջին և երկրորդ, եթե պայմաններն ապահովում են, որ ինդեքսները զանգվածի չափից այն կողմ չեն անցնում: Երրորդ և չորրորդ պայմանի բլոկները, համապատասխանաբար, տեղափոխվում են ավելի փոքր տարրի ստացված զանգված:
Բաժանիր և տիրիր
Այսպիսով, մենք սովորել ենք միավորել տեսակավորվածըարժեքների հավաքածուներ. Կարելի է ասել, որ միաձուլման տեսակավորման ալգորիթմի երկրորդ մասը՝ ինքնին միաձուլումը, արդեն տեսակավորված է։
Այնուամենայնիվ, դուք դեռ պետք է հասկանաք, թե ինչպես կարելի է սկզբնական չտեսակավորված թվերի զանգվածից հասնել մի քանի տեսակավորվածների, որոնք կարող են միավորվել:
Եկեք դիտարկենք ալգորիթմի առաջին փուլը և սովորենք, թե ինչպես առանձնացնել զանգվածները:
Սա դժվար չէ. արժեքների սկզբնական ցանկը բաժանված է կիսով չափ, այնուհետև յուրաքանչյուր մասը նույնպես երկփեղկված է, և այսպես շարունակ, մինչև ստացվեն շատ փոքր բլոկներ:
Նման նվազագույն տարրերի երկարությունը կարող է հավասար լինել մեկի, այսինքն՝ իրենք կարող են լինել տեսակավորված զանգված, բայց դա անհրաժեշտ պայման չէ։ Բլոկի չափը որոշվում է նախօրոք, և ցանկացած հարմար տեսակավորման ալգորիթմ, որն արդյունավետորեն աշխատում է փոքր չափերի զանգվածների հետ (օրինակ՝ արագ տեսակավորում կամ ներդիր տեսակավորում), կարող է օգտագործվել այն պատվիրելու համար։
Այնպիսի տեսք ունի.
// բնօրինակ զանգված {34, 95, 10, 2, 102, 70}; // առաջին բաժանումը {34, 95, 10} և {2, 102, 70}; // երկրորդ բաժանում {34} և {95, 10} և {2} և {102, 70}
Ստացված բլոկները՝ բաղկացած 1-2 տարրից, շատ հեշտ է դասավորվում։
Դրանից հետո անհրաժեշտ է զույգերով միաձուլել արդեն տեսակավորված փոքր զանգվածները՝ պահպանելով անդամների հերթականությունը, ինչն արդեն սովորել ենք։
Առաջին փուլի իրականացում
Զանգվածի ռեկուրսիվ բաժանումը ներկայացված է ստորև:
void mergeSort(T a, երկար սկիզբ, երկար ավարտ) { long split; եթե(սկիզբ < ավարտ) { պառակտում=(սկիզբ + ավարտ)/2; mergeSort (a, start, split); mergeSort(a, split+1, finish); միաձուլում (ա, սկիզբ, պառակտում, ավարտ); } }
Ինչ է տեղի ունենում այս ծածկագրում.
-
mergeSort ֆունկցիան ստանում է նախնական զանգվածը
a
և տեսակավորվող տարածաշրջանի ձախ և աջ սահմանները (ինդեքսները սկսվում են և
- ավարտել).
-
Եթե այս հատվածի երկարությունը մեկից մեծ է (
սկիզբ < ավարտ
), ապա այն բաժանվում է երկու մասի (
- բաժանում ինդեքսով), և յուրաքանչյուրը դասավորված է ռեկուրսիվորեն։
-
Ձախ կողմի ռեկուրսիվ ֆունկցիայի կանչում տրված են սյուժեի մեկնարկային ինդեքսը և
split
ինդեքսը: Ճիշտի համար, համապատասխանաբար, սկիզբը կլինի
- (բաժանում + 1), իսկ վերջը կլինի սկզբնական բաժնի վերջին ցուցանիշը։
-
միաձուլում
ֆունկցիան ստանում է երկու դասավորված հաջորդականություն (
a[start]…a[split]
և
- a[բաժանում +1]…a[finish]) և միավորում է դրանք տեսակավորման կարգով:
Միաձուլման ֆունկցիայի մեխանիզմը քննարկված է վերևում:
Ալգորիթմի ընդհանուր սխեման
Միաձուլման տեսակավորման զանգվածի մեթոդը բաղկացած է երկու մեծ քայլերից.
- Բաժանեք չտեսակավորված բնօրինակ զանգվածը փոքր կտորների:
- Հավաքեք դրանք զույգերով՝ հետևելով տեսակավորման կանոնին։
Մեծ և բարդ առաջադրանքը բաժանվում է շատ պարզների, որոնք հաջորդաբար լուծվում են՝ տանելով ցանկալի արդյունքի։
Մեթոդի գնահատում
Միաձուլման տեսակավորման ժամանակային բարդությունը որոշվում է բաժանված ծառի բարձրությամբալգորիթմը և հավասար է զանգվածի տարրերի թվին (n) բազմապատկած նրա լոգարիթմի (log n): Նման գնահատականը կոչվում է լոգարիթմական։
Սա մեթոդի և՛ առավելությունն է, և՛ թերությունը: Դրա գործարկման ժամանակը չի փոխվում նույնիսկ ամենավատ դեպքում, երբ սկզբնական զանգվածը դասավորված է հակառակ հերթականությամբ: Այնուամենայնիվ, ամբողջությամբ տեսակավորված տվյալները մշակելիս ալգորիթմը ժամանակի շահույթ չի ապահովում։
Կարևոր է նաև նշել միաձուլման տեսակավորման մեթոդի հիշողության արժեքը: Դրանք հավասար են բնօրինակ հավաքածուի չափերին։ Այս լրացուցիչ հատկացված տարածքում, դասավորված զանգվածը հավաքվում է կտորներից:
Ալգորիթմի իրականացում
Պասկալի միաձուլման տեսակավորումը ներկայացված է ստորև:
Ընթացակարգ MergeSort (անունը` տող; var f: տեքստ); Var a1, a2, s, i, j, kol, tmp՝ ամբողջ թիվ; f1, f2՝ տեքստ; բ. բուլյան Սկիզբ:=0; Նշանակել (զ, անուն); զրոյացնել (զ); Մինչդեռ EOF(f)-ը չէ, սկսում է կարդալ (f, a1); inc(col); վերջ; փակել (զ); Assign(f1, '{1st օժանդակ ֆայլի անունը}'); Assign(f2, '{2-րդ օժանդակ ֆայլի անունը}'); s:=1; Մինչդեռ (s<kol) սկսում է Վերակայել(f); վերաշարադրել (f1); վերաշարադրել (f2); For i:=1-ից մինչև kol div 2 սկսեք Read(f, a1); Գրել (f1, a1, ' '); վերջ; Եթե (kol div 2) mod s0, ապա սկսեք tmp:=kol div 2; Մինչ tmp mod s0-ը սկսում է Read(f, a1); Գրել (f1, a1, ' '); inc (tmp); վերջ; վերջ; Մինչդեռ EOF(f)-ը չէ, սկսում է Read(f, a2); Գրել (f2, a2, ' '); վերջ; փակել (զ); փակել (f1); փակել (f2); վերաշարադրել (f); վերականգնել (f1); վերականգնել (f2); Կարդացեք (f1, a1); Read (f2, a2); Մինչդեռ (ոչ EOF(f1)) և (ոչ EOF(f2)) սկսում են i:=0; j:=0; բ:=ճշմարիտ; Մինչ (b) և (ոչ EOF(f1)) և (ոչ EOF(f2)) սկսվում են, եթե (a1<a2), ապա սկսեքԳրել (f, a1, ' '); Կարդացեք (f1, a1); inc(i); End else begin Write(f, a2, ' '); Read (f2, a2); inc(j); վերջ; Եթե (i=s) կամ (j=s) ապա b:=false; վերջ; Եթե ոչ b, ապա սկսեք while (i<s) և (ոչ EOF(f1)) սկսեք Write(f, a1, ' '); Կարդացեք (f1, a1); inc(i); վերջ; Մինչդեռ (j<s) և (ոչ EOF(f2)) սկսում են գրել (f, a2, ' '); Read (f2, a2); inc(j); վերջ; վերջ; վերջ; Մինչդեռ EOF(f1) չէ, սկսեք tmp:=a1; Կարդացեք (f1, a1); Եթե ոչ EOF(f1) ապա Write(f, tmp, ' ') else Write(f, tmp); վերջ; Մինչդեռ EOF(f2) չէ, սկսեք tmp:=a2; Read (f2, a2); Եթե ոչ EOF(f2) ապա Write(f, tmp, ' ') else Write(f, tmp); վերջ; փակել (զ); փակել (f1); փակել (f2); s:=s2; վերջ; Ջնջել (f1); Ջնջել (f2); Ավարտ;
Տեսողականորեն ալգորիթմի գործողությունն այսպիսի տեսք ունի (վերևում` չդասավորված հաջորդականություն, ներքևում` դասավորված):
Արտաքին տվյալների տեսակավորում
Շատ հաճախ անհրաժեշտություն է առաջանում տեսակավորել որոշ տվյալներ, որոնք տեղակայված են համակարգչի արտաքին հիշողության մեջ: Որոշ դեպքերում դրանք տպավորիչ չափի են և չեն կարող տեղադրվել RAM-ում՝ դրանց մուտքը հեշտացնելու համար: Նման դեպքերի համար օգտագործվում են արտաքին տեսակավորման մեթոդներ։
Արտաքին մեդիա մուտք գործելու անհրաժեշտությունը նվազեցնում է մշակման ժամանակի արդյունավետությունը:
Աշխատանքի բարդությունն այն է, որ ալգորիթմը կարող է միաժամանակ մուտք գործել տվյալների հոսքի միայն մեկ տարր: Եվ այս դեպքում լավագույն արդյունքներից մեկը ցուցադրվում է միաձուլման տեսակավորման մեթոդով, որը կարող է իրար հաջորդաբար համեմատել երկու ֆայլերի տարրերը։
Տվյալների ընթերցումարտաքին աղբյուրը, դրանց վերամշակումը և վերջնական ֆայլին գրելը կատարվում են պատվիրված բլոկներով (սերիաներով): Ըստ պատվիրված շարքերի չափերի հետ աշխատելու ձևի՝ կա տեսակավորման երկու տեսակ՝ պարզ և բնական միաձուլում։
Պարզ միաձուլում
Պարզ միաձուլմամբ շարքի երկարությունը ֆիքսված է։
Այսպիսով, բնօրինակ չտեսակավորված ֆայլում բոլոր շարքերը բաղկացած են մեկ տարրից: Առաջին քայլից հետո չափը մեծանում է երկուսի: Հաջորդը՝ 4, 8, 16 և այլն։
Այն աշխատում է այսպես.
- Աղբյուր ֆայլը (f) բաժանված է երկու օժանդակ ֆայլերի՝ f1, f2:
- Դրանք կրկին միաձուլվում են մեկ ֆայլի մեջ (f), բայց միևնույն ժամանակ բոլոր տարրերը համեմատվում են զույգերով և կազմում զույգեր։ Շարքի չափն այս քայլում դառնում է երկու։
- Քայլ 1 կրկնվում է։
- Քայլ 2-ը կրկնվում է, բայց արդեն պատվիրված 2-երը միաձուլվում են՝ ձևավորելով տեսակավորված 4-ներ:
- Օղակը շարունակվում է՝ ավելացնելով շարքը յուրաքանչյուր կրկնության վրա, մինչև որ ամբողջ ֆայլը տեսակավորվի:
Ինչպե՞ս գիտեք, որ արտաքին տեսակավորումը պարզ միաձուլմամբ ավարտված է:
- նոր շարքի երկարությունը (միաձուլումից հետո) տարրերի ընդհանուր քանակից ոչ պակաս;
- մնացել է ընդամենը մեկ դրվագ;
- Օժանդակ ֆայլ f2 մնացել է դատարկ:
Պարզ միաձուլման թերություններն են. քանի որ գործարկման երկարությունը ամրագրված է յուրաքանչյուր միաձուլման անցուղու վրա, մասնակի պատվիրված տվյալների մշակումը կպահանջվի այնքան ժամանակ, որքան բոլորովին պատահական տվյալները:
Բնական միաձուլում
Այս մեթոդը չի սահմանափակում երկարությունըշարքը, բայց ընտրում է հնարավոր առավելագույնը։
Տեսակավորման ալգորիթմ՝
- Ընթերցում է սկզբնական հաջորդականությունը f ֆայլից. Առաջին ստացված տարրը գրվում է f1 ֆայլում։
- Եթե հաջորդ գրառումը բավարարում է տեսակավորման պայմանը, ապա այն գրվում է այնտեղ, եթե ոչ, ապա երկրորդ օժանդակ ֆայլում f2:
- Այս կերպ բաշխվում են սկզբնաղբյուր ֆայլի բոլոր գրառումները, և f1-ում ձևավորվում է պատվիրված հաջորդականություն, որը որոշում է շարքի ընթացիկ չափը:
- F1 և f2 ֆայլերը միավորվել են:
- Ցիկլը կրկնվում է։
Շարքի ոչ ֆիքսված չափի պատճառով անհրաժեշտ է հաջորդականության վերջը նշել հատուկ գրանշանով։ Հետեւաբար, միաձուլման ժամանակ համեմատությունների թիվն ավելանում է։ Բացի այդ, օժանդակ ֆայլերից մեկի չափը կարող է մոտ լինել բնօրինակի չափին:
Միջինում բնական միաձուլումն ավելի արդյունավետ է, քան պարզ միաձուլումը արտաքին տեսակավորման հետ:
Ալգորիթմի առանձնահատկությունները
Երկու միանման արժեքներ համեմատելիս մեթոդը պահպանում է դրանց սկզբնական կարգը, այսինքն՝ այն կայուն է։
Տեսակավորման գործընթացը կարելի է շատ հաջողությամբ բաժանել բազմաթիվ թելերի:
Տեսանյութը հստակ ցույց է տալիս միաձուլման տեսակավորման ալգորիթմի աշխատանքը:
