Ikki saralangan massivni birlashtirish
Ikkita do‘stingiz alifbo tartibida kitob ro‘yxatini tuzib kelgan bo‘lsin. Sizga bu ikki ro‘yxatni bitta, yana alifbo tartibida bo‘lgan ro‘yxatga birlashtirish kerak. Ikkala ro‘yxatni yana boshidan saralashning hojati yo‘q — ular allaqachon tartiblangan. Kerak bo‘lgani — ikkala ro‘yxatning boshidan boshlab, har safar kichikroq nomni tanlab, natijaga qo‘shib borish.
Aynan shu masala — ikkita saralangan massivni bitta saralangan massivga birlashtirish — dasturlashda juda tez-tez uchraydi. Bu, ayni paytda, merge sort algoritmining markazidagi operatsiya.
Masala
Ikkita saralangan massiv berilgan. Ularni bitta, o‘sish tartibida saralangan massivga birlashtiring.
KIRISH: A = [1, 3, 5, 7]
B = [2, 4, 6, 8]
NATIJA: [1, 2, 3, 4, 5, 6, 7, 8]
KIRISH: A = [1, 2, 9]
B = [3, 5]
NATIJA: [1, 2, 3, 5, 9]
KIRISH: A = []
B = [1, 2, 3]
NATIJA: [1, 2, 3]
Yondashuvni topish
Naiv yechim — ikkala massivni bitta katta massivga qo‘shib, keyin uni saralash bo‘lardi. Bu ishlaydi, lekin ma’noga ega emas: biz allaqachon saralangan ma’lumotdan foydalanish o‘rniga uni tashlab yubormoqdamiz. Saralash O(n log n) vaqt talab qiladi, holbuki ma’lumotning tartibliligidan foydalansak, buni ancha tezroq qilish mumkin.
To‘g‘ri fikrlash — ikkala massivning eng boshidagi elementlarini solishtirish. Ikkalasi ham saralangan bo‘lgani uchun, ikkala massivning eng kichik elementi aynan shu ikki elementning biri bo‘lishi shart. Kichigi natijaga qo‘shiladi, o‘sha massivda keyingi elementga o‘tiladi, va jarayon takrorlanadi.
Rekursiv yechim
Bu masalani rekursiv tarzda ifodalash mumkin: “ikkita massivni birlashtirish” muammosi “ikkala massivning boshidagi eng kichik elementni ajratib olish, so‘ng qolgan qismlarni birlashtirish” muammosiga tenglashadi.
FUNCTION MERGE(A, i, B, j)
IF i = A uzunligi
RETURN B[j:] (B ning qolgan qismi)
IF j = B uzunligi
RETURN A[i:] (A ning qolgan qismi)
IF A[i] <= B[j]
RETURN [A[i]] + MERGE(A, i + 1, B, j)
RETURN [B[j]] + MERGE(A, i, B, j + 1)
i va j — mos ravishda A va B massivlarida hali ko‘rilmagan elementning indeksi. Tayanch holat ikkita: qaysi biri bo‘lsa, bitta massiv tugab, ikkinchisining qolgan qismini to‘g‘ridan-to‘g‘ri qaytarish kerak.
Bosqichma-bosqich tahlil
A = [1, 4, 6], B = [2, 3] massivlarini birlashtiraylik.
MERGE(A, 0, B, 0) A[0]=1, B[0]=2, 1<=2
= [1] + MERGE(A, 1, B, 0)
MERGE(A, 1, B, 0) A[1]=4, B[0]=2, 4>2
= [2] + MERGE(A, 1, B, 1)
MERGE(A, 1, B, 1) A[1]=4, B[1]=3, 4>3
= [3] + MERGE(A, 1, B, 2)
MERGE(A, 1, B, 2) j = B uzunligi (2) — tayanch holat
= A[1:] = [4, 6]
Endi natijalarni pastdan yuqoriga qarab yig‘amiz:
MERGE(A, 1, B, 2) = [4, 6]
MERGE(A, 1, B, 1) = [3] + [4, 6] = [3, 4, 6]
MERGE(A, 1, B, 0) = [2] + [3, 4, 6] = [2, 3, 4, 6]
MERGE(A, 0, B, 0) = [1] + [2, 3, 4, 6] = [1, 2, 3, 4, 6]
Yakuniy natija — [1, 2, 3, 4, 6]. Har bir qadam faqat ikkita elementni solishtiradi va kichigini natijaning boshiga qo‘shadi; qolgan ish kichikroq muammoga topshiriladi.
Vaqt va xotira murakkabligi
Har bir rekursiv chaqiruv i yoki j ko‘rsatkichlaridan birini bittaga oshiradi. A massivi m ta, B massivi n ta elementdan iborat bo‘lsa, ikkala ko‘rsatkich birgalikda ko‘pi bilan m + n marta oshishi mumkin — chunki har chaqiruvda ulardan biri albatta bir birlikka siljiydi.
Demak, chaqiruvlar soni, ya’ni vaqt murakkabligi O(m + n) — ikkala massivning umumiy uzunligiga chiziqli bog‘liq. Bu kutilgan natija: har bir elementni natijaga qo‘yish uchun kamida bitta amal bajarilishi kerak, ortiqcha ish yo‘q.
Xotira jihatidan ikki narsani hisobga olish kerak. Birinchisi — call stack chuqurligi: eng yomon holatda (masalan, bitta massiv juda uzun) chuqurlik O(m + n) ga yetishi mumkin. Ikkinchisi — natija massivini qanday quramiz. Yuqoridagi pseudocode har chaqiruvda [A[i]] + MERGE(...) shaklida yangi ro‘yxat yaratadi — bu tushunishga qulay, lekin amalda har safar nusxa olish qo‘shimcha xotira sarflaydi. Amaliy implementatsiyada natija oldindan ajratilgan bitta massivga indekslar orqali to‘ldiriladi, natijada qo‘shimcha xotira faqat O(m + n) natija massivi va O(m + n) call stack bilan cheklanadi.
Iterativ variant bilan taqqoslash
Aynan shu masalani sikl bilan ham yechish mumkin — bu Merge sort maqolasida ko‘rilgan merge funksiyasi:
FUNCTION MERGE_ITERATIVE(A, B)
natija = bo‘sh massiv
i = 0
j = 0
WHILE i < A uzunligi VA j < B uzunligi
IF A[i] <= B[j]
natija ga A[i] qo‘sh
i = i + 1
ELSE
natija ga B[j] qo‘sh
j = j + 1
natija ga A[i:] qo‘sh
natija ga B[j:] qo‘sh
RETURN natija
Ikkala variant ham O(m + n) vaqtda ishlaydi. Farq xotira profilida: iterativ variant O(1) qo‘shimcha stack xotirasi ishlatadi (faqat natija massivi kerak), rekursiv variant esa O(m + n) call stack xotirasini qo‘shadi. Amaliyotda bu masala uchun iterativ yechim afzalroq — chunki muammoning o‘zi chiziqli va daraxt yoki ichma-ich tuzilishga ega emas. Rekursiv yechim esa g‘oyani ochib berish, va merge sortdagi rekursiya bilan bog‘liqligini ko‘rsatish uchun foydali.
Teng qiymatlarda tanlov
A[i] <= B[j] shartida teng bo‘lgan holatda Adan olish tasodifiy emas. Agar ikkala massiv allaqachon barqaror (stable) saralangan bo‘lsa va ularning asl tartibini saqlash kerak bo‘lsa (masalan, A boshqa massivdan oldinroq kelgan hisoblansa), teng qiymatda doim bitta belgilangan massivdan olish natijaning barqarorligini ta’minlaydi.
Edge case’lar
Bitta massiv bo‘sh
A = [] bo‘lsa, natija to‘g‘ridan-to‘g‘ri Bning o‘zi bo‘lishi kerak. Tayanch holatlar (i = A uzunligi yoki j = B uzunligi) buni avtomatik qamrab oladi — algoritmga bo‘sh massiv uchun alohida shart yozish shart emas.
Ikkala massiv ham bo‘sh
Natija bo‘sh massiv bo‘ladi. Bu ham tayanch holatlarning to‘g‘ridan-to‘g‘ri natijasi.
Massivlar teng uzunlikda emas
Algoritm bu holatni tabiiy tarzda boshqaradi — qisqaroq massiv tugagach, uzunroq massivning qolgan qismi to‘g‘ridan-to‘g‘ri ko‘chiriladi. Bu yerdagi keng tarqalgan xato — faqat ikkala massiv bir vaqtda tugaydi deb faraz qilib, faqat WHILE i < A uzunligi VA j < B uzunligi sharti bilan chegaralanib qolish va qolgan elementlarni ko‘chirishni unutish.
Massivlar saralanmagan bo‘lsa
Bu algoritm ikkala massiv allaqachon saralangan deb faraz qiladi. Agar kirish saralanmagan bo‘lsa, algoritm hech qanday xato bermaydi, lekin natija ham saralangan bo‘lmaydi — chunki mantiq faqat ikkala massivning “joriy eng kichik” elementini solishtirishga asoslangan, bu esa faqat kirish saralangan bo‘lgandagina to‘g‘ri ishlaydi.
Real qo‘llanish
Merge sortning yuragi. Merge sort massivni rekursiv ravishda ikkiga bo‘lib, har yarmini alohida saralaydi, so‘ng aynan shu birlashtirish operatsiyasi orqali ikkala saralangan yarmni bitta massivga qo‘shadi. Merge sortning O(n log n) tezligi ana shu O(n) birlashtirish operatsiyasining log n marta takrorlanishidan kelib chiqadi.
Ma’lumotlar bazalarida JOIN va birlashtirish. Ikki saralangan jadval yozuvini umumiy kalit bo‘yicha birlashtirishda (merge join deb ataladigan usulda) xuddi shu ikki ko‘rsatkichli yondashuv ishlatiladi — chunki ma’lumot indeks bo‘yicha saralangan bo‘lsa, uni qayta saralashning hojati yo‘q.
Versiya nazorati tizimlari. Ikki foydalanuvchi qilgan o‘zgarishlarni vaqt bo‘yicha saralangan holda birlashtirishda (masalan, log fayllarni yoki commit tarixini birlashtirishda) shunga o‘xshash mantiq qo‘llaniladi.
Eng muhim xulosa
Ikkita saralangan massivni birlashtirish masalasi — ma’lumotning allaqachon tartibli ekanligidan qanday foydalanish mumkinligini ko‘rsatadigan yaxshi misol. Har ikkala massivning boshidagi elementlarni solishtirib, kichigini olish va qolganini kichikroq muammoga topshirish — bu rekursiyaning tabiiy qo‘llanilishi, garchi bu masala amalda ko‘pincha sikl bilan yozilsa ham.
Bu operatsiyani tushunish merge sort algoritmining nima uchun O(n log n) ekanini yanada aniq tasavvur qilishga yordam beradi. Keyingi masalada esa boshqa turdagi savolni ko‘ramiz: massivni to‘liq saralamasdan, undagi k-chi eng katta elementni qanday topish mumkin.