सी++ प्रोग्राम सरणी को विभाजित करने की विधि द्वारा kth सबसे छोटा तत्व खोजने के लिए

हम एरे को विभाजित करने की विधि द्वारा kth सबसे छोटा तत्व खोजने के लिए एक C++ प्रोग्राम विकसित करेंगे।

एल्गोरिदम

Begin
   Function CreatePartition() has an array a, and the lower l and upper limit h as arguments
   in := l and pi := h
   for i in range l to h, do
      if a[i] < a[pi], then
         exchange the values of a[i] and a[in]
         increase the in by 1
      done
      exchange the values of a[pi] and a[in]
   return in
End
Begin
   Function Partition():
   Arguments:
      An array A, and the lower and upper limit low and high, and also k.
      Body of the function:
      if low < high, then
         p_in := Create_Partition(A, low, high)
         if p_in = k-1, then
            return k-1
         else if p_in > k-1
            Partition (A, low, p_in – 1, k)
         else
            Partition (A, p_in + 1, high, k)
End

उदाहरण कोड

#include<iostream>
using namespace std;
void swap(int *a, int *b) {
   int t;
   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