Chương trình C++ tìm k phần tử gần trung vị nhất

Sắp xếp mảng bằng QuickSort, tìm trung vị, sau đó mở rộng ra hai bên để lấy k phần tử gần trung vị nhất.

Thuật toán

Partition(a, l, h): QuickSort partition chuẩn.
QuickSort(a, l, h): Đệ quy sắp xếp.
Main:
  Sắp xếp mảng.
  Tính median (trung vị).
  Thiết lập l, h hai bên median.
  Lặp k lần: so sánh khoảng cách a[l] và a[h] đến median, in cái gần hơn, dịch con trỏ.

Ví dụ mã nguồn

#include <iostream>
#include <cmath>
using namespace std;

void swap(int* x, int* y) { int t=*x; *x=*y; *y=t; }

int partition(int a[], int l, int h) {
    int pivot = h, idx = l;
    for (int i = l; i < h; i++)
        if (a[i] < a[pivot]) swap(&a[i], &a[idx++]);
    swap(&a[pivot], &a[idx]);
    return idx;
}

void quickSort(int a[], int l, int h) {
    if (l < h) {
        int p = partition(a, l, h);
        quickSort(a, l, p-1);
        quickSort(a, p+1, h);
    }
}

int main() {
    int n, k;
    cout << "So phan tu: "; cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cout << "Phan tu " << i+1 << ": "; cin >> a[i];
    }
    cout << "So phan tu gan median can tim: "; cin >> k;
    quickSort(a, 0, n-1);
    double median;
    int l, h;
    if (n % 2) {
        median = a[n/2];
        l = n/2 - 1; h = n/2 + 1;
    } else {
        median = (a[n/2] + a[n/2-1]) / 2.0;
        l = n/2 - 1; h = n/2;
    }
    cout << k << " phan tu gan median " << median << ": ";
    while (k-- > 0) {
        double dl = (l >= 0) ? median - a[l] : 1e9;
        double dr = (h < n) ? a[h] - median : 1e9;
        if (dl <= dr) cout << a[l--] << " ";
        else cout << a[h++] << " ";
    }
    return 0;
}

Đầu ra mẫu

So phan tu: 7
Phan tu: 7 6 5 4 3 2 1
So phan tu gan median: 2
2 phan tu gan median 4: 4 3