Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: रैंडमाइजेशन का उपयोग करके क्विक सॉर्ट इम्प्लीमेंट करना


क्विकसॉर्ट तकनीक लिस्ट को दो भागों में अलग करके की जाती है। प्रारंभ में पार्टीशनिंग एल्गोरिदम द्वारा एक पिवट एलिमेंट चुना जाता है। पिवट का बायां भाग पिवट से छोटे मान रखता है, और दायां भाग बड़ा मान रखता है। पार्टीशनिंग के बाद, प्रत्येक अलग लिस्ट को उसी प्रक्रिया का उपयोग करके पार्टीशन किया जाता है।

इस मामले में हम पिवट एलिमेंट को रैंडमली चुन रहे हैं। पिवट चुनने के बाद, हम पार्टीशनिंग कर रहे हैं, फिर ऐरे को रिकर्सिवली सॉर्ट कर रहे हैं।

क्विकसॉर्ट तकनीक की जटिलता

  • टाइम कॉम्प्लेक्सिटी - बेस्ट केस और एवरेज केस के लिए O(n log n), वर्स्ट केस के लिए O(n²)।

  • स्पेस कॉम्प्लेक्सिटी - O(log n)

इनपुट - अनसॉर्टेड लिस्ट: 90 45 22 11 22 50
आउटपुट - सॉर्टिंग के बाद ऐरे: 11 22 22 45 50 90

एल्गोरिदम

partition(array, lower, upper)

इनपुट - डेटा सेट ऐरे, लोअर बाउंडरी और अपर बाउंडरी

आउटपुट - सही पोजीशन में पिवट

Begin
    index := lower
    pivot := higher
    i को lower से higher की रेंज में, करें
        यदि array[i] < array[pivot], तो
            array[i] और array[index] के मान एक्सचेंज करें
            index := index + 1
    किया
    array[pivot] और array[index] के मान एक्सचेंज करें
End

random_pivot_partition(array, lower, upper)

इनपुट - डेटा सेट ऐरे, लोअर बाउंडरी और अपर बाउंडरी

आउटपुट - रैंडमली चुने गए पिवट का अंतिम इंडेक्स

Begin
    n := एक रैंडम नंबर
    pvt := lower + n mod (upper - lower + 1)
    array[pivot] और array[upper] के मान एक्सचेंज करें
    index := Partition(array, lower, upper)
    index लौटाएं
End

quickSort(array, left, right)

इनपुट - डेटा का एक ऐरे, और ऐरे की लोअर और अपर बाउंड

आउटपुट - सॉर्टेड ऐरे

Begin
    यदि lower < right तो
        q = random_pivot_partition(array, left, right).
        quickSort(array, left, q-1)
        quickSort(array, q+1, right)
End

उदाहरण कोड

#include <iostream>
#include <cstdlib>
#include <ctime>
#define MAX 100
using namespace std;

void random_shuffle(int arr[]) {
    // ऐरे एलिमेंट्स को रैंडम पोजीशन में शफल करने का फंक्शन
    srand(time(NULL));
    for (int i = MAX - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

// हाई पर पिवट वैल्यू के आधार पर ऐरे को पार्टीशन करना।
int Partition(int a[], int low, int high) {
    int pivot, index, i;
    index = low;
    pivot = high;
    for (i = low; i < high; i++) {
        // पिवट का इंडेक्स ढूंढना।
        if (a[i] < a[pivot]) {
            swap(a[i], a[index]);
            index++;
        }
    }
    swap(a[pivot], a[index]);
    return index;
}

int RandomPivotPartition(int a[], int low, int high) {
    // पिवट का रैंडम चयन।
    int pvt, n, temp;
    n = rand();
    pvt = low + n % (high - low + 1); // सब-ऐरे से पिवट वैल्यू रैंडमाइज़ करना।
    swap(a[high], a[pvt]);
    return Partition(a, low, high);
}

void quick_sort(int arr[], int p, int q) {
    // रिकर्सिवली लिस्ट सॉर्ट करें
    int pindex;
    if (p < q) {
        pindex = RandomPivotPartition(arr, p, q); // रैंडमली पिवट चुनें
        // क्विकसॉर्ट रिकर्सिवली इम्प्लीमेंट करना।
        quick_sort(arr, p, pindex - 1);
        quick_sort(arr, pindex + 1, q);
    }
}

int main() {
    int i;
    int arr[MAX];
    for (i = 0; i < MAX; i++)
        arr[i] = i + 1;
    random_shuffle(arr); // ऐरे को रैंडमाइज करें
    quick_sort(arr, 0, MAX - 1); // ऐरे के एलिमेंट्स सॉर्ट करें
    for (i = 0; i < MAX; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

आउटपुट

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

  1. - दिए गए जटिलता प्रतिबंध के साथ क्विक सॉर्ट लागू करने के लिए C++ प्रोग्राम

    क्विक सॉर्ट डिवाइड-एंड-कंकर पर आधारित है। इस एल्गोरिदम की औसत समय जटिलता O(n log n) है लेकिन सबसे खराब स्थिति की जटिलता O(n^2) है। सबसे खराब स्थिति की संभावना को कम करने के लिए यहां क्विकसॉर्ट को रैंडमाइजेशन का उपयोग करके लागू किया गया है। एल्गोरिदम partition(int a[], int l,int h) शुरुआत   &nbs

  1. - C++ प्रोग्राम: ऐरे का उपयोग करके स्टैक कार्यान्वयन

    ऐरे आधारित स्टैक निश्चित आकार की सरणी और top सूचकांक का उपयोग करके स्टैक कार्यान्वयन। LIFO सिद्धांत का पालन करता है। C++ प्रोग्राम उदाहरण = MAX - 1) cout << Stack Overflow << endl; else { top++; stack[top] = val; } } void pop() { if (top = 0; i--)

  1. - C++ में हीप सॉर्ट एल्गोरिदम का उपयोग करके 10 तत्वों की सरणी को सॉर्ट करने का प्रोग्राम

    हीप सॉर्ट बाइनरी हीप डेटा संरचना पर आधारित है। बाइनरी हीप में, मैक्स हीप के मामले में पैरेंट नोड के चाइल्ड नोड्स उससे छोटे या बराबर होते हैं, और मिन हीप के मामले में चाइल्ड नोड्स पैरेंट से बड़े या बराबर होते हैं। हीप सॉर्ट के सभी चरणों को समझाने वाला एक उदाहरण निम्नलिखित है। सॉर्टिंग से पहले 10 तत्व