Chương trình C++ tìm phần tử nhỏ thứ k bằng phương pháp phân hoạch mảng

Chúng ta sẽ phát triển chương trình C++ tìm phần tử nhỏ thứ k (kth smallest element) bằng phương pháp phân hoạch mảng (partitioning the Array).

Thuật toán

Bắt đầu
  Hàm CreatePartition() có tham số mảng a, giới hạn dưới l và giới hạn trên h:
    in := l và pi := h
    với i từ l đến h, làm:
      nếu a[i] < a[pi], thì
        hoán đổi giá trị a[i] và a[in]
        tăng in lên 1
      xong
    hoán đổi giá trị a[pi] và a[in]
    trả về in
Kết thúc

Bắt đầu
  Hàm Partition():
    Tham số:
      Mảng A, giới hạn dưới/đến low/high, và k.
    Phần thân hàm:
      nếu low < high, thì
        p_in := Create_Partition(A, low, high)
        nếu p_in = k-1, thì
          trả về k-1
        khác nếu p_in > k-1
          Partition (A, low, p_in - 1, k)
        khác
          Partition (A, p_in + 1, high, k)
Kết thúc

Mã ví dụ

#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 << "\nNhập số phần tử mảng: ";
    cin >> n;
    int a[n];
    for(i = 0; i < n; i++) {
        cout << "Nhập phần tử " << i+1 << ": ";
        cin >> a[i];
    }
    cout << "\nNhập k cho phần tử nhỏ thứ k: ";
    cin >> k;
    k_k = Partition(a, 0, n-1, k);
    cout << "\nPhần tử nhỏ thứ k: " << a[k_k];
    return 0;
}

Kết quả đầu ra

Nhập số phần tử mảng: 4
Nhập phần tử 1: 3
Nhập phần tử 2: 2
Nhập phần tử 3: 5
Nhập phần tử 4: 4
Nhập k cho phần tử nhỏ thứ k: 3
Phần tử nhỏ thứ k: 4