Birlashtirish tartibi 1945-yilda buyuk matematik Jon fon Neyman tomonidan ishlab chiqilgan kompyuter fanining asosiy algoritmlaridan biridir. Manhetten loyihasida ishtirok etar ekan, Neumann katta hajmdagi ma'lumotlarni samarali qayta ishlash zarurati bilan duch keldi. U ishlab chiqqan usulda “bo‘l va zabt et” tamoyili qo‘llanilgan, bu ish uchun zarur bo‘lgan vaqtni sezilarli darajada qisqartirgan.
Algoritm printsipi va foydalanish
Birlashtirish saralash usuli massivlar, roʻyxatlar, oqimlar kabi elementlarga ruxsat berilgan tuzilmalarni saralash muammolarida qoʻllaniladi.
Qayta ishlash jarayonida dastlabki ma'lumotlar bloki kichik komponentlarga bo'linadi, bitta elementgacha, bu aslida tartiblangan ro'yxatdir. Keyin u to'g'ri tartibda qayta yig'iladi.
Ma'lum uzunlikdagi massivni saralash uchun bir xil o'lchamdagi qo'shimcha xotira maydoni talab qilinadi, unda tartiblangan massiv qismlarga bo'linadi.
Usul raqamlar yoki satrlar kabi har qanday taqqoslanadigan ma'lumotlar turiga buyurtma berish uchun ishlatilishi mumkin.
Birlashtirish tartiblanganuchastkalar
Algoritmni tushunish uchun uning tahlilini oxiridan - tartiblangan bloklarni birlashtirish mexanizmidan boshlaylik.
Tasavvur qilaylik, bizda har qanday usulda tartiblangan ikkita raqamlar massivi bor, ularni tartiblash buzilmasligi uchun bir-biri bilan birlashtirish kerak. Oddiylik uchun raqamlarni o'sish tartibida tartiblaymiz.
Elementar misol: ikkala massiv ham bittadan elementdan iborat.
int arr1={31}; int arr2={18};
Ularni birlashtirish uchun siz birinchi massivning nol elementini (raqamlash noldan boshlanishini unutmang) va ikkinchi massivning nol elementini olishingiz kerak. Bular, mos ravishda, 31 va 18. Saralash shartiga ko'ra, 18 soni birinchi bo'lishi kerak, chunki u kamroq. Raqamlarni to'g'ri tartibda qo'ying:
int natija={18, 31};
Keling, murakkabroq misolni ko'rib chiqaylik, bunda har bir massiv bir nechta elementlardan iborat:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Birlashtirish algoritmi kichikroq elementlarni ketma-ket taqqoslash va ularni olingan massivga toʻgʻri tartibda joylashtirishdan iborat boʻladi. Joriy indekslarni kuzatib borish uchun ikkita o'zgaruvchini kiritamiz - indeks1 va indeks2. Dastlab biz ularni nolga qo‘ydik, chunki massivlar tartiblangan va eng kichik elementlar boshida joylashgan.
int indeks1=0; int indeks2=0;
Birlashtirish jarayonini bosqichma-bosqich yozamiz:
- Indeks1 ga ega elementni arr1 massividan, indeks2 ga ega elementni arr2 massivdan oling.
- Taqqoslang, ulardan eng kichigini tanlang va kiritingolingan massiv.
- Kichikroq elementning joriy indeksini 1 ga oshiring.
- Birinchi bosqichdan davom eting.
Birinchi orbitada vaziyat quyidagicha ko'rinadi:
index1=0; indeks2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indeks1++; natija[0]=arr1[0]; // natija=[2]
Ikkinchi burilishda:
index1=1; indeks2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indeks2++; natija[1]=arr2[0]; // natija=[2, 5]
Uchinchisi:
index1=1; indeks2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; indeks2++; natija[2]=arr2[1]; // natija=[2, 5, 6]
Va hokazo, natijada toʻliq tartiblangan massiv hosil boʻlguncha: {2, 5, 6, 17, 21, 19, 30, 45}.
Har xil uzunlikdagi massivlar birlashtirilsa, ma'lum qiyinchiliklar paydo bo'lishi mumkin. Joriy indekslardan biri oxirgi elementga yetib, ikkinchi massivda hali ham a'zolar qolsa-chi?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 bosqichli indeks1=0, indeks2=0; 1 2 natija={1, 2}; // 3 bosqichli indeks1=1, indeks2=1; 4 < 5 natija={1, 2, 4}; //4 bosqichli indeks1=2, indeks2=1 ??
Indeks1 oʻzgaruvchisi 2 qiymatiga yetdi, lekin arr1 massivida bu indeksli element yoʻq. Bu yerda hammasi oddiy: ikkinchi massivning qolgan elementlarini ularning tartibini saqlab, natijada olinganiga o‘tkazing.
natija={1, 2, 4, 5, 6, 7, 9};
Bu holat bizga zaruratdan dalolat beradijoriy tekshirish indeksini birlashtirilayotgan massiv uzunligiga moslang.
Har xil uzunlikdagi tartiblangan ketma-ketliklar (A va B) uchun birlashtirish sxemasi:
- Agar ikkala ketma-ketlikning uzunligi 0 dan katta boʻlsa, A[0] va B[0] ni solishtiring va kichigini buferga oʻtkazing.
- Agar ketma-ketliklardan birining uzunligi 0 bo'lsa, ikkinchi ketma-ketlikning qolgan elementlarini oling va ularning tartibini o'zgartirmasdan, buferning oxiriga o'ting.
Ikkinchi bosqichni amalga oshirish
Java-da ikkita tartiblangan massivni birlashtirish misoli quyida keltirilgan.
int a1=yangi int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=yangi 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; uchun (int k=0; k a1.uzunlik-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++; } }
Bu yerda:
- a1 va a2 - birlashtiriladigan asl tartiblangan massivlar;
- a3 – yakuniy massiv;
- i va j - a1 va a2 massivlari uchun joriy elementlarning indekslari.
Birinchi va ikkinchi agar shartlar indekslar massiv hajmidan tashqariga chiqmasligini ta'minlaydi. Uchinchi va toʻrtinchi shart bloklari mos ravishda kichikroq elementning natijaviy massiviga oʻtkaziladi.
Boʻl va zabt et
Shunday qilib, biz tartiblanganlarni birlashtirishni o'rgandikqadriyatlar to'plami. Aytish mumkinki, birlashma tartiblash algoritmining ikkinchi qismi – birlashmaning o‘zi allaqachon tartiblangan.
Biroq, siz asl tartiblanmagan raqamlar qatoridan birlashtirilishi mumkin boʻlgan bir nechta tartiblangan raqamlarga qanday oʻtishni tushunishingiz kerak.
Algoritmning birinchi bosqichini koʻrib chiqamiz va massivlarni qanday ajratishni oʻrganamiz.
Bu qiyin emas - qiymatlarning asl ro'yxati yarmiga bo'linadi, keyin har bir qism ham ikkiga bo'linadi va juda kichik bloklar olinmaguncha shunday davom etadi.
Bunday minimal elementlarning uzunligi bittaga teng boʻlishi mumkin, yaʼni ular oʻzlari tartiblangan massiv boʻlishi mumkin, lekin bu zaruriy shart emas. Blokning oʻlchami oldindan aniqlanadi va uni buyurtma qilish uchun kichik oʻlchamdagi massivlar (masalan, tezkor saralash yoki kiritish tartibi) bilan samarali ishlaydigan har qanday mos tartiblash algoritmidan foydalanish mumkin.
Bu shunday.
// asl massiv {34, 95, 10, 2, 102, 70}; // birinchi bo'linish {34, 95, 10} va {2, 102, 70}; // ikkinchi boʻlinish {34} va {95, 10} va {2} va {102, 70}
1-2 ta elementdan tashkil topgan bloklarni tartibga solish juda oson.
Shundan soʻng, biz allaqachon qilishni oʻrgangan aʼzolar tartibini saqlab, tartiblangan kichik massivlarni juftlik bilan birlashtirishingiz kerak.
Birinchi bosqichni amalga oshirish
Masivning rekursiv boʻlinishi quyida koʻrsatilgan.
void mergeSort(T a, uzoq boshlanish, uzoq tugatish) { uzun boʻlinish; agar(boshlash < tugatish) { bo'linish=(boshlash + tugatish)/2; mergeSort(a, boshlash, ajratish); mergeSort(a, split+1, tugatish); birlashtirish (a, boshlash, ajratish, tugatish); } }
Bu kodda nima sodir boʻladi:
-
MergeSort funksiyasi
a
boshlangʻich massivini va saralanadigan hududning chap va oʻng chegaralarini oladi (indekslar boshlanish va
- finish).
-
Agar bu boʻlimning uzunligi bittadan katta boʻlsa (
start < finish
), u ikki qismga boʻlinadi (indeks boʻyicha
- split) va har biri rekursiv tartiblangan.
-
Chap tomon uchun rekursiv funksiya chaqiruvida chizmaning boshlang'ich indeksi va
split
indeksi uzatiladi. To'g'ri bo'limning boshi mos ravishda
- (bo'lingan + 1), oxiri esa asl qismning oxirgi indeksi bo'ladi.
-
Funksiya
merge
ikkita tartiblangan ketma-ketlikni oladi (
a[start]…a[split]
va
- a[bo'lingan +1]…a[finish]) va ularni saralash tartibida birlashtiradi.
Birlashtirish funksiyasining mexanikasi yuqorida muhokama qilingan.
Algoritmning umumiy sxemasi
Masivlarni birlashtirish usuli ikkita katta bosqichdan iborat:
- Tartiblanmagan asl massivni kichik qismlarga ajrating.
- Saralash qoidasiga rioya qilgan holda ularni juft-juft qilib toʻplang.
Katta va murakkab vazifa koʻplab oddiy vazifalarga boʻlinadi, ular ketma-ket hal qilinadi va bu kerakli natijaga olib keladi.
Usulni baholash
Birlashtirishning vaqt murakkabligi ajratilgan daraxt balandligi bilan belgilanadialgoritm va massivdagi elementlar sonining (n) uning logarifmini (log n) ko‘paytirishga teng. Bunday taxmin logarifmik deb ataladi.
Bu usulning ham afzalligi, ham kamchiligi. Asl massiv teskari tartibda tartiblanganda ham uning ishlash vaqti eng yomon holatda ham o'zgarmaydi. Biroq, toʻliq tartiblangan maʼlumotlarni qayta ishlashda algoritm vaqtni oshirmaydi.
Shuningdek, birlashtirishning saralash usulining xotira narxini ham hisobga olish kerak. Ular asl kollektsiya hajmiga teng. Bu qoʻshimcha ajratilgan maydonda qismlardan tartiblangan massiv yigʻiladi.
Algoritmni amalga oshirish
Paskalni birlashtirish tartibi quyida ko'rsatilgan.
Protsedura MergeSort(nom: string; var f: text); Var a1, a2, s, i, j, kol, tmp: butun son; f1, f2: matn; b: mantiqiy Begincol:=0; Tayinlash (f, ism); qayta o'rnatish (f); EOF(f) bo'lmasa-da, o'qishni boshlang (f, a1); inc(col); oxiri; yopish (f); Assign(f1, '{1-yordamchi fayl nomi}'); Assign(f2, '{2-yordamchi fayl nomi}'); s:=1; Holbuki (s<kol) Reset(f) boshlanadi; qayta yozish (f1); qayta yozish (f2); For i:=1 to kol div 2 do begin Read(f, a1); Write(f1, a1, ' '); oxiri; Agar (kol div 2) mod s0 bo'lsa, tmp ni boshlang:=kol div 2; Tmp mod s0 o'qishni boshlaganda (f, a1); Write(f1, a1, ' '); inc(tmp); oxiri; oxiri; EOF(f) bo'lmasa-da, Read(f, a2) ni boshlang; Write(f2, a2, ' '); oxiri; yopish (f); yopish (f1); yopish (f2); qayta yozish (f); qayta o'rnatish (f1); qayta o'rnatish (f2); O'qish (f1, a1); O'qish (f2, a2); Holbuki (EOF(f1) emas) va (EOF(f2) emas) boshlanadi i:=0; j:=0; b:=to'g'ri; (b) va (EOF(f1) emas) va (EOF(f2) emas) boshlanganda, agar (a1<a2) boshlanadiWrite(f, a1, ' '); O'qish (f1, a1); inc(i); End else begin Write(f, a2, ' '); O'qish (f2, a2); inc(j); oxiri; Agar (i=s) yoki (j=s) bo'lsa, b:=false; oxiri; Agar b bo'lmasa, while (i<s) va (EOF(f1) emas) boshlanadi Write(f, a1, ' '); O'qish (f1, a1); inc(i); oxiri; (j<s) va (EOF(f2) emas) Write(f, a2, ' '); O'qish (f2, a2); inc(j); oxiri; oxiri; oxiri; EOF(f1) bo'lmasa ham tmp:=a1; O'qish (f1, a1); Agar EOF(f1) bo'lmasa, Write(f, tmp, ' ') else Write(f, tmp); oxiri; EOF(f2) bo'lmasa ham tmp:=a2; O'qish (f2, a2); Agar EOF(f2) bo'lmasa, Write(f, tmp, ' ') boshqacha Write(f, tmp); oxiri; yopish (f); yopish (f1); yopish (f2); s:=s2; oxiri; Oʻchirish(f1); Oʻchirish(f2); Tugash;
Vizual ravishda algoritmning ishlashi quyidagicha ko'rinadi (yuqori - tartibsiz ketma-ketlik, pastki - tartibli).
Tashqi ma'lumotlarni saralash
Ko'pincha kompyuterning tashqi xotirasida joylashgan ba'zi ma'lumotlarni saralash kerak bo'ladi. Ba'zi hollarda, ular ta'sirchan hajmga ega va ularga kirishni osonlashtirish uchun RAMga joylashtirilmaydi. Bunday hollarda tashqi saralash usullari qo'llaniladi.
Tashqi mediaga kirish zarurati ishlov berish vaqti samaradorligini pasaytiradi.
Ishning murakkabligi shundaki, algoritm bir vaqtning o'zida ma'lumotlar oqimining faqat bitta elementiga kira oladi. Va bu holda, eng yaxshi natijalardan biri ikkita faylning elementlarini ketma-ket taqqoslashi mumkin bo'lgan birlashma tartiblash usuli bilan ko'rsatiladi.
Ma'lumotni o'qishtashqi manba, ularni qayta ishlash va yakuniy faylga yozish tartiblangan bloklarda (seriyalarda) amalga oshiriladi. Buyurtma qilingan seriyalar hajmi bilan ishlash usuliga ko'ra, saralashning ikki turi mavjud: oddiy va tabiiy birlashma.
Oddiy birlashtirish
Oddiy birlashma bilan seriya uzunligi aniqlanadi.
Shunday qilib, asl tartiblanmagan faylda barcha seriyalar bitta elementdan iborat. Birinchi qadamdan keyin o'lcham ikkiga ko'tariladi. Keyingi - 4, 8, 16 va hokazo.
Bu shunday ishlaydi:
- Manba fayl (f) ikkita yordamchi faylga bo'lingan - f1, f2.
- Ular yana bitta faylga (f) birlashtiriladi, lekin shu bilan birga barcha elementlar juftlikda taqqoslanadi va juftlik hosil qiladi. Bu bosqichda seriya hajmi ikkiga aylanadi.
- 1-qadam takrorlanadi.
- 2-qadam takrorlanadi, lekin allaqachon buyurtma qilingan 2-lar birlashtirilib tartiblangan 4-sonlarni hosil qiladi.
- Silka davom etadi va butun fayl saralanmaguncha har bir iteratsiyada ketma-ketlikni oshiradi.
Oddiy birlashma bilan tashqi saralash tugallanganini qayerdan bilasiz?
- yangi seriya uzunligi (birlashtirilgandan keyin) elementlarning umumiy sonidan kam emas;
- faqat bitta qism qoldi;
- F2 yordamchi fayli boʻsh qoldi.
Oddiy birlashtirishning kamchiliklari quyidagilardir: ishga tushirish uzunligi har bir birlashma yoʻlida belgilangan boʻlgani uchun, qisman tartiblangan maʼlumotlarni qayta ishlash toʻliq tasodifiy maʼlumotlar kabi uzoq davom etadi.
Tabiiy sintez
Ushbu usul uzunlikni cheklamaydiqator, lekin mumkin boʻlgan maksimalni tanlaydi.
Tartiblash algoritmi:
- f faylidagi dastlabki ketma-ketlikni o'qish. Birinchi qabul qilingan element f1 fayliga yoziladi.
- Agar keyingi yozuv saralash shartiga javob bersa, u oʻsha yerda, agar boʻlmasa, f2 ikkinchi yordamchi faylga yoziladi.
- Shunday qilib, manba faylning barcha yozuvlari taqsimlanadi va f1 da tartiblangan ketma-ketlik hosil boʻladi, bu qatorning joriy hajmini belgilaydi.
- f1 va f2 fayllari birlashtirildi.
- Tsikl takrorlanadi.
Serialning oʻlchami qatʼiy boʻlmagani uchun ketma-ketlik oxirini maxsus belgi bilan belgilash kerak. Shuning uchun, birlashtirganda, taqqoslashlar soni ortadi. Bundan tashqari, yordamchi fayllardan birining oʻlchami asl nusxaga yaqin boʻlishi mumkin.
Oʻrtacha, tabiiy birlashma tashqi tartib bilan oddiy birlashmaga qaraganda samaraliroq.
Algoritmning xususiyatlari
Ikki bir xil qiymatni solishtirganda usul ularning asl tartibini saqlaydi, ya'ni barqaror.
Tartiblash jarayoni juda muvaffaqiyatli tarzda bir nechta mavzularga boʻlinishi mumkin.
Videoda birlashtirish tartiblash algoritmining ishlashi aniq koʻrsatilgan.
