Birlashtirib saralash (merge sort)
Birlashtirish tartibi
Birlashtirish tartibi algoritmi massivni avval kichikroq massivlarga bo‘lish, so‘ngra massivni saralash uchun to‘g‘ri yo‘l bilan birlashtirish yo‘li bilan saralash algoritmidir.
{{ msgDone }}
Bo‘lish: Algoritm massivni kichikroq va kichikroq bo‘laklarga bo‘lishdan boshlanadi, shunda bitta kichik massiv faqat bitta elementdan iborat bo‘ladi.
Conquer: Algoritm massivning kichik qismlarini birinchi navbatda eng past qiymatlarni qo‘yish orqali birlashtiradi, natijada tartiblangan massiv hosil bo‘ladi.
Massivni saralash uchun massivni ajratish va qurish rekursiv tarzda amalga oshiriladi.
Yuqoridagi animatsiyada har safar chiziqlar pastga surilganda massivni kichikroq bo‘laklarga bo‘ladigan rekursiv chaqiruvni ifodalaydi. Chiziqlar yuqoriga ko‘tarilganda, bu ikkita kichik massiv birlashtirilganligini anglatadi.
Birlashtirish saralash algoritmini quyidagicha tasvirlash mumkin:
Qanday ishlaydi:
- Tartibga solinmagan massivni asl nusxaning yarmiga teng ikkita kichik massivga ajrating.
- Massivning joriy qismi bir nechta elementga ega ekan, pastki massivlarni bo‘lishda davom eting.
- Har doim eng past qiymatni birinchi o‘ringa qo‘yib, ikkita kichik massivni birlashtiring.
- Hech qanday pastki massivlar qolmaguncha birlashishni davom eting.
Birlashtirish saralash boshqa nuqtai nazardan qanday ishlashini ko‘rish uchun quyidagi chizmaga qarang. Ko‘rib turganingizdek, massiv yana birlashtirilgunga qadar kichikroq va kichikroq bo‘laklarga bo‘linadi. Va birlashish sodir bo‘lganda, har bir kichik massivdagi qiymatlar taqqoslanadi, shunda eng past qiymat birinchi bo‘ladi.
Qo‘lda yugurish
Keling, Python dasturida amalda qo‘llashdan oldin Merge Sort qanday ishlashini yaxshiroq tushunish uchun saralashni qo‘lda qilishga harakat qilaylik.
1-qadam: Biz tartiblanmagan massivdan boshlaymiz va biz bilamizki, pastki massivlar faqat bitta elementdan iborat bo‘lmaguncha u yarmiga bo‘linadi. Merge Sort funksiyasi massivning har bir yarmi uchun bir martadan ikki marta o‘zini chaqiradi. Bu shuni anglatadiki, birinchi pastki massiv birinchi navbatda eng kichik bo‘laklarga bo‘linadi.
[ 12, 8, 9, 3, 11, 5, 4]
[ 12, 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8] [ 9] [ 3, 11, 5, 4]
2-qadam: Birinchi kichik massivni ajratish tugallandi va endi birlashish vaqti keldi. 8 va 9 - birlashtiriladigan birinchi ikkita element. 8 - eng past qiymat, shuning uchun birinchi birlashtirilgan pastki massivda 9 dan oldin keladi.
[ 12] [ 8, 9] [ 3, 11, 5, 4]
3-qadam: Birlashtiriladigan keyingi kichik massivlar [12] va [8, 9]. Ikkala massivdagi qiymatlar boshidan solishtiriladi. 8 12 dan kichik, shuning uchun 8 birinchi keladi va 9 ham 12 dan past.
[ 8, 9, 12] [ 3, 11, 5, 4]
4-qadam: Endi ikkinchi katta kichik massiv rekursiv bo‘linadi.
[ 8, 9, 12] [ 3, 11, 5, 4]
[ 8, 9, 12] [ 3, 11] [ 5, 4]
[ 8, 9, 12] [ 3] [ 11] [ 5, 4]
5-qadam: 3 va 11 ko‘rsatilgan tartibda qayta birlashtiriladi, chunki 3 11 dan past.
[ 8, 9, 12] [ 3, 11] [ 5, 4]
6-qadam: 5 va 4 qiymatlari bo‘lgan kichik massiv bo‘linadi, so‘ngra 4 5 dan oldin keladigan tarzda birlashtiriladi.
[ 8, 9, 12] [ 3, 11] [ 5] [ 4]
[ 8, 9, 12] [ 3, 11] [ 4, 5]
7-qadam: O‘ngdagi ikkita kichik massiv birlashtiriladi. Yangi birlashtirilgan massivda elementlarni yaratish uchun taqqoslashlar amalga oshiriladi:
- 3 4 dan past
- 4 11 dan past
- 5 11 dan past
- 11 - oxirgi qolgan qiymat
[ 8, 9, 12] [ 3, 4, 5, 11]
8-qadam: Qolgan ikkita pastki massiv birlashtiriladi. Keling, yangi birlashtirilgan va tugallangan tartiblangan massivni yaratish uchun taqqoslashlar qanday amalga oshirilishini batafsil ko‘rib chiqaylik:
3 8 dan past:
Before [ 8, 9, 12] [ 3, 4, 5, 11]
After: [ 3, 8, 9, 12] [ 4, 5, 11]
9-qadam: 4 8 dan past:
Before [ 3, 8, 9, 12] [ 4, 5, 11]
After: [ 3, 4, 8, 9, 12] [ 5, 11]
10-qadam: 5 8 dan past:
Before [ 3, 4, 8, 9, 12] [ 5, 11]
After: [ 3, 4, 5, 8, 9, 12] [ 11]
11-qadam: 8 va 9 11 dan past:
Before [ 3, 4, 5, 8, 9, 12] [ 11]
After: [ 3, 4, 5, 8, 9, 12] [ 11]
12-qadam: 11 12 dan past:
Before [ 3, 4, 5, 8, 9, 12] [ 11]
After: [ 3, 4, 5, 8, 9, 11, 12]
Saralash tugadi!
Yuqoridagi animatsiyali qadamlarni ko‘rish uchun quyidagi simulyatsiyani bajaring:
{{ x.dieNmbr }}
Python-da Merge Sort-ni qo‘llang
Birlashtirish tartiblash algoritmini amalga oshirish uchun bizga kerak:
- Saralash kerak bo‘lgan qiymatlarga ega massiv.
- Massivni olib, uni ikkiga bo‘ladigan va massivning har bir yarmi bilan o‘zini chaqiradigan funksiya, shunda massivlar rekursiv ravishda qayta-qayta bo‘linadi, toki pastki massiv faqat bitta qiymatdan iborat bo‘lguncha.
- Pastki massivlarni tartiblangan tarzda birlashtiradigan yana bir funksiya.
Olingan kod quyidagicha ko‘rinadi:
Misol
Pythonda birlashtirish tartiblash algoritmini amalga oshirish:
def mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
leftHalf = arr[:mid]
rightHalf = arr[mid:]
sortedLeft = mergeSort(leftHalf)
sortedRight = mergeSort(rightHalf)
return merge(sortedLeft, sortedRight)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
mylist = [3, 7, 6, -10, 15, 23.5, 55, -13]
mysortedlist = mergeSort(mylist)
print("Sorted array:", mysortedlist)
Misolni ishga tushirish »
6-qatorda arr[:mid] massivdan “mid” indeksidagi qiymatgacha bo‘lgan barcha qiymatlarni oladi, lekin shu jumladan emas.
7-qatorda arr[mid:] “mid” indeksidagi qiymatdan va keyingi barcha qiymatlardan boshlab massivdan barcha qiymatlarni oladi.
26-27-qatorlarda birlashmaning birinchi qismi amalga oshiriladi. Ushbu nuqtada ikkita kichik massivning qiymatlari solishtiriladi va chap pastki massiv yoki o‘ng pastki massiv bo‘sh, shuning uchun natija massivi faqat chap yoki o‘ng pastki massivning qolgan qiymatlari bilan to‘ldirilishi mumkin. Bu chiziqlar almashtirilishi mumkin va natija bir xil bo‘ladi.
Rekursiyasiz saralashni birlashtirish
Merge Sort «bo‘l va hukmronlik qil» (divide and conquer) algoritmi bo‘lgani uchun uni amalga oshirishda rekursiyadan foydalanish eng tabiiy yo‘ldir. Merge Sortning rekursiv amalga oshirilishini tushunish ham, ehtimol, osonroq va u odatda kamroq kod satrini talab qiladi.
Lekin Merge Sort rekursiyadan foydalanmasdan ham amalga oshirilishi mumkin, shuning uchun o‘zini chaqiradigan funksiya yo‘q.
Quyida rekursiyadan foydalanmaydigan Merge Sort ilovasini ko‘rib chiqing:
Misol
Rekursiyasiz birlashtirish tartibi
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def mergeSort(arr):
step = 1 # Starting with sub-arrays of length 1
length = len(arr)
while step < length:
for i in range(0, length, 2 * step):
left = arr[i:i + step]
right = arr[i + step:i + 2 * step]
merged = merge(left, right)
# Place the merged array back into the original array
for j, val in enumerate(merged):
arr[i + j] = val
step *= 2 # Double the sub-array length for the next iteration
return arr
mylist = [3, 7, 6, -10, 15, 23.5, 55, -13]
mysortedlist = mergeSort(mylist)
print(mysortedlist)
Misolni ishga tushirish »
Yuqoridagi ikkita Merge Sort ilovasida birlashma funksiyalari aynan bir xil ekanligini payqashingiz mumkin, lekin yuqoridagi dasturda rekursiyani almashtirish uchun mergeSort funksiyasi ichidagi while siklidan foydalaniladi. while sikli massivni o‘z joyida bo‘lish va birlashtirishni amalga oshiradi va bu kodni tushunishni biroz qiyinlashtiradi.
Oddiy qilib aytganda, mergeSort funksiyasi ichidagi while sikli birlashma funksiyasidan foydalangan holda dastlabki massivning kichik qismlarini (pastki massivlarni) saralash uchun qisqa qadam uzunliklaridan foydalanadi. Keyin butun massiv saralanmaguncha massivning katta qismlarini birlashtirish va saralash uchun qadam uzunligi oshiriladi.
Saralash vaqtining murakkabligini birlashtirish
Birlashtirish saralash uchun vaqt murakkabligi: \( O( n \cdot \log n ) \)
Va vaqt murakkabligi har xil turdagi massivlar uchun deyarli bir xil. Algoritm massivni ajratishi va uni tartiblanganmi yoki butunlay aralashtirilganmi, birlashtirishi kerak.
Quyidagi rasmda Birlashtirish Saralash uchun vaqt murakkabligi ko‘rsatilgan.
Birlashtirish saralash har safar deyarli bir xil ishlaydi, chunki massiv bo‘linadi va massiv allaqachon tartiblangan yoki tartiblanmagan bo‘lsa ham, taqqoslash yordamida birlashtiriladi.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!