MERGE SORT
Merge Sort, o'z vaqtida qatorni bo'lib bo'lingan algoritmdir. Bu algoritm yordamida katta muammolar to'plami qismlarga bo'lingan va keyin ulardan iborat bo'lgan ro'yxatlar to'plamini bir-biriga qo'shish jarayoni orqali tartiblangan. Merge Sortning harakatlar ketma-ketligi quyidagicha bo'ladi:
1. Agar ro'yxat bir elementdan iborat bo'lsa, uni to'xtatamiz, chunki u avvaldan tartiblangan hisoblanadi.
2. Aksincha, ro'yxatni ikki yarimka bo'ladi. Bu yarimkalarga ro'yxatning o'rtasini topish uchun indekslar kerak bo'ladi.
3. Birinchi yarimkada Merge Sortni qo'llaymiz.
4. Ikkinchi yarimkada ham Merge Sortni qo'llaymiz.
5. Har ikki yarimka ham tartiblangan bo'lganda, ularni birlashtirish jarayoniga kirib kelamiz. Birlashtirish jarayonida, ikki yarimka o'rtasidagi elementlarni solishtirib, ularni tartiblangan ro'yxatga joylashtiramiz.
6. Birlashtirish jarayonini davom ettirib, barcha yarimkalarni birlashtirib boramiz.
def mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = mergeSort(left_half)
right_half = mergeSort(right_half)
return merge(left_half, right_half)
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
while i < len(left):
result.append(left[i])
i += 1
while j < len(right):
result.append(right[j])
j += 1
return result
arr = [4, 2, 7, 1, 3]
sorted_arr = mergeSort(arr)
print(sorted_arr)
Ushbu kod Merge Sortni amalga oshiradi va natijadagi tartiblangan ro'yxatni chiqaradi. Kod esa "arr" nomli ro'yxatni o'zgartirib natijani ekranga chiqaradi.
QUICK SORT
Tez saralash - umuman olganda, bu massivlarni tartiblash uchun eng tezkor algoritmlardan biridir, ammo amalda ko'pincha turli xil o'zgartirishlar bilan qo'llaniladi. Bu "bo'linish va zabt etish" tamoyiliga misol.
Algoritmning g'oyasi shundaki, saralash amalga oshiriladigan qo'llab-quvvatlovchi element tanlangan. Teng va kattaroq elementlar o'ngga, kichikroq - chap tomonga joylashtirilgan. Keyin, dastlabki ikki nuqta rekursiv ravishda natijada paydo bo'lgan subarraysiyalarga qo'llaniladi.
|
