पायथन प्रोग्राम: पुनरावर्ती मर्ज सॉर्ट

इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे।

समस्या कथन

हमें एक सरणी दी गई है, हमें पुनरावृत्ति द्वारा मर्ज सॉर्ट की अवधारणा का उपयोग करके इसे क्रमबद्ध करना है।

यहां हम अधिकतम तत्व को अंत में रखते हैं। यह तब तक दोहराया जाता है जब तक सरणी क्रमबद्ध नहीं हो जाती।

उदाहरण

# पुनरावर्ती तरीका
def mergeSort(a):
    current_size = 1
    # सबएरे ट्रैवर्स करना
    while current_size < len(a) - 1:
        left = 0
        # क्रमबद्ध किया जा रहा सबएरे
        while left < len(a)-1:
            # मध्य मान की गणना
            mid = left + current_size - 1
            # current_size
            right = min((2 * current_size + left - 1), len(a) - 1)
            # मर्ज
            merge(a, left, mid, right)
            left = left + current_size * 2
        # सबएरे आकार बढ़ाना
        current_size = 2 * current_size

# मर्ज
def merge(a, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = a[l + i]
    for i in range(0, n2):
        R[i] = a[m + i + 1]
    i, j, k = 0, 0, l
    while i < n1 and j < n2:
        if L[i] > R[j]:
            a[k] = R[j]
            j += 1
        else:
            a[k] = L[i]
            i += 1
        k += 1
    while i < n1:
        a[k] = L[i]
        i += 1
        k += 1
    while j < n2:
        a[k] = R[j]
        j += 1
        k += 1

# ड्राइवर कोड
a = [2, 5, 3, 8, 6, 5, 4, 7]
mergeSort(a)
print("Sorted array is:")
for i in range(len(a)):
    print(a[i], end=" ")

आउटपुट

Sorted array is: 2 3 4 5 5 6 7 8

निष्कर्ष

इस लेख में हमने पुनरावर्ती मर्ज सॉर्ट के पायथन प्रोग्राम के बारे में सीखा।