এটি একটি C++ প্রোগ্রাম যা S সেটের n সংখ্যার মিডিয়ানের কাছে k সংখ্যা খুঁজে বের করে।
অ্যালগরিদম
শুরু
ফাংশন partition() হাই-এ পিভট ভ্যালু ভিত্তিকেই অ্যারে পার্টিশন করার জন্য:
আর্গুমেন্ট:
a[] = একটি অ্যারে।
l = লো
h = হাই
ফাংশনের বডি:
ভেরিয়েবল ডিক্লেয়ার করুন 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() ডেটা এলিমেন্ট সোর্ট করার জন্য কুইকসোর্ট অ্যালগরিদম বাস্তবায়ন:
আর্গুমেন্ট:
a[] = একটি অ্যারে।
l = লো
h = হাই
ফাংশনের বডি:
pindex ডিক্লেয়ার করুন
যদি (l < h)
index = Partition(a, l, h)
QuickSort(a, l, pindex-1);
QuickSort(a, pindex+1, h);
0 রিটার্ন করুন।
শেষ
শুরু
ফাংশন main(),
যদি ডেটা এলিমেন্টের সংখ্যা বিজোড় হয়,
মিডল ইনডেক্সকে low-এ এবং তার পরের ইনডেক্সকে high-এ অ্যাসাইন করুন এবং মিডিয়ান ক্যালকুলেট করুন।
k বার লুপ চালান এবং যে এলিমেন্ট মিডিয়ানের কাছে সেটি প্রিন্ট করুন।
অন্যথায়
মিডিয়ান হবে দুটি মিডল ভ্যালুর গড়।
k বার লুপ চালান এবং যে এলিমেন্ট মিডিয়ানের কাছে সেটি প্রিন্ট করুন।
শেষ
উদাহরণ
#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
