ವಿಷಯಕ್ಕೆ ಹೋಗು

ಮರ್ಜ್ ಸಾರ್ಟ್ (ವಿಲೀನ ವಿಂಗಡಣೆ)

ವಿಕಿಪೀಡಿಯದಿಂದ, ಇದು ಮುಕ್ತ ಹಾಗೂ ಸ್ವತಂತ್ರ ವಿಶ್ವಕೋಶ
ಮರ್ಜ್ ಸಾರ್ಟ್
An example of merge sort. First, divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally, all the elements are sorted and merged.
ಕ್ಲಾಸ್{{{class}}}
ಡೇಟಾ ರಚನೆ{{{data}}}
ಪ್ರತಿಕೂಲ ಸ್ಥಿತಿ ವಿಶ್ಲೇಷಣೆ{{{time}}}
ಕೆಟ್ಟ-ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆ{{{space}}}

ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಮರ್ಜ್ ಸಾರ್ಟ್ (ಸಾಮಾನ್ಯವಾಗಿ ವಿಲೀನಗೊಳಿಸುವಿಕೆ ಎಂದು ಸಹ ಉಚ್ಚರಿಸಲಾಗುತ್ತದೆ) ಒಂದು ಸಮರ್ಥ, ಸಾಮಾನ್ಯ-ಉದ್ದೇಶ ಮತ್ತು ಹೋಲಿಕೆ-ಆಧಾರಿತ ವಿಂಗಡಣೆ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಹೆಚ್ಚಿನ ಅನುಷ್ಠಾನಗಳು ಸ್ಥಿರವಾದ ವಿಂಗಡಣೆ (ಸ್ಟೇಬಲ್ ಸಾರ್ಟ್) ಯನ್ನು ಉತ್ಪಾದಿಸುತ್ತವೆ. ಅಂದರೆ ಸಮಾನ ಎಲಿಮೆಂಟ್ ಗಳ ಸಾಪೇಕ್ಷ ಕ್ರಮವು ಇನ್‌ಪುಟ್ ಮತ್ತು ಔಟ್‌ಪುಟ್‌ನಲ್ಲಿ ಒಂದೇ ಆಗಿರುತ್ತದೆ. ವಿಲೀನ ವಿಂಗಡಣೆಯು ವಿಭಜಿತ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳುವ (ಡಿವೈಡ್ ಅಂಡ್ ಕಾನ್ಕರ್) ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಇದನ್ನು 1945 ರಲ್ಲಿ ಜಾನ್ ವಾನ್ ನ್ಯೂಮನ್ ಕಂಡುಹಿಡಿದನು [] 1948 ರ ಹಿಂದೆಯೇ ಗೋಲ್ಡ್‌ಸ್ಟೈನ್ ಮತ್ತು ವಾನ್ ನ್ಯೂಮನ್‌ರ ವರದಿಯಲ್ಲಿ ಬಾಟಮ್-ಅಪ್ ವಿಲೀನ ರೀತಿಯ ವಿವರವಾದ ವಿವರಣೆ ಮತ್ತು ವಿಶ್ಲೇಷಣೆ ಕಾಣಿಸಿಕೊಂಡಿತು []

ಅಲ್ಗಾರಿದಮ್

[ಬದಲಾಯಿಸಿ]

ಕಲ್ಪನಾತ್ಮಕವಾಗಿ, ಮರ್ಜ್ ಸಾರ್ಟ್ ಈ ಕೆಳಗಿನಂತೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ:

  1. ವಿಂಗಡಿಸದ ಅರ್ರೆಯನ್ನು n ಸಬ್ ಅರ್ರೆ ಗಳಾಗಿ ವಿಂಗಡಿಸಿ, ಪ್ರತಿಯೊಂದೂ ಒಂದು ಎಲಿಮೆಂಟನ್ನು ಹೊಂದಿರುತ್ತದೆ (ಒಂದು ಎಲಿಮೆಂಟಿನ ಅರ್ರೆಯನ್ನು ವಿಂಗಡಿಸಲಾಗಿದೆ ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ).
  2. ಒಂದೇ ಒಂದು ಸಬ್ ಅರ್ರೆಯನ್ನು ಉಳಿದಿರುವವರೆಗೆ ಹೊಸ ವಿಂಗಡಿಸಲಾದ ಸಬ್ ಅರ್ರೆಗಳನ್ನು ಉತ್ಪಾದಿಸಲು ಸಬ್ ಅರ್ರೆಗಳನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ವಿಲೀನಗೊಳಿಸಿ . ಇದು ವಿಂಗಡಿಸಲಾದ ಅರ್ರೆಯಾಗಿರುತ್ತದೆ.

ಟಾಪ್-ಡೌನ್ ಅನುಷ್ಠಾನ

[ಬದಲಾಯಿಸಿ]
// Array A[] has the items to sort; array B[] is a work array.
void TopDownMergeSort(A[], B[], n)
{
    CopyArray(A, 0, n, B);           // one time copy of A[] to B[]
    TopDownSplitMerge(A, 0, n, B);   // sort data from B[] into A[]
}

// Split A[] into 2 runs, sort both runs into B[], merge both runs from B[] to A[]
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
void TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
    if (iEnd - iBegin <= 1)                     // if run size == 1
        return;                                 //   consider it sorted
    // split the run longer than 1 item into halves
    iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
    // recursively sort both runs from array A[] into B[]
    TopDownSplitMerge(A, iBegin,  iMiddle, B);  // sort the left  run
    TopDownSplitMerge(A, iMiddle,    iEnd, B);  // sort the right run
    // merge the resulting runs from array B[] into A[]
    TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}

//  Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1   ].
// Result is            B[ iBegin:iEnd-1   ].
void TopDownMerge(B[], iBegin, iMiddle, iEnd, A[])
{
    i = iBegin, j = iMiddle;
 
    // While there are elements in the left or right runs...
    for (k = iBegin; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;
        }
    }
}

void CopyArray(A[], iBegin, iEnd, B[])
{
    for (k = iBegin; k < iEnd; k++)
        B[k] = A[k];
}

ಸಂಪೂರ್ಣ ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸುವ ಮೂಲಕ ಸಾಧಿಸಲಾಗುತ್ತದೆ  .

ತಳಮಟ್ಟದ (ಬಾಟಮ್ ಅಪ್) ಅನುಷ್ಠಾನ

[ಬದಲಾಯಿಸಿ]
  1. Knuth (1998)
  2. . Rome. March 1997. pp. 217–228. {{cite conference}}: Missing or empty |title= (help)