Біріктіру сұрыптауы 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 индекс1=0; int индекс2=0;
Біріктіру процесін кезең-кезеңмен жазайық:
- 1 arr1 массивінен 1 индексі бар элементті және arr2 массивінен индекс2 элементті алыңыз.
- Салыстырыңыз, олардың ең кішісін таңдап, салыңызнәтижелі массив.
- Кішірек элементтің ағымдағы индексін 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=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; үшін (int k=0; k a1.ұзындығы-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, бастау, бөлу); mergeSort(a, бөлу+1, аяқтау); біріктіру(а, бастау, бөлу, аяқтау); } }
Бұл кодта не болады:
-
MergeSort функциясы
a
бастапқы массивін және сұрыпталатын аймақтың сол және оң жақ шекараларын алады (индекстердің басталуы және
- finish).
-
Егер бұл бөлімнің ұзындығы біреуден көп болса (
start < finish
), онда ол екі бөлікке бөлінеді (индекс бойынша
- split) және әрқайсысы рекурсивті сұрыпталған.
-
Сол жаққа арналған рекурсивті функция шақыруында сызбаның бастапқы индексі және
split
индексі беріледі. Дұрысы үшін, тиісінше, басы
- (бөліну + 1) болады, ал соңы бастапқы бөлімнің соңғы индексі болады.
-
Функция
біріктіру
екі реттелген тізбекті алады (
a[бастау]…a[бөлу
және
- a[бөліну +1]…a[finish]) және оларды сұрыптау ретімен біріктіреді.
Біріктіру функциясының механикасы жоғарыда талқыланған.
Алгоритмнің жалпы схемасы
Біріктіру массивін сұрыптау әдісі екі үлкен қадамнан тұрады:
- Сұрыпталмаған бастапқы массивті кішкене бөліктерге бөліңіз.
- Сұрыптау ережесін сақтай отырып, оларды жұппен жинаңыз.
Үлкен және күрделі тапсырма көптеген қарапайым тапсырмаларға бөлінеді, олар дәйекті түрде шешіліп, қажетті нәтижеге әкеледі.
Әдісті бағалау
Біріктіру сұрыптауының уақыт күрделілігі бөлінген ағаштың биіктігімен анықталадыалгоритм және массивтегі элементтер санының (n) оның логарифмінің (log n) көбейтіндісіне тең. Мұндай бағалау логарифмдік деп аталады.
Бұл әдістің артықшылығы да, кемшілігі де. Оның жұмыс уақыты тіпті ең нашар жағдайда, бастапқы массив кері ретпен сұрыпталғанда өзгермейді. Дегенмен, толық сұрыпталған деректерді өңдеу кезінде алгоритм уақыт ұтымдылығын қамтамасыз етпейді.
Біріктіру сұрыптау әдісінің жады құнын да ескеру маңызды. Олар бастапқы жинақтың көлеміне тең. Бұл қосымша бөлінген аумақта сұрыпталған массив бөліктерден жиналады.
Алгоритмді енгізу
Паскаль біріктіру сұрыптауы төменде көрсетілген.
Procedure MergeSort(аты: жол; var f: мәтін); Var a1, a2, s, i, j, kol, tmp: бүтін; f1, f2: мәтін; б: логикалық Begincol:=0; Тағайындау(f, аты); қалпына келтіру(f); EOF(f) болмаса да оқуды бастаңыз(f, a1); inc(col); Соңы; жабу(f); Assign(f1, '{1-ші көмекші файлдың аты}'); Assign(f2, '{2-ші көмекші файлдың аты}'); s:=1; Әзірге (s<kol) Reset(f) басталады; қайта жазу(f1); қайта жазу(f2); i:=1 to kol div 2 үшін Read(f, a1); Write(f1, a1, ' '); Соңы; Егер (kol div 2) mod s0 болса, онда tmp:=kol div 2 басталады; tmp mod s0 басталатын кезде Read(f, a1); Write(f1, a1, ' '); inc(tmp); Соңы; Соңы; EOF(f) болмаса да Read(f, a2) бастаңыз; Write(f2, a2, ' '); Соңы; жабу(f); жабу(f1); жабу(f2); қайта жазу(f); қалпына келтіру(f1); қалпына келтіру(f2); Оқу(f1, a1); Оқу(f2, a2); Әзірге (EOF(f1) емес) және (EOF(f2) емес) басталады i:=0; j:=0; b:=шын; (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 болмаса, 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); жабу(f1); жабу(f2); s:=s2; Соңы; Өшіру(f1); Өшіру(f2); Соңы;
Алгоритмнің жұмысы визуалды түрде былай көрінеді (жоғары – ретсіз реттілік, төменгі – реттелген).
Сыртқы деректерді сұрыптау
Компьютердің сыртқы жадында орналасқан кейбір деректерді сұрыптау қажеттілігі жиі туындайды. Кейбір жағдайларда олар әсерлі өлшемге ие және оларға қол жеткізуді жеңілдету үшін жедел жадқа орналастыру мүмкін емес. Мұндай жағдайларда сыртқы сұрыптау әдістері қолданылады.
Сыртқы медиаға кіру қажеттілігі өңдеу уақытының тиімділігін төмендетеді.
Жұмыстың күрделілігі мынада, алгоритм бір уақытта деректер ағынының бір элементіне ғана қол жеткізе алады. Және бұл жағдайда ең жақсы нәтижелердің бірі екі файлдың элементтерін бірінен кейін бірін ретімен салыстыра алатын біріктіру сұрыптау әдісі арқылы көрсетіледі.
Деректерді оқусыртқы көз, оларды өңдеу және соңғы файлға жазу реттелген блоктарда (серияларда) жүзеге асырылады. Реттелген қатар өлшемімен жұмыс істеу тәсілі бойынша сұрыптаудың екі түрі бар: қарапайым және табиғи біріктіру.
Қарапайым біріктіру
Қарапайым біріктіру арқылы серия ұзындығы бекітіледі.
Осылайша, бастапқы сұрыпталмаған файлда барлық қатарлар бір элементтен тұрады. Бірінші қадамнан кейін өлшем екіге дейін артады. Келесі - 4, 8, 16 және т.б.
Ол келесідей жұмыс істейді:
- Бастапқы файл (f) екі көмекшіге бөлінген - f1, f2.
- Олар қайтадан бір файлға біріктіріледі (f), бірақ сонымен бірге барлық элементтер жұппен салыстырылады және жұптар құрайды. Бұл қадамдағы серия өлшемі екі болады.
- 1-қадам қайталанады.
- 2-қадам қайталанады, бірақ бұрыннан реттелген 2-лер сұрыпталған 4-тер үшін біріктірілген.
- Бүкіл файл сұрыпталғанша, цикл жалғасады, әр иерациядағы қатарды көбейтеді.
Қарапайым біріктіру арқылы сыртқы сұрыптау аяқталғанын қайдан білесіз?
- жаңа серия ұзындығы (біріктіргеннен кейін) элементтердің жалпы санынан кем емес;
- бір ғана эпизод қалды;
- Көмекші файл f2 бос қалды.
Қарапайым біріктірудің кемшіліктері мыналар: орындау ұзақтығы әрбір біріктіру рұқсатында бекітілгендіктен, ішінара реттелген деректерді өңдеуге толығымен кездейсоқ деректер сияқты ұзақ уақыт кетеді.
Табиғи синтез
Бұл әдіс ұзындықты шектемейдісериясы, бірақ мүмкін болатын максималды таңдайды.
Сұрыптау алгоритмі:
- f файлындағы бастапқы тізбекті оқу. Бірінші қабылданған элемент f1 файлына жазылады.
- Егер келесі жазба сұрыптау шартын қанағаттандырса, онда ол сол жерде, егер орындалмаса, екінші көмекші f2 файлына жазылады.
- Осылайша, бастапқы файлдың барлық жазбалары таратылады және серияның ағымдағы өлшемін анықтайтын f1 ішінде реттелген реттілік қалыптасады.
- f1 және f2 файлдары біріктірілді.
- Цикл қайталанады.
Қатарлардың көлемі белгіленбегендіктен, кезектің соңын арнайы таңбамен белгілеу қажет. Сондықтан біріктіру кезінде салыстыру саны артады. Сонымен қатар, көмекші файлдардың бірінің өлшемі түпнұсқаның өлшеміне жақын болуы мүмкін.
Орташа алғанда табиғи біріктіру сыртқы сұрыптаумен қарапайым біріктіруге қарағанда тиімдірек.
Алгоритм мүмкіндіктері
Екі бірдей мәнді салыстыру кезінде әдіс олардың бастапқы ретін сақтайды, яғни тұрақты.
Сұрыптау процесін бірнеше ағындарға өте сәтті бөлуге болады.
Бейне біріктіру сұрыптау алгоритмінің жұмысын анық көрсетеді.
