Marge sort (Qo'shib saralash) algoritmi 202-guruh kidt talabasi

Marge sort (Qo'shib saralash) algoritmi

202-guruh KIDT talabasi

Shoxnoza Jumaboyeva

Ushbu usul juda oddiy qo'shish amaliga asoslanib, ikkita tartiblangan massivlami bitta yagona tartiblangan massiv ko‘rinishida tasvirlaydi. Ushbu amal qo‘shish usulida saralash nomli saralashning oddiy rekursiv metodiga olib kelib, saralash uchun massivni teng ikkiga bo‘lib, hosil bo'lgan yarimtaliklarni (rekursiv) saralashva natijalami qo‘shish kerak bo‘ladi. 

Qo'shish usulida saralashning eng qiziq tomoni shundan iboratki, N elementdan iborat ixtiyoriy massivni NlogN prorotsional garantirlangan vaqtda saralashidir.Joylashtirish usulida saralashning turlaridan biri fon Neyman usuli hisoblanadi. Ushbu masalani yechish algoritmi “fon Neyman saralash usuli” nomi bilan tanilgan yoki qo'shib saralash usuli deb nomlanadi.

Ushbu usul quyidagidan iborat: avval ikkala massivning birinchi elementlari tahlil qilinadi. Eng kichik element yangi massivga yozilib boriladi. Ketma-ketlikning qolgan elementlari boshqa massiv elementlari bilan taqqoslanadi. Har bir taqqoslashdan keyin yangi massivga eng kichik element borib tushadi. Jarayon massivlaming birida elementlaming kamayishigacha davom etadi. Shundan so‘ng, boshqa massivning qoldig'i yangi massivga voziladi.

Hosil qilingan yangi massiv dastlabki massiv singari shu usulda tartiblangan bo‘ladi.Ikkita o‘sish tartibida tartiblangan p[ 1], p[2],„.,p[n] va q[l], ij[2],...,

U holda keyingi qadamda p[2] va

# Python program for implementation of MergeSort def mergeSort(arr): if len(arr) > 1: mid = len(arr)//2 # Dividing the array elements L = arr[:mid] R = arr[mid:] mergeSort(L) i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1

while i < len(L):

arr[k] = L[i]

i += 1

k += 1

while j < len(R):

arr[k] = R[j]

j += 1

k += 1

def printList(arr):

for i in range(len(arr)):

print(arr[i], end=" ")

print()

if __name__ == '__main__':

arr = [12, 11, 13, 5, 6, 7]

print("Given array is", end="\n")

printList(arr)

mergeSort(arr)

print("Sorted array is: ", end="\n")

printList(arr)

Python code

Python code

E'TIBORINGIZ UCHUN RAXMAT

202-KIDT talabasi

Shoxnoza Jumaboyeva