Chương trình C++ cho thuật toán Pigeonhole Sort

Pigeonhole Sort là ví dụ của kỹ thuật sắp xếp không so sánh (non-comparison sort). Dùng khi số lượng phần tử (n) và phạm vi giá trị khóa có thể (N) xấp xỉ nhau.

Để thực hiện sắp xếp này, ta tạo các "lổ" (holes). Số lổ cần thiết được quyết định bởi phạm vi số. Mỗi lổ chứa các phần tử. Cuối cùng lấy phần tử từ các lổ và đưa vào mảng theo thứ tự đã sắp xếp.

Pigeonhole sorting còn gọi là Count Sort, phù hợp khi n ≈ N. Độ phức tạp thời gian O(n + N).

Ví dụ

Input: arr[] = {7, 4, 2, 6, 3, 1, 5}
Output: 1 2 3 4 5 6 7

Giải thích

1. Tìm min và max trong mảng. Phạm vi = max - min + 1.
2. Tạo mảng "pigeonholes" rỗng kích thước bằng phạm vi.
3. Duyệt mảng gốc, đưa phần tử arr[i] vào lổ tại chỉ số arr[i] - min.
4. Duyệt mảng pigeonholes theo thứ tự, đưa các phần tử từ lổ không rỗng về mảng gốc.

Code ví dụ

#include <iostream>
using namespace std;

#define MAX 7

void pigeonhole_sort(int min, int max, int *a) {
    int size = max - min + 1;
    int holes[size] = {0};
    
    // Đưa phần tử vào lổ tương ứng
    for (int i = 0; i < size; i++) {
        holes[a[i] - min] += 1;
    }
    
    // Lấy phần tử từ lổ về mảng gốc
    int idx = 0;
    for (int count = 0; count < size; count++) {
        while (holes[count]-- > 0) {
            a[idx++] = count + min;
        }
    }
}

int main() {
    int a[] = {7, 4, 2, 6, 3, 1, 5};
    int min = a[0], max = a[0];
    
    for (int i = 1; i < MAX; i++) {
        if (a[i] < min) min = a[i];
        if (a[i] > max) max = a[i];
    }
    
    pigeonhole_sort(min, max, a);
    
    for (int i = 0; i < MAX; i++) {
        cout << a[i] << "\t";
    }
    return 0;
}

Kết quả

1 2 3 4 5 6 7

Độ phức tạp

• Thời gian: O(n + N) với N = max - min + 1
• Không gian: O(N)
• Ổn định: Có

Lưu ý: Chỉ hiệu quả khi phạm vi giá trị (N) không quá lớn so với số phần tử (n).