โปรแกรม C++ เพื่อค้นหา kth องค์ประกอบที่เล็กที่สุดโดยวิธีการแบ่งพาร์ติชั่นอาร์เรย์

เราจะพัฒนาโปรแกรม C++ เพื่อค้นหาองค์ประกอบที่เล็กที่สุดที่ k โดยวิธีการแบ่งพาร์ติชั่นอาร์เรย์

อัลกอริทึม

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