क्विक सॉर्ट

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

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

• टाइम कॉम्प्लेक्सिटी: बेस्ट और औसत केस के लिए O(n log n), सबसे खराब केस के लिए O(n^2)।
• स्पेस कॉम्प्लेक्सिटी: O(log n)

इनपुट और आउटपुट

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

एल्गोरिदम

partition(array, lower, upper)

इनपुट: डेटासेट ऐरे, निचली सीमा और ऊपरी सीमा

आउटपुट: सही स्थिति में पिवट

Begin
    pivot := array[lower]
    start := lower and end := upper
    while start < end do
        while array[start] <= pivot AND start < end do
            start := start + 1
        done
        while array[end] > pivot do
            end := end - 1
        done
        if start < end then
            swap array[start] with array[end]
        done
    array[lower] := array[end]
    array[end] := pivot
    return end
End

quickSort(array, left, right)

इनपुट: डेटा का एक ऐरे, और ऐरे की निचली और ऊपरी सीमा

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

Begin
    if left < right then
        q = partition(array, left, right)
        quickSort(array, left, q-1)
        quickSort(array, q+1, right)
End

उदाहरण

#include <iostream>
using namespace std;

void swapping(int &a, int &b) {
    // a और b की सामग्री को स्वैप करें
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

int partition(int *array, int lower, int upper) {
    // पिवट के लिए सही स्थान ढूंढने के लिए होयर पार्टीशनिंग तकनीक
    int pivot, start, end;
    pivot = array[lower]; // पहला एलिमेंट पिवट के रूप में
    start = lower; end = upper;
    while(start < end) {
        while(array[start] <= pivot && start < end) {
            start++; // स्टार्ट पॉइंटर दाईं ओर जाता है
        }
        while(array[end] > pivot) {
            end--; // एंड पॉइंटर बाईं ओर जाता है
        }
        if(start < end) {
            swap(array[start], array[end]); // छोटे और बड़े एलिमेंट को स्वैप करें
        }
    }
    array[lower] = array[end];
    array[end] = pivot;
    return end;
}

void quickSort(int *array, int left, int right) {
    int q;
    if(left < right) {
        q = partition(array, left, right);
        quickSort(array, left, q - 1); // लेफ्ट सब-ऐरे सॉर्ट करें
        quickSort(array, q + 1, right); // राइट सब-ऐरे सॉर्ट करें
    }
}

int main() {
    int n;
    cout << "एलिमेंट्स की संख्या दर्ज करें: ";
    cin >> n;
    int arr[n]; // दिए गए एलिमेंट्स की संख्या के साथ ऐरे बनाएं
    cout << "एलिमेंट्स दर्ज करें:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "सॉर्टिंग से पहले ऐरे: ";
    display(arr, n);
    quickSort(arr, 0, n - 1); // (n-1) अंतिम इंडेक्स के लिए
    cout << "सॉर्टिंग के बाद ऐरे: ";
    display(arr, n);
}

आउटपुट

एलिमेंट्स की संख्या दर्ज करें: 6
एलिमेंट्स दर्ज करें: 90 45 22 11 22 50
सॉर्टिंग से पहले ऐरे: 90 45 22 11 22 50
सॉर्टिंग के बाद ऐरे: 11 22 22 45 50 90