C++ প্রোগ্রাম: অ্যারে পার্টিশনিং মেথড দিয়ে kth সবচেয়ে ছোট এলিমেন্ট বের করা

আমরা অ্যারে পার্টিশনিং মেথড ব্যবহার করে kth সবচেয়ে ছোট এলিমেন্ট বের করার একটি C++ প্রোগ্রাম বিকাশ করব।

শুরু
  CreatePartition() ফাংশনের আর্গুমেন্ট: অ্যারে a, লোয়ার লিমিট l এবং আপার লিমিট h
    in := l এবং pi := h
    i = l থেকে h পর্যন্ত লুপ চালান
      যদি a[i] < a[pi] হয়, তবে
        a[i] এবং a[in] এর মান এক্সচেঞ্জ করুন
        in কে 1 বাড়ান
      শেষ
    a[pi] এবং a[in] এর মান এক্সচেঞ্জ করুন
    in রিটার্ন করুন
শেষ

শুরু
  Partition() ফাংশন:
    আর্গুমেন্ট: অ্যারে A, লোয়ার এবং আপার লিমিট low এবং high, এবং k।
    ফাংশন বডি:
      যদি low < high হয়, তবে
        p_in := Create_Partition(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 
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, in, i;
    in = l; pi = h;
    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 << "\nEnter the number array elements: "; cin >> n;
    int a[n];
    for (i = 0; i < n; i++) { cout << "Enter element " << i+1 << ": "; cin >> a[i]; }
    cout << "\nEnter the k for the kth smallest element: "; cin >> k;
    k_k = Partition(a, 0, n-1, k);
    cout << "\nThe kth smallest element: " << a[k_k];
    return 0;
}

Enter the number array elements: 4
Enter element 1: 3
Enter element 2: 2
Enter element 3: 5
Enter element 4: 4
Enter the k for the kth smallest element: 3
The kth smallest element: 4