Showing posts with label Merge Sort Algorithm. Show all posts
Showing posts with label Merge Sort Algorithm. Show all posts

Saturday, May 9, 2020

Merge Sort Algorithm In HIndi And Its Examples

This chapter Will help you to learn about Merge Sort Algorithm In HIndi And Its Examples and also help to understand the time complexity for mearge sort


Merge Sort Algorithm In HIndi And Its Examples
Merge Sort Algorithm In HIndi And Its Examples

 
Merge Sort एक Devide And Conqure Algorithm है जो एक सूची को कई उप-सूचियों में तोड़ने के विचार के आधार पर है, जब तक कि प्रत्येक सबलिस्ट में एक एकल तत्व न हो और उन सब्लिस्ट्स को एक तरीके से मर्ज करें जो एक क्रमबद्ध सूची में परिणाम करता है।

विचार:
  •     N Sublist में अनसोल्ड लिस्ट को डिवाइड करें, प्रत्येक में 1 एलिमेंट हो।
  •     दो सिंगलटन सूचियों के आसन्न जोड़े लें और उन्हें 2 तत्वों की सूची बनाने के लिए मर्ज करें। N अब N / 2 आकार 2 की सूची में बदल जाएगा।
  •     प्राप्त की गई एकल सॉर्ट की गई सूची तक प्रक्रिया को दोहराएं।

विलय के लिए दो उपविदों की तुलना करते समय, दोनों सूचियों के पहले तत्व को ध्यान में रखा जाता है। आरोही क्रम में छंटनी करते समय, जो तत्व कम मूल्य का होता है, वह क्रमबद्ध सूची का एक नया तत्व बन जाता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि दोनों छोटे सब्लिस्ट खाली न हों और नई संयुक्त सबलिस्ट में दोनों सब्लिस्ट के सभी तत्व शामिल हों।



"Merge Sort Algorithm And Its Examples"
Merge Sort Algorithm And Its Examples


जैसा कि ऊपर की छवि से कोई भी समझ सकता है, प्रत्येक चरण में आकार M की एक सूची को आकार M / 2 के 2 उपविभाजकों में विभाजित किया जा रहा है, जब तक कि कोई और विभाजन नहीं किया जा सकता। बेहतर समझने के लिए, तत्वों (9,7,8) वाले छोटे सरणी A पर विचार करें।

पहले चरण में आकार 3 की इस सूची को 2 उपविभागों में विभाजित किया गया है जिसमें पहले तत्व (9,7) और दूसरा एक (8) है। अब, तत्वों (9,7) से मिलकर पहली सूची को क्रमशः तत्वों (9) और (7) से मिलकर 2 उप-विभाजकों में विभाजित किया गया है।

चूंकि इस सूची का कोई और टूटना नहीं हो सकता है, क्योंकि प्रत्येक सबलिस्ट में अधिकतम 1 तत्व होता है, अब हम इन सूचियों को मर्ज करना शुरू करते हैं। अंतिम चरण में गठित 2 उप-सूचियों को फिर एक नई सूची (7,9) के लिए ऊपर उल्लिखित प्रक्रिया का उपयोग करके क्रमबद्ध क्रम में एक साथ विलय कर दिया जाता है। फिर से आगे पीछे करते हुए, हमें फिर इस सूची के साथ तत्व (8) से मिलकर सूची को मर्ज करने की आवश्यकता है, जिससे नई छंटनी सूची (7,8,9) हो सके।


Merge Sort Algorithm Program

 void merge(int A[ ] , int start, int mid, int end) {
 //stores the starting position of both parts in temporary variables.
int p = start ,q = mid+1;

int Arr[end-start+1] , k=0;

for(int i = start ;i <= end ;i++) {
    if(p > mid)      //checks if first part comes to an end or not .
       Arr[ k++ ] = A[ q++] ;

   else if ( q > end)   //checks if second part comes to an end or not
       Arr[ k++ ] = A[ p++ ];

   else if( A[ p ] < A[ q ])     //checks which part has smaller element.
      Arr[ k++ ] = A[ p++ ];

   else
      Arr[ k++ ] = A[ q++];
 }
  for (int p=0 ; p< k ;p ++) {
   /* Now the real array has elements in sorted manner including both 
        parts.*/
     A[ start++ ] = Arr[ p ] ;                          
  }
}

यहां, Merge Funcation में, हम एरे के दो भागों को मर्ज करेंगे, जहां एक भाग में शुरुआत से लेकर क्रमशः मध्य तक और अंत में स्थितियां हैं और दूसरे भाग में mid + 1 से अंत तक स्थितियां हैं।

एक शुरुआत दोनों सरणियों के शुरुआती हिस्सों से की जाती है। यानी पी और क्यू। फिर दोनों हिस्सों के संबंधित तत्वों की तुलना की जाती है और छोटे मूल्य वाले एक को सहायक सरणी (Arr []) में संग्रहीत किया जाएगा। यदि किसी स्थिति में, एक भाग समाप्त होता है, तो सरणी के दूसरे भाग के सभी तत्व सहायक सरणी में उसी क्रम में जुड़ जाते हैं, जिस क्रम में वे मौजूद हैं। 

Merge Sort Algorithm Program

   void merge_sort (int A[ ] , int start , int end )
   {
           if( start < end ) {
           int mid = (start + end ) / 2 ;           // defines the current array in 2 parts .
           merge_sort (A, start , mid ) ;                 // sort the 1st part of array .
           merge_sort (A,mid+1 , end ) ;              // sort the 2nd part of array.

         // merge the both parts by comparing elements of both the parts.
          merge(A,start , mid , end );   
   }                    
}

Time Complexity Merge Sort Algorithm in hindi

list of size N is devided into max of logN and mergin sublist after sorted take O(N) Time. Worst case algorithm time for merge sort is O(N logN)

Merge Sort Algorithm Program In C/C-PLUS

*/ C program for Merge Sort */
#include 
#include 
  
// Merges two subarrays of arr[]. 
// First subarray is arr[l..m] 
// Second subarray is arr[m+1..r] 
void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
  
    /* create temp arrays */
    int L[n1], R[n2]; 
  
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 
  
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray 
    j = 0; // Initial index of second subarray 
    k = l; // Initial index of merged subarray 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    /* Copy the remaining elements of L[], if there 
       are any */
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    /* Copy the remaining elements of R[], if there 
       are any */
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
  
/* l is for left index and r is right index of the 
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
        // Same as (l+r)/2, but avoids overflow for 
        // large l and h 
        int m = l+(r-l)/2; 
  
        // Sort first and second halves 
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 
  
        merge(arr, l, m, r); 
    } 
} 
  
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", A[i]); 
    printf("\n"); 
} 
  
/* Driver program to test above functions */
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
  
    printf("Given array is \n"); 
    printArray(arr, arr_size); 
  
    mergeSort(arr, 0, arr_size - 1); 
  
    printf("\nSorted array is \n"); 
    printArray(arr, arr_size); 
    return 0; 
} 

Merge Sort Algorithm Program In JAVA


/* Java program for Merge Sort */
class MergeSort 
{ 
    // Merges two subarrays of arr[]. 
    // First subarray is arr[l..m] 
    // Second subarray is arr[m+1..r] 
    void merge(int arr[], int l, int m, int r) 
    { 
        // Find sizes of two subarrays to be merged 
        int n1 = m - l + 1; 
        int n2 = r - m; 
  
        /* Create temp arrays */
        int L[] = new int [n1]; 
        int R[] = new int [n2]; 
  
        /*Copy data to temp arrays*/
        for (int i=0; i

Merge Sort Algorithm Program In Python

# Python program for implementation of MergeSort 
def mergeSort(arr): 
    if len(arr) >1: 
        mid = len(arr)//2 #Finding the mid of the array 
        L = arr[:mid] # Dividing the array elements  
        R = arr[mid:] # into 2 halves 
  
        mergeSort(L) # Sorting the first half 
        mergeSort(R) # Sorting the second half 
  
        i = j = k = 0
          
        # Copy data to temp arrays L[] and R[] 
        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
          
        # Checking if any element was left 
        while i < len(L): 
            arr[k] = L[i] 
            i+=1
            k+=1
          
        while j < len(R): 
            arr[k] = R[j] 
            j+=1
            k+=1
  
# Code to print the list 
def printList(arr): 
    for i in range(len(arr)):         
        print(arr[i],end=" ") 
    print() 
  
# driver code to test the above code 
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) 

Sorting Algorithm : - 

Bubble Sort Algorithm And sorting program in different language

bucket sort Algorithm In Hindi And Its Examples

Counting sort Algorithm in hindi and Its Example 

Heap Sort Algorithm In Hindi and its examples 

Insertion sort Algorithm And Its Examples

Quick Sort Algorithm And Its Examples in hindi

Selection sort algorithm And Its Examples