C++ प्रोग्राम: सरणी के पार्टीशन विधि से kवां सबसे छोटा तत्व खोजें

एल्गोरिदम

CreatePartition() फ़ंक्शन बनाएं जिसमें सरणी a, निचली सीमा l और ऊपरी सीमा h हो। in := l और pi := h सेट करें। l से h तक लूप चलाएं, यदि a[i] < a[pi] तो a[i] और a[in] को स्वैप करें और in बढ़ाएं। अंत में a[pi] और a[in] को स्वैप करें और in लौटाएं। Partition() फ़ंक्शन में: यदि low < high तो p_in := CreatePartition(A, low, high)। यदि p_in == k-1 तो k-1 लौटाएं, अन्यथा यदि p_in > k-1 तो Partition(A, low, p_in-1, k) कॉल करें, अन्यथा Partition(A, p_in+1, high, k) कॉल करें।

उदाहरण कोड

#include <iostream>
using namespace std;

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

int CreatePartition(int a[], int l, int h) {
    int pi = h, in = l, i;
    for (i = l; i < h; i++) {
        if (a[i] < a[pi]) {
            swap(&a[i], &a[in]);
            in++;
        }
    }
    swap(&a[pi], &a[in]);
    return in;
}

int Partition(int a[], int low, int high, int k) {
    int p_in;
    if (low < high) {
        p_in = CreatePartition(a, low, high);
        if (p_in == k-1)
            return k-1;
        else if (p_in > k-1)
            Partition(a, low, p_in-1, k);
        else
            Partition(a, p_in+1, high, k);
    }
}

int main() {
    int n, i, k, k_k;
    cout << "\nसरणी तत्वों की संख्या दर्ज करें: ";
    cin >> n;
    int a[n];
    for (i = 0; i < n; i++) {
        cout << "तत्व " << i+1 << ": ";
        cin >> a[i];
    }
    cout << "\nkवें सबसे छोटे तत्व के लिए k दर्ज करें: ";
    cin >> k;
    k_k = Partition(a, 0, n-1, k);
    cout << "\nkवां सबसे छोटा तत्व: " << a[k_k];
    return 0;
}

आउटपुट

सरणी तत्वों की संख्या दर्ज करें: 4
तत्व 1: 3
तत्व 2: 2
तत्व 3: 5
तत्व 4: 4
kवें सबसे छोटे तत्व के लिए k दर्ज करें: 3
kवां सबसे छोटा तत्व: 4