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

C++ प्रोग्राम: बड़ी संख्या में एलिमेंट्स पर क्विक सॉर्ट करना


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

यहां हम लगभग 100 एलिमेंट्स के एक बड़े ऐरे को सॉर्ट करने पर विचार कर रहे हैं। हम कुछ नंबर ले रहे हैं फिर उन्हें रैंडमाइज्ड ऑर्डर में शफल कर रहे हैं ताकि वे अनसॉर्टेड हो जाएं। फिर क्विकसॉर्ट तकनीक का उपयोग करके सॉर्ट करें।

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

  • टाइम कॉम्प्लेक्सिटी - बेस्ट केस और एवरेज केस के लिए 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
    pivot := array[upper]
    i := lower - 1
    j को lower से higher की रेंज में, करें
        यदि array[j] < pivot, तो
            array[i] और array[j] के मान एक्सचेंज करें
            i := i + 1
    किया
    array[upper] और array[i + 1] के मान एक्सचेंज करें
    i + 1 लौटाएं
End

quickSort(array, left, right)

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

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

Begin
    यदि lower < right तो
        q = 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 partion(int arr[], int p, int r) {
    int pivot = arr[r]; // लास्ट आइटम को पिवट के रूप में
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[r]);
    return i + 1;
}

void quick_sort(int arr[], int p, int q) { // रिकर्सिवली लिस्ट सॉर्ट करें
    int j;
    if (p < q) {
        j = partion(arr, p, q);
        quick_sort(arr, p, j - 1);
        quick_sort(arr, j + 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++ प्रोग्राम में बड़ी संख्याओं के लिए 37 से विभाज्यता

    इस ट्यूटोरियल में, हम एक प्रोग्राम लिखेंगे जो जांचता है कि दी गई बड़ी संख्या 37 से विभाज्य है या नहीं।हम यहां थोड़ी गणित का उपयोग करने जा रहे हैं। समस्या को हल करने के चरण देखते हैं।संख्या को इनिशियलाइज़ करें।यदि दी गई संख्या की लंबाई 3 से विभाज्य नहीं है, तो संख्या की शुरुआत में शून्य जोड़ें ताकि ल

  1. - C++ प्रोग्राम में बड़ी संख्या के लिए 12 से विभाज्यता

    इस ट्यूटोरियल में, हम एक प्रोग्राम लिखेंगे जो जांचता है कि स्ट्रिंग फॉर्मेट में दी गई बड़ी संख्या 12 से विभाज्य है या नहीं।हम इस समस्या को हल करने के लिए थोड़ी गणित का उपयोग करने जा रहे हैं। यदि संख्या 3 और 4 से विभाज्य है, तो संख्या 12 से विभाज्य होगी।एक संख्या 3 से विभाज्य होती है यदि उसके अंकों क

  1. C++ में सरणी के एलिमेंट्स का गुणनफल C++ में सरणी के एलिमेंट्स का गुणनफल

    पूर्णांक एलिमेंट्स की एक सरणी दी गई है और कार्य सरणी के एलिमेंट्स को गुणा करना और प्रदर्शित करना है। उदाहरण इनपुट-: arr[]={1,2,3,4,5,6,7} आउटपुट-: 1 x 2 x 3 x 4 x 5 x 6 x 7 = 5040 इनपुट-: arr[]={3, 4,6, 2, 7, 8, 4} आउटपुट-: 3 x 4 x 6 x 2 x 7 x 8 x 4 = 32256 नीचे दिए गए प्रोग्राम में उपयोग किया गया द