C++ में क्विकसॉर्ट प्रोग्राम

क्विकसॉर्ट क्या है?

क्विकसॉर्ट एक सॉर्टिंग तकनीक है जो अनसॉर्टेड सूची (सरणी) को सॉर्ट करने के लिए तुलनाओं का उपयोग करती है। क्विकसॉर्ट को पार्टीशन एक्सचेंज सॉर्ट के नाम से भी जाना जाता है।

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

क्विकसॉर्ट सबसे कुशल सॉर्टिंग एल्गोरिदम में से एक है और यह एक सरणी को छोटे भागों में विभाजित करने पर आधारित है। नाम इस तथ्य से आता है कि क्विकसॉर्ट किसी भी सामान्य सॉर्टिंग एल्गोरिदम की तुलना में डेटा तत्वों की सूची को काफी तेजी से सॉर्ट करने में सक्षम है। और मर्ज सॉर्ट की तरह, क्विक सॉर्ट भी समस्या-समाधान पद्धति के विभाजन और विजय (divide and conquer) दृष्टिकोण की श्रेणी में आता है।

क्विकसॉर्ट एल्गोरिदम कैसे काम करता है

1. पिवट चुनें: सूची से किसी भी मान को पिवट के रूप में तय करें (आमतौर पर अंतिम मान)
2. विभाजन: सरणी को दो भागों में बांटें - पिवट से छोटे तत्व बाएं, बड़े तत्व दाएं
3. पुनरावृत्ति: प्रत्येक उप-सरणी के लिए चरण 1-2 दोहराएं जब तक सरणी का आकार 1 न हो जाए
4. संयोजन: छोटे भागों को जोड़कर पूरी तरह से सॉर्ट की गई सरणी प्राप्त करें

चरण-दर-चरण उदाहरण

सरणी पर विचार करें: 50, 23, 9, 18, 61, 32

चरण 1: पिवट = 32 (अंतिम तत्व)

• 50 > 32: कोई परिवर्तन नहीं
• 23 < 32: 50 और 23 स्वैप करें → 23, 50, 9, 18, 61, 32
• 9 < 32: 50 और 9 स्वैप करें → 23, 9, 50, 18, 61, 32
• 18 < 32: 50 और 18 स्वैप करें → 23, 9, 18, 50, 61, 32
• 61 > 32: कोई परिवर्तन नहीं
• पिवट को 50 के साथ स्वैप करें → 23, 9, 18, 32, 61, 50

चरण 2: पिवट (32) अपनी सही स्थिति में है। बाएं: 23, 9, 18 | दाएं: 61, 50

चरण 3: उप-सरणियों के लिए पुनरावृत्ति करें

अंतिम सरणी: 9, 18, 23, 32, 50, 61

उदाहरण

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int a[], int low, int high) {
    int pivot = a[high];
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if (a[j] < pivot) {
            i++;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i + 1], &a[high]);
    return (i + 1);
}

int randomPivotPartition(int a[], int low, int high) {
    int pvt = low + rand() % (high - low + 1);
    swap(&a[high], &a[pvt]);
    return partition(a, low, high);
}

void quickSort(int a[], int low, int high) {
    if (low < high) {
        int pindex = randomPivotPartition(a, low, high);
        quickSort(a, low, pindex - 1);
        quickSort(a, pindex + 1, high);
    }
}

int main() {
    int arr[] = {7, 4, 2, 6, 3, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

आउटपुट

Sorted array: 1 2 3 4 5 6 7

जटिलता विश्लेषण

स्थान जटिलता: O(log n) - रिकर्सन स्टैक के कारण

क्विकसॉर्ट के लाभ

• औसत स्थिति में बहुत तेज़
• इन-प्लेस सॉर्टिंग (कम अतिरिक्त मेमोरी)
• कैश-फ्रेंडली

नुकसान

• अस्थिर सॉर्ट
• सबसे खराब स्थिति O(n²) - पहले से सॉर्टेड सरणी के लिए
• रिकर्सन स्टैक ओवरफ्लो का खतरा