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};
Нэгдүүлэх алгоритм нь жижиг элементүүдийг дараалан харьцуулж, тэдгээрийг үүссэн массивын зөв дарааллаар байрлуулахаас бүрдэнэ. Одоо байгаа индексүүдийг хянахын тулд индекс1 ба индекс2 гэсэн хоёр хувьсагчийг оруулъя. Массивууд эрэмбэлэгдсэн, хамгийн жижиг элементүүд нь эхэнд байгаа тул бид эхний ээлжинд тэдгээрийг тэг болгосон.
int индекс1=0; int индекс2=0;
Нэгтгэх үйл явцыг бүхэлд нь алхам алхмаар бичье:
- arr1 массиваас индекс1-тэй элементийг, arr2 массиваас индекс2-тэй элементийг авна уу.
- Харьцуулж, хамгийн жижигийг нь сонгоод оруулаарайүүссэн массив.
- Бага элементийн одоогийн индексийг 1-ээр нэмэгдүүлнэ.
- Эхний алхамаас үргэлжлүүл.
Эхний тойрог замд байдал дараах байдлаар харагдана:
index1=0; индекс2=0; arr1[0]=2; arr2[0]=5; arr1[0] < арр2[0]; индекс1++; үр дүн[0]=arr1[0]; // үр дүн=[2]
Хоёр дахь эргэхэд:
индекс1=1; индекс2=0; arr1[1]=17; arr2[0]=5; arr1[1] > арр2[0]; индекс2++; үр дүн[1]=arr2[0]; // үр дүн=[2, 5]
Гурав:
индекс1=1; индекс2=1; arr1[1]=17; arr2[1]=6; arr1[1] > арр2[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 ??
Индекс1 хувьсагч 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, урт эхлэл, урт дуусах) { урт хуваах; хэрэв(эхлэх < дуусгах) {хуваах=(эхлэх + дуусгах)/2; mergeSort(a, эхлэх, хуваах); mergeSort(a, хуваах+1, дуусгах); нэгтгэх(а, эхлэх, хуваах, дуусгах); } }
Энэ кодонд юу болдог вэ:
-
MergeSort функц нь
a
анхны массив болон эрэмбэлэх бүсийн зүүн ба баруун хүрээг авдаг (индексүүд эхлэх ба
- finish).
-
Хэрэв энэ хэсгийн урт нэгээс их байвал (
эхлэх < дуусгах
) хоёр хэсэгт хуваагдана (индексээр
- split) бөгөөд тус бүрийг рекурсив байдлаар эрэмбэлсэн.
-
Зүүн талын рекурсив функцийн дуудлагад графикийн эхлэлийн индекс болон
split
индексийг дамжуулдаг. Зөв хэсгийнх нь эхлэл нь
- (хуваах + 1) байх ба төгсгөл нь эх хэсгийн сүүлчийн индекс байх болно.
-
Функц
merge
нь дараалсан хоёр дараалал авдаг (
a[эхлэх]…a[хуваах]
болон
- a[хуваах" +1]…a[finish]) ба тэдгээрийг эрэмбэлэх дарааллаар нэгтгэнэ.
Нэгдүүлэх функцийн механикийг дээр авч үзсэн.
Алгоритмын ерөнхий схем
Нэгтгэх эрэмбэлэх арга нь хоёр том алхмаас бүрдэнэ:
- Ангилалгүй эх массивыг жижиг хэсгүүдэд хуваа.
- Ангилах дүрмийг дагаж хосоор нь цуглуул.
Том бөгөөд ээдрээтэй ажлыг олон энгийн даалгаврууд болгон хувааж, дарааллаар нь шийдэж, хүссэн үр дүндээ хүргэдэг.
Аргын үнэлгээ
Нэгдүүлэх төрлийн цагийн нарийн төвөгтэй байдлыг хуваах модны өндрөөр тодорхойлноалгоритм ба массив дахь элементийн тоог (n) логарифмыг (log n) үржүүлсэнтэй тэнцүү байна. Ийм тооцоог логарифм гэж нэрлэдэг.
Энэ нь аргын давуу болон сул тал юм. Анхны массивыг урвуу дарааллаар эрэмбэлэх үед түүний ажиллах хугацаа хамгийн муу тохиолдолд ч өөрчлөгддөггүй. Гэсэн хэдий ч бүрэн эрэмбэлэгдсэн өгөгдлийг боловсруулах үед алгоритм нь цаг хугацааны ашиг өгдөггүй.
Мөн нэгтгэх эрэмбэлэх аргын санах ойн зардлыг анхаарах нь чухал. Тэд анхны цуглуулгын хэмжээтэй тэнцүү байна. Энэ нэмэлт хуваарилагдсан хэсэгт хэсгүүдээс ангилсан массив угсарч байна.
Алгоритмыг хэрэгжүүлэх
Паскаль нэгтгэх төрлийг доор харуулав.
Procedure MergeSort(нэр: string; var f: text); 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); For i:=1 to kol div 2 do begin Read(f, a1); Write(f1, a1, ' '); Төгсгөл; Хэрэв (kol div 2) mod s0 бол tmp эхлэх:=kol div 2; tmp mod s0 уншиж эхлэх үед (f, a1); Write(f1, a1, ' '); inc(tmp); Төгсгөл; Төгсгөл; EOF(f) биш ч гэсэн Унших(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:=худал; Төгсгөл; Хэрэв үгүй бол b then start 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, ' ') өөрөөр Write(f, tmp); Төгсгөл; EOF(f2) биш ч гэсэн эхлэх tmp:=a2; Унших(f2, a2); Хэрэв EOF(f2) биш бол Write(f, tmp, ' ') өөрөөр Write(f, tmp); Төгсгөл; хаах(f); хаах(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 файлуудыг нэгтгэсэн.
- Цикл давтагдана.
Цуврал нь тогтворгүй хэмжээтэй тул дарааллын төгсгөлийг тусгай тэмдэгтээр тэмдэглэх шаардлагатай. Тиймээс нэгтгэх үед харьцуулах тоо нэмэгддэг. Нэмж хэлэхэд, туслах файлуудын аль нэгнийх нь хэмжээ эх файлын хэмжээтэй ойролцоо байж болно.
Дундажаар бол байгалийн нэгдэл нь гадаад төрлийн энгийн нэгдэлээс илүү үр дүнтэй байдаг.
Алгоритмын онцлог
Ижил хоёр утгыг харьцуулах үед арга нь анхны дарааллыг нь хадгалдаг, өөрөөр хэлбэл тогтвортой байдаг.
Ангилах процессыг олон хэлхээнд маш амжилттай хувааж болно.
Видео нь нэгтгэх эрэмбэлэх алгоритмын ажиллагааг тодорхой харуулж байна.
