นี่คือโปรแกรม C++ สำหรับหา k ตัวเลขที่ใกล้ Median ของ S มากที่สุด โดย S เป็นเซตของ n ตัวเลข
อัลกอริทึม
เริ่มต้น ฟังก์ชัน partition() สำหรับแบ่งอาร์เรย์ตามค่า pivot ที่ high: อาร์กิวเมนต์: a[]=อาร์เรย์ l=low H=high ส่วนตัวของฟังก์ชัน: ประกาศตัวแปร pivot, in, i เริ่มต้น in = l ตั้งค่า pivot = h สำหรับ i=l ถึง h-1 ถ้า(a[i] < a[pivot]) swap a[i] และ a[in] เพิ่ม in swap a[pivot] และ a[in] คืนค่า in จบ เริ่มต้น ฟังก์ชัน QuickSort() เพื่อนำ QuickSort มาใช้จัดเรียงข้อมูล: อาร์กิวเมนต์: a[]=อาร์เรย์ l=low h=high ส่วนตัวของฟังก์ชัน: ประกาศ pindex ถ้า(l < h) index = Partition(a, l, h) QuickSort(a, l, pindex-1); QuickSort(a, pindex+1, h); คืนค่า 0 จบ เริ่มต้น ฟังก์ชัน main() ถ้าจำนวนข้อมูลเป็นคี่ กำหนดดัชนีกลางให้ low และดัชนีถัดไปให้ high คำนวณ median รันลูป k ครั้ง พิมพ์องค์ประกอบที่ใกล้ median มากที่สุด มิฉะนั้น Median จะเป็นค่าเฉลี่ยของค่ากลางสองค่า รันลูป k ครั้ง พิมพ์องค์ประกอบที่ใกล้ median มากที่สุด จบ
ตัวอย่างโค้ด
#include<iostream> using namespace std; void swap(int *x, int *y) { //สลับค่าสองค่า int tmp; tmp = *x; *x = *y; *y = tmp; } int Partition(int a[], int l, int h) { int pivot, in, i; in = l; pivot = h; for(i=l; i < h; i++) { if(a[i] < a[pivot]) { swap(&a[i], &a[in]); in++; } } swap(&a[pivot], &a[in]); return in; } int QuickSort(int a[], int l, int h) { int pindex; if(l < h) { pindex = Partition(a, l, h); QuickSort(a, l, pindex-1); QuickSort(a, pindex+1, h); } return 0; } int main() { int n, i, h, l, k; double d1,d2, median; cout<<"Enter the number of element in dataset: "; cin>>n; int a[n]; for(i = 0; i < n; i++) { cout<<"\nEnter "<<i+1<<" element: "; cin>>a[i]; } cout<<"\nEnter the number of element nearest to the median required: "; cin>>k; QuickSort(a, 0, n-1); cout<<"The K element nearest to the median are: "; if(n%2 == 1) { median = a[n/2]; h = n/2+1; l= n/2; while(k > 0) { if((median-a[l] <= a[h]-median) && l >= 0) { cout<<" "<<a[l]; l--; k--; } else if((median-a[l] > a[h]-median) && h <= n-1) { cout<<" "<<a[h]; h++; k--; } } } else { d1 = a[n/2]; d2 = a[n/2-1]; median = (d1+d2)/2; h = n/2; l = n/2-1; while(k > 0) { d1 = a[l]; d2 = a[h]; if((median-d2 <= d1-median) && l >= 0) { cout<<" "<<a[l]; l--; k--; } else if((median-d2 > d1-median) && h <= n-1) { cout<<" "<<a[h]; h++; k--; } } } return 0; }
ผลลัพธ์
Enter the number of element in dataset: 7 Enter 1 element: 7 Enter 2 element: 6 Enter 3 element: 5 Enter 4 element: 4 Enter 5 element: 3 Enter 6 element: 2 Enter 7 element: 1 Enter the number of element nearest to the median required: 2 The K element nearest to the median are: 4 3
