เราจะพัฒนาโปรแกรม C++ เพื่อหาองค์ประกอบที่เล็กที่สุดลำดับที่ k (kth smallest element) โดยวิธีการแบ่งพาร์ติชันอาร์เรย์ (Partitioning the Array)
อัลกอริทึม
Begin ฟังก์ชัน 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 End Begin ฟังก์ชัน 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) 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
