Thuật toán Pigeonhole Sort (Sắp xếp lỗ bồ câu)

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

Để thực hiện sắp xếp này, cần tạo các "lỗ" (holes). Số lượng lỗ 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 ra từ lỗ và lưu vào mảng theo thứ tự đã sắp xếp.

Độ phức tạp của Pigeonhole Sort

• Time Complexity: O(n + 2^k)
• Space Complexity: O(2^k)

Input và Output

Input: Danh sách chưa sắp xếp: 802 630 20 745 52 300 612 932 78 187
Output: Dữ liệu trước sắp xếp: 802 630 20 745 52 300 612 932 78 187
Dữ liệu sau sắp xếp: 20 52 78 187 300 612 630 745 802 932

Thuật toán

pigeonHoleSort(array, size)
Input: Mảng dữ liệu, và tổng số phần tử trong mảng
Output: Mảng đã sắp xếp

Begin
  tìm max và min từ mảng
  holeRange := max - min + 1
  định nghĩa holeRange số lượng List (lỗ)
  for i := 0 to n-1 do
    hole[array[i] - min].append(array[i])
  done
  count := 0
  for j := 0 to holeRange-1 do
    while hole[j] không rỗng do
      array[count] := lấy node đầu của hole[j] và xóa nó
      count := count + 1
    done
  done
End

Ví dụ (C++)

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

void getMaxMin(int *arr, int n, int &maximum, int &minimum) {
    maximum = minimum = arr[0];
    for(int i = 1; i < n; i++) {
        if(arr[i] > maximum) maximum = arr[i];
        if(arr[i] < minimum) minimum = arr[i];
    }
}

void pegionHoleSort(int *arr, int n) {
    int max, min;
    getMaxMin(arr, n, max, min);
    int holeRange = max - min + 1;
    list<int> hole[holeRange];
    for(int i = 0; i < n; i++) {
        hole[arr[i] - min].push_back(arr[i]);
    }
    int count = 0;
    for(int j = 0; j < holeRange; j++) {
        while(!hole[j].empty()) {
            arr[count] = *(hole[j].begin());
            hole[j].erase(hole[j].begin());
            count++;
        }
    }
}

void display(int *array, int size) {
    for(int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

int main() {
    int n;
    cout << "Nhập số lượng phần tử: ";
    cin >> n;
    int arr[n];
    cout << "Nhập các phần tử:" << endl;
    for(int i = 0; i < n; i++) cin >> arr[i];
    cout << "Dữ liệu trước sắp xếp: ";
    display(arr, n);
    pegionHoleSort(arr, n);
    cout << "Dữ liệu sau sắp xếp: ";
    display(arr, n);
}

Kết quả

Nhập số lượng phần tử: 10
Nhập các phần tử: 802 630 20 745 52 300 612 932 78 187
Dữ liệu trước sắp xếp: 802 630 20 745 52 300 612 932 78 187
Dữ liệu sau sắp xếp: 20 52 78 187 300 612 630 745 802 932

Đặc điểm: Pigeonhole Sort hiệu quả khi phạm vi giá trị (range) không lớn hơn nhiều so với số phần tử n. Nếu range quá lớn, bộ nhớ O(range) trở nên không thực tế.