हाइब्रिड मर्ज / सम्मिलन सॉर्ट एल्गोरिथ्म

Question

स्पष्टीकरण: हालांकि मर्ज सॉर्ट ation (nlgn) और प्रविष्टि सॉर्ट रन mer (n ^ 2) में चलता है, प्रविष्टि सॉर्ट में लगातार कारक इसे छोटी समस्या आकार के लिए कार्यान्वयन में तेज बना सकते हैं। यह सॉर्टिंग कार्यान्वयन अभी भी स्थिर होना चाहिए।

पुनरावर्ती विलय सॉर्ट सबरूटीन विधि:

private static void recursiveMergeSort(double[] arr, int lowerBound, int upperBound) {
    if (lowerBound < upperBound) {
        // Split the sub array into halves
        int mid = lowerBound + (upperBound - lowerBound) / 2;
        recursiveMergeSort(arr, lowerBound, mid);
        recursiveMergeSort(arr, mid + 1, upperBound);
        merge(arr, lowerBound, mid, upperBound);
    }
}

मर्ज विधि: * नोट- मैं लूप के साथ और यदि-और स्टेटमेंट्स को बदलना चाहूंगा।

private static void merge(double[] arr, int left, int mid, int right) {
    int i = 0, j = 0, k = left;
    //System.out.println("used merge");

    // Sizes of the temporary arrays to be copied
    int n1 = (mid - left) + 1;
    int n2 = (right - mid);

    // Create temporary arrays and copy data
    double[] leftTemp = Arrays.copyOfRange(arr, left, mid + 1);
    double[] rightTemp = Arrays.copyOfRange(arr, mid + 1, right + 1);

    // Merge the temp arrays back into arr[left...right]
    while (i < n1 && j < n2) {
        if (leftTemp[i] <= rightTemp[j]) {
            arr[k++] = leftTemp[i++];
        } else {
            arr[k++] = rightTemp[j++];
        }
    }

    // Copy remaining elements, if any
    while (i < n1) {
        arr[k++] = leftTemp[i++];
    }
    while (j < n2) {
        arr[k++] = rightTemp[j++];
    }
}

सम्मिलन सॉर्ट सबरूटीन विधि:

private static void insertionSort(double[] arr, int left, int right){
    for (int i = left + 1; i <= right; i++) {
        double key = arr[i];
        int j = i - 1;

        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

हाइब्रिड मर्ज / सम्मिलन छँटाई विधि:

ऑप्टिमाइज़्ड एक ऐसा मूल्य है जो [25,100] के बीच सबसे अच्छा सेट है

private static void insertionRecursiveMergeSort(double[] arr, int left, int right) {
    // If <= OPTIMIZED use insertion sort subroutine
    if (right <= left + OPTIMIZED - 1) {
        insertionSort(arr, left, right);
    } else {
        int mid = left + (right - left) / 2;
        insertionRecursiveMergeSort(arr, left, mid);
        insertionRecursiveMergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

टेस्ट रन के लिए, मैंने 25, 50, 100, और 125 के अनुकूलित सेट के साथ सरणी आकार 1M, 2M, 3M और 5M का उपयोग किया।

Answer 1

अनुकूलन नोट।

• अस्थायी सरणी को एक बार आवंटित करें, और इसे पुनरावर्ती चालान में पास करें।

• तुरंत सम्मिलन प्रकार पर वापस न जाएं। इसे तब तक के लिए स्थगित करें जब तक कि सभी पुनरावृत्ति पूर्ण न हो जाएं, और सम्मिलन पूरे सरणी को एक बार क्रमबद्ध करता है।

  यह संपूर्ण सरणी को सम्मिलित करने के लिए डरावना लगता है। यह करने के लिए प्रदर्शन नीचा नहीं होगा \$O(n^2)\$? जवाब न है। सरणी पहले से ही "लगभग क्रमबद्ध" है: प्रत्येक तत्व OPTIMIZEDअपने अंतिम गंतव्य से सबसे दूर है। इसलिए, एक आंतरिक लूप OPTIMIZEDप्रति तत्व अधिकांश पुनरावृत्तियों पर करता है , और समग्र जटिलता \ _ है $O(n * \texttt{OPTIMIZED})\$। यह अवलोकन भी संकेत करता है कि \ "कीOPTIMIZED बॉलपार्क में होना चाहिए $\log n\$।

  संपादित करें : मुझे नहीं पता कि मैं क्या सोच रहा था। ऊपर पूरी तरह से गलत है (यह quicksort के लिए मान्य है, लेकिन यहाँ नहीं), अवलोकन है कि सिवाय OPTIMIZEDके बॉलपार्क में होना चाहिए \$\log n\$।

• एक अल्पज्ञात चाल, सम्मिलन प्रकार की तुलना की संख्या को आधे में कटौती करने की अनुमति देती है। के बजाय

    while (j >= left && arr[j] > key)
  

  पहली तुलना keyकरने पर विचार करें arr[left]:

    if (key < arr[left]) {
        // The key shall land at the left. No need to compare values anymore
        for (j = i; j > 0; j--) {
            arr[j] = arr[j-1];
        }
    } else {
        // arr[left] is a natural sentinel. No need to compare indices anymore
        for (j = i; arr[j] > key; j--) {
            arr[j] = arr[j-1];
        }
    }
  

  अब यदि आप एक स्थगित प्रविष्टि प्रकार का विकल्प चुनते हैं, तो इसे और भी अधिक अनुकूलित किया जा सकता है: पहले OPTIMIZEDतत्वों के बीच न्यूनतम ढूंढें और इसके साथ स्वैप करें arr[0]। अब इसके लिए परीक्षण करने की आवश्यकता नहीं है key < arr[left]- यह विफल होने की गारंटी है। बिना छेड़े लूप में सीधे जाएं।