C++ प्रोग्राम: मीडियन के निकटतम k नंबर खोजना

यह C++ प्रोग्राम एक सेट S (n नंबर्स) के मीडियन (Median) के निकटतम k नंबर खोजता है। यह क्विकसॉर्ट द्वारा सॉर्टिंग के बाद मीडियन के दोनों ओर से निकटतम तत्व चुनता है।

एल्गोरिदम

शुरुआत
  1. फंक्शन Partition() - हाई पर पिवट के आधार पर ऐरे पार्टीशन करें
  2. फंक्शन QuickSort() - क्विकसॉर्ट एल्गोरिदम से डेटा सॉर्ट करें
  3. मेन फंक्शन:
     - यदि डेटा तत्वों की संख्या विषम है:
         * मध्य इंडेक्स को low और अगले को high असाइन करें, मीडियन कैलकुलेट करें
         * k बार लूप चलाएं और मीडियन के निकटतम तत्व प्रिंट करें
     - अन्यथा (सम संख्या):
         * मीडियन दो मध्य मानों का औसत होगा
         * k बार लूप चलाएं और मीडियन के निकटतम तत्व प्रिंट करें
समाप्ति

उदाहरण कोड

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

void swap(int *x, int *y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

int Partition(int a[], int l, int h) {
    int pivot = h, index = l;
    for (int i = l; i < h; i++) {
        if (a[i] < a[pivot]) {
            swap(&a[i], &a[index]);
            index++;
        }
    }
    swap(&a[pivot], &a[index]);
    return index;
}

void QuickSort(int a[], int l, int h) {
    if (l < h) {
        int pindex = Partition(a, l, h);
        QuickSort(a, l, pindex - 1);
        QuickSort(a, pindex + 1, h);
    }
}

int main() {
    int n, k;
    cout << "Enter number of elements in dataset: ";
    cin >> n;
    
    int a[n];
    for (int i = 0; i < n; i++) {
        cout << "Enter element " << i+1 << ": ";
        cin >> a[i];
    }
    
    cout << "\nEnter number of elements nearest to median: ";
    cin >> k;
    
    QuickSort(a, 0, n-1);
    
    double median;
    int left, right;
    
    if (n % 2 == 1) {
        median = a[n/2];
        left = n/2 - 1;
        right = n/2 + 1;
    } else {
        median = (a[n/2 - 1] + a[n/2]) / 2.0;
        left = n/2 - 1;
        right = n/2;
    }
    
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << "\nMedian: " << median;
    cout << "\nThe " << k << " elements nearest to median: ";
    
    while (k > 0) {
        double diffLeft = (left >= 0) ? abs(median - a[left]) : 1e9;
        double diffRight = (right < n) ? abs(a[right] - median) : 1e9;
        
        if (diffLeft <= diffRight && left >= 0) {
            cout << a[left] << " ";
            left--;
        } else if (right < n) {
            cout << a[right] << " ";
            right++;
        } else break;
        k--;
    }
    cout << endl;
    return 0;
}

आउटपुट

Enter number of elements in dataset: 7
Enter element 1: 7
Enter element 2: 6
Enter element 3: 5
Enter element 4: 4
Enter element 5: 3
Enter element 6: 2
Enter element 7: 1
Enter number of elements nearest to median: 2

Sorted array: 1 2 3 4 5 6 7
Median: 4
The 2 elements nearest to median: 3 5

व्याख्या: सॉर्टेड ऐरे [1,2,3,4,5,6,7] में मीडियन 4 है। इसके निकटतम दो तत्व 3 और 5 हैं (दोनों की दूरी 1 है)। प्रोग्राम दोनों तरफ से तुलना करके निकटतम तत्व चुनता है।

समय जटिलता: O(n log n) सॉर्टिंग के लिए, O(k) निकटतम तत्व खोजने के लिए।