Бириктирүү сорту 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 индекс2=0;
Келиңиз, бириктирүү процессин этап-этабы менен жазалы:
- arr1 массивинен индекс1 бар элементти, ал эми индекс2 бар элементти arr2 массивинен алыңыз.
- Салыштырыңыз, алардын ичинен эң кичинесин тандап, киргизиңизнатыйжасында массив.
- Кичирээк элементтин учурдагы индексин 1ге көбөйтүү.
- Биринчи кадамдан улант.
Биринчи орбитада абал мындай болот:
index1=0; индекс2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; натыйжа[0]=arr1[0]; // натыйжа=[2]
Экинчи бурулушта:
index1=1; индекс2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; натыйжа[1]=arr2[0]; // натыйжа=[2, 5]
Үчүнчү:
index1=1; индекс2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; натыйжа[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=new 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=new 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 start, long finish) { long split; эгерде(баштоо < бүтүрүү) { бөлүү=(баштоо + бүтүрүү)/2; mergeSort(а, баштоо, бөлүү); mergeSort(a, split+1, бүтүрүү); бириктирүү (а, баштоо, бөлүү, бүтүрүү); } }
Бул коддо эмне болот:
-
MergeSort функциясы
a
баштапкы массивди жана иргеле турган аймактын сол жана оң чектерин алат (индекстердин башталышы жана
- finish).
-
Эгер бул бөлүмдүн узундугу бирден көп болсо (
start < finish
), анда ал эки бөлүккө бөлүнөт (индекс боюнча
- split) жана ар бири рекурсивдүү иреттелет.
-
Сол тарапка рекурсивдүү функция чакыруусунда сюжеттин башталгыч индекси жана
split
өткөрүлөт. Тиешелүүлүгүнө жараша, башталышы
- (бөлүнүү + 1), ал эми аягы баштапкы бөлүмдүн акыркы индекси болот.
Функция
бириктир?? +1]…a[finish]
- ) жана аларды сорттоо иретинде бириктирет.
Бириктирүү функциясынын механикасы жогоруда талкууланган.
Алгоритмдин жалпы схемасы
Бириктирүү иреттөө массив ыкмасы эки чоң кадамдан турат:
- Сорттолбогон баштапкы массивди майда бөлүктөргө бөлүңүз.
- Иртиптөө эрежесин сактоо менен аларды жуптаңыз.
Чоң жана татаал тапшырма көптөгөн жөнөкөй тапшырмаларга бөлүнөт, алар ырааттуу түрдө чечилип, каалаган натыйжага алып келет.
Методду баалоо
Бириктирүү сортунун убакыт татаалдыгы бөлүнгөн дарактын бийиктиги менен аныкталаталгоритм жана массивдеги элементтердин санына (n) анын логарифмине (log n) барабар. Мындай баалоо логарифмдик деп аталат.
Бул ыкманын артыкчылыгы да, кемчилиги да. Анын иштөө убактысы эң начар учурда, баштапкы массив тескери тартипте иреттелгенде өзгөрбөйт. Бирок, толугу менен сорттолгон маалыматтарды иштеп чыгууда, алгоритм убакытты көбөйтпөйт.
Бириктирүү сорттоо ыкмасынын эстутум баасын да эске алуу маанилүү. Алар баштапкы коллекциянын өлчөмүнө барабар. Бул кошумча бөлүнгөн аймакта сорттолгон массив бөлүктөрдөн чогултулган.
Алгоритмдин ишке ашырылышы
Паскалда бириктирилген сорт төмөндө көрсөтүлгөн.
Procedure MergeSort(аты: сап; var f: text); Var a1, a2, s, i, j, kol, tmp: бүтүн; f1, f2: текст; б: логикалык Begincol:=0; Assign(f, name); баштапкы абалга келтирүү(f); EOF(f) болбосо да окууну баштаңыз(f, a1); inc(col); бүтүрүү; жабу(f); Assign(f1, '{1-көмөкчү файлдын аты}'); Assign(f2, '{2-көмөкчү файлдын аты}'); s:=1; While (s<kol) do begin Reset(f); rewrite(f1); rewrite(f2); For i:=1 to kol div 2 do begin Read(f, a1); Write(f1, a1, ' '); бүтүрүү; If (kol div 2) mod s0 then begin tmp:=kol div 2; Tmp mod s0 баштаганда Оку (f, a1); Write(f1, a1, ' '); inc(tmp); бүтүрүү; бүтүрүү; EOF(f) болбосо да, Read(f, a2) баштаңыз; Write(f2, a2, ' '); бүтүрүү; жабу(f); close(f1); close(f2); кайра жазуу(f); reset(f1); reset(f2); Окуу(f1, a1); Окуу(f2, a2); Ал эми (EOF(f1) эмес) жана (EOF(f2) эмес) башталат i:=0; j:=0; b:=true; (b) жана (EOF(f1) эмес) жана (EOF(f2) эмес) башталса, анда (a1<a2) башталатWrite(f, a1, ' '); Окуу(f1, a1); inc(i); End else begin Write(f, a2, ' '); Окуу(f2, a2); inc(j); бүтүрүү; Эгерде (i=s) же (j=s) анда b:=false; бүтүрүү; Эгерде b болбосо, анда begin While (i<s) жана (EOF(f1) эмес) башталат Write(f, a1, ' '); Окуу(f1, a1); inc(i); бүтүрүү; Ал эми (j<s) жана (EOF(f2) эмес) Write(f, a2, ' '); Окуу(f2, a2); inc(j); бүтүрүү; бүтүрүү; бүтүрүү; EOF(f1) болбосо да tmp:=a1; Окуу(f1, a1); Эгерде EOF(f1) болбосо Write(f, tmp, ' ') else Write(f, tmp); бүтүрүү; EOF(f2) болбосо да tmp:=a2; Окуу(f2, a2); Эгерде EOF(f2) болбосо Write(f, tmp, ' ') else Write(f, tmp); бүтүрүү; жабу(f); close(f1); close(f2); s:=s2; бүтүрүү; Erase(f1); Erase(f2); Аягы;
Алгоритмдин иштеши визуалдуу түрдө мындай көрүнөт (жогорку – иретсиз ырааттуулук, ылдый – иреттүү).
Тышкы маалыматтарды сорттоо
Көп учурда компьютердин тышкы эс тутумунда жайгашкан кээ бир маалыматтарды сорттоо зарылчылыгы келип чыгат. Кээ бир учурларда, алар таасирдүү өлчөмдө жана аларга жетүүнү жеңилдетүү үчүн RAMга жайгаштыруу мүмкүн эмес. Мындай учурларда тышкы сорттоо ыкмалары колдонулат.
Сырткы медиага кирүү зарылдыгы процесстин натыйжалуулугун төмөндөтөт.
Жумуштун татаалдыгы - алгоритм бир убакта маалымат агымынын бир эле элементине кире алат. Жана бул учурда эң жакшы натыйжалардын бири эки файлдын элементтерин ырааттуу түрдө биринин артынан бири салыштыра турган бириктирүү сорттоо ыкмасы менен көрсөтүлөт.
Дайындарды окуутышкы булак, аларды иштетүү жана акыркы файлга жазуу иреттелген блоктордо (серияларда) ишке ашырылат. Тартиптүү катардын өлчөмү менен иштөө ыкмасы боюнча сорттоонун эки түрү бар: жөнөкөй жана табигый бириктирүү.
Жөнөкөй бириктирүү
Жөнөкөй бириктирүү менен сериянын узундугу бекитилет.
Ошентип, баштапкы сорттолбогон файлда бардык сериялар бир элементтен турат. Биринчи кадамдан кийин өлчөмү экиге чейин көбөйөт. Кийинки - 4, 8, 16 жана башкалар.
Ал мындай иштейт:
- Булак файлы (f) эки көмөкчү файлга бөлүнгөн - f1, f2.
- Алар кайрадан бир файлга (f) бириктирилет, бирок ошол эле учурда бардык элементтер жуп болуп салыштырылат жана жуптарды түзөт. Бул кадамдагы сериянын өлчөмү экиге айланат.
- 1-кадам кайталанат.
- 2-кадам кайталанат, бирок мурунтан эле буйрутмаланган 2лер иреттелген 4с үчүн бириктирилген.
- Бүткүл файл иреттелгенге чейин цикл уланып, ар бир итерацияда катар көбөйөт.
Жөнөкөй бириктирүү менен сырткы сорттоо аяктаганын кайдан билесиз?
- жаңы сериянын узундугу (бириккенден кийин) элементтердин жалпы санынан кем эмес;
- бир гана эпизод калды;
- Жардамчы файл f2 бош калды.
Жөнөкөй бириктирүүнүн кемчиликтери төмөнкүлөр: иштетүү узундугу ар бир бириктирүү өтүүсүндө белгиленгендиктен, жарым-жартылай иреттелген дайындарды иштетүүгө толук кокустук маалыматтардай эле көп убакыт талап кылынат.
Табигый синтез
Бул ыкма узундукка чек койбойтсериясы, бирок максималдуу мүмкүн болгонду тандайт.
Сорттоо алгоритми:
- f файлынан баштапкы ырааттуулукту окуу. Биринчи кабыл алынган элемент f1 файлына жазылган.
- Эгер кийинки жазуу сорттоо шартын канааттандырса, анда ал ошол жерде, эгер жок болсо, анда f2 экинчи көмөкчү файлына жазылат.
- Ушундай жол менен баштапкы файлдын бардык жазуулары бөлүштүрүлөт жана f1де катардын учурдагы өлчөмүн аныктаган иреттелген ырааттуулук түзүлөт.
- f1 жана f2 файлдары бириктирилди.
- Цикл кайталанат.
Сериянын өлчөмү аныкталбагандыктан, катардын соңун атайын белги менен белгилөө зарыл. Ошондуктан бириккенде салыштыруулардын саны көбөйөт. Кошумчалай кетсек, көмөкчү файлдардын биринин өлчөмү түпнускага жакын болушу мүмкүн.
Орточо алганда, табигый бириктирүү тышкы сорт менен жөнөкөй бириктирүүгө караганда натыйжалуураак.
Алгоритмдин өзгөчөлүктөрү
Эки бирдей маанини салыштырганда, метод алардын баштапкы тартибин сактайт, башкача айтканда, туруктуу.
Сорттоо процессин ийгиликтүү бир нече жиптерге бөлсө болот.
Видео бириктирүү сорттоо алгоритминин иштешин даана көрсөтүп турат.
