Pigeonhole Sort เป็นตัวอย่างของเทคนิคการเรียงลำดับแบบไม่เปรียบเทียบ (non-comparison sorting technique) ใช้ในกรณีที่จำนวนรายการและช่วงของคีย์ที่เป็นไปได้มีค่าใกล้เคียงกัน
เพื่อทำการเรียงนี้ เราต้องสร้าง "รู" (holes) จำนวนรูที่ต้องการขึ้นอยู่กับช่วงของตัวเลข ในแต่ละรูจะใส่รายการเข้าไป สุดท้ายนำออกจากรูและเก็บในอาร์เรย์เพื่อลำดับที่เรียงแล้ว
Pigeonhole sorting หรือที่รู้จักในชื่อ Count Sort เป็นอัลกอริทึมการเรียงที่เหมาะสำหรับการเรียงรายการที่จำนวนองค์ประกอบ (n) และจำนวนค่าคีย์ที่เป็นไปได้ (N) ใกล้เคียงกัน ต้องใช้เวลา O(n + N)
Input: arr[]={7,4,2,6,3,1,5} Output: 1 2 3 4 5 6 7
คำอธิบาย
หาองค์ประกอบน้อยที่สุดและมากที่สุดในอาร์เรย์ องค์ประกอบน้อยที่สุดและมากที่สุดจะเป็น 'min' และ 'max' ตามลำดับ จากนั้นหาช่วง (range) เป็น 'max - min - 1'
ตั้งค่าอาร์เรย์ว่างเปล่าสำหรับ "pigeonholes" ขนาดเท่ากับช่วง
วนลูปผ่านแต่ละองค์ประกอบของอาร์เรย์ และใส่แต่ละองค์ประกอบใน pigeonhole ของมัน องค์ประกอบ arr[i] จะถูกใส่ในรูที่ดัชนี arr[i] - min
ลูปจะเริ่มต้นใหม่ทั้งหมดในอาร์เรย์ pigeonhole ตามลำดับ และนำองค์ประกอบทั้งหมดจากรูที่ไม่ว่างกลับไปในอาร์เรย์เดิม
ตัวอย่าง
#include <iostream>
using namespace std;
#define MAX 7
void pigeonhole_sort(int, int, int *);
int main() {
int i, min, max;
int a[] = {7, 4, 2, 6, 3, 1, 5};
min = a[0];
max = a[0];
for (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 (i = 0; i < MAX; i++) {
cout << a[i] << "\t";
}
}
void pigeonhole_sort(int mi, int ma, int *a) {
int size, count = 0, i;
int *current;
current = a;
size = ma - mi + 1;
int holes[size];
for (i = 0; i < size; i++) {
holes[i] = 0;
}
for (i = 0; i < size; i++, current++) {
holes[*current - mi] += 1;
}
for (count = 0, current = &a[0]; count < size; count++) {
while (holes[count]-- > 0) {
*current++ = count + mi;
}
}
}
ผลลัพธ์
1 2 3 4 5 6 7
