Merge sort. Birlashtirish orqali massivni tartiblash.
Salom! Bugun ancha qiyinroq mavzu -
Birlashtirish orqali massivni tartiblash. Keling birgalashib, massivni tartibga solib qo'yamiz. 😁😄😁
😇
Github:
MergeSort
⏰
Time complexity: O(N * logN)
🔎
Space complexity: O(N)
🧑💻 G'oya 🧑💻
Birlashtirish orqali massivni tartiblash algoritmi berilgan massivni kichikroq massivlarga bo'lish va har bir kichik massivni tartiblash, keyin shu tartiblangan kichik massivlardan katta massivni birlashtirish orqali ishlaydi.
Boshqa so'z bilan aytganda, siz berilgan massivni ikkita teng massivga bo'lasiz, har birini tartiblaysiz va keyin ularni bir qayta birlashtirasiz. Bu jarayonni to'la massiv tartibga solingani qadar bajarasiz.
Nimaga bu algoritm zo'r? Chiziqli funksiya logarifmlik funksiyaga ko'paytirilgan funksiyani kvadrat funksiya bilan taqqoslashtiring.
🧑💻 Algorithm 🧑💻
Agar code-ga qarasangiz, siz 3ta metodni ko'rasiz. Bular mergeSort(), recursiveMergeSort() va merge().
Ahamiyat bering: Men ishlatgan usulda yangi kichik massivlarni yaratilmaydi. Buning o'rniga bitta uzunligi teng massiv yaratiladi va u elementlarni vaqtincha saqlab turish uchun ishlatiladi. Bunga elementlarning indekslarini chegaralar sifatida ishlatilish orqali erishiladi.
👩💻 mergeSort():
- workSpace massivini elementlarni vaqtincha saqlash uchun ishlatasiz.
- recursiveMergeSort() metodini chaqirasiz va unga parametrlar sifatida workSpace, chap chegara va o'ng chegaralarni berib yuborasiz.
👩💻 recursiveMergeSort():
Bu metod berilgan massivni teng qismlarga bo'lib chiqish va keyin ularni ulash uchun ishlatiladi.
- Agar chap va o'ng chegaralar teng bo'lsa, metod hozirgi bajarilishini to'xtatasiz.
- Aksincha massivning o'rta indeksini topasiz. Bundan so'ng rekursiv tarzda shu metodni chap qism va o'ng qism uchun bajarasiz. Keyin esa ikkita qism birlashtiriladi.
👩💻 merge():
Bu metod ikkita (yarim) qismni birlashtirish uchun ishlatiladi.
- Sizda chap chegara va chap chegara yana alohida ko'rsatgich bo'ladi. Chap chegara ko'rsatgichi bu vaqtincha massivga chap tarafdan qo'shiladigan elementning ko'rsatgichidir. Sizda yana o'ng chegara va o'ng qismning boshini ko'rsatuvchi o'zgaruvchi bo'ladi. Bular o'ng tarafda qo'shiladigan elementlarning chegaralarni ko'rsatuvchi sonlar.
- Birinchi while loop ichida siz ikkita qismdan eng kichik elementdan boshlab, eng katta elementgacha workSpace massiviga kiritib chiqasiz.
- Ikkinchi while loop ichida chap qismdan qolib ketgan elementlarni workSpace-ga qo'shib chiqasiz.
- Uchinchi while loop ichida esa o'ng qismdan qolib ketgan elementlarni workSpace-ga qo'shib chiqasiz.
- for loop ichida biz merge() metodining hozirgi bajarilishida tartiblangan elementlarni berilgan massivga yozib qo'yamiz.
☝️ Manbalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2.
Geeksforgeeks
3.
Wikipedia
Bugunga shu.
Agar qaysidir qism bo'yicha savollaringiz bo'lsa, comments-da yozing.
Omad! ✌️😎
@azamovme
