Pigeonhole Sort (การจัดเรียงรูปหลุมนกกระปูด)

Pigeonhole Sort เป็นอัลกอริทึมจัดเรียงแบบ Non-comparison (ไม่เปรียบเทียบ) ใช้ได้ดีเมื่อ จำนวนข้อมูล (n) และช่วงค่าที่เป็นไปได้ (range) ใกล้เคียงกัน

ความซับซ้อน (Complexity)

แนวคิดการทำงาน

1. หาค่า min และ max ของข้อมูล
2. สร้าง "หลุม" (Holes/Buckets) จำนวน max - min + 1 ช่อง
3. นำแต่ละตัวเลขไปวางในหลุมที่ตรงกับค่า (index = value - min)
4. ดึงข้อมูลออกจากหลุมตามลำดับ มาใส่ในอาเรย์ผลลัพธ์

ตัวอย่างข้อมูล

Input:  802 630 20 745 52 300 612 932 78 187
Output: 20 52 78 187 300 612 630 745 802 932

อัลกอริทึม (Pseudocode)

pigeonHoleSort(array, size)
  min, max = find min and max from array
  holeRange = max - min + 1
  create hole[holeRange] as list of lists

  for each value in array:
    hole[value - min].append(value)

  count = 0
  for each hole in holes:
    while hole not empty:
      array[count] = hole.pop_first()
      count++

ตัวอย่างโค้ด C++

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

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

void pigeonHoleSort(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].front();
            hole[j].pop_front();
            count++;
        }
    }
}

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

int main() {
    int n; cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << "Before: "; display(arr, n);
    pigeonHoleSort(arr, n);
    cout << "After: "; display(arr, n);
}

เมื่อไหร่ควรใช้ Pigeonhole Sort?

• ข้อมูลเป็นจำนวนเต็ม (Integers)
• ช่วงค่า (Range) ไม่ใหญ่เกินไป (k ≈ n)
• ต้องการ Stable Sort (รักษาลำดับเดิมของค่าเท่ากัน)
• ไม่เหมาะสำหรับ: ข้อมูล Float, String, Range ใหญ่มาก (เช่น 1 ถึง 1 ล้าน)

เปรียบเทียบกับ Counting Sort

Pigeonhole Sort คล้าย Counting Sort แต่เก็บ ค่าจริง ในหลุม (ไม่ใช่แค่นับจำนวน) ทำให้เหมาะกับข้อมูลที่มีค่าซ้ำกัน และต้องการ Stable Sort