Pigeonhole Sort เป็นตัวอย่างของเทคนิคการคัดแยกแบบไม่เปรียบเทียบ ใช้ในกรณีที่จำนวนรายการและช่วงของค่าคีย์ที่เป็นไปได้ใกล้เคียงกัน
ในการจัดเรียงนี้ เราต้องเจาะรู จำนวนหลุมที่ต้องการจะขึ้นอยู่กับช่วงของตัวเลข ในแต่ละหลุมจะมีการแทรกรายการ ในที่สุดก็ลบออกจากหลุมและเก็บไว้ในอาร์เรย์เพื่อเรียงลำดับ
การเรียงลำดับ Pigeonhole หรือที่เรียกว่าการเรียงลำดับการนับ เป็นอัลกอริธึมการเรียงลำดับที่เหมาะสำหรับการจัดเรียงรายการองค์ประกอบโดยที่จำนวนองค์ประกอบ (n) และจำนวนของค่าคีย์ที่เป็นไปได้ (N) ใกล้เคียงกัน[1] ต้องใช้เวลา O(n + N)
Input: arr[]={7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7 คำอธิบาย
-
ค้นหาองค์ประกอบต่ำสุดและสูงสุดในอาร์เรย์ องค์ประกอบต่ำสุดและสูงสุดจะเป็น 'min' และ 'max' ตามลำดับ แล้วหาช่วงเป็น 'max-min-1'
-
ตั้งค่าอาร์เรย์ในขั้นต้นที่ว่างเปล่าสำหรับ "ช่องนกพิราบ" ที่มีขนาดเท่ากับของช่วง
-
สำรวจแต่ละองค์ประกอบของอาร์เรย์ แล้วใส่แต่ละองค์ประกอบลงในช่องพิราบ องค์ประกอบ arr[i] จะถูกใส่ลงในรูที่ดัชนี arr[i] – นาที
-
การวนซ้ำจะเริ่มทั่วทั้งอาร์เรย์ของรูพิราบตามลำดับและนำองค์ประกอบทั้งหมดจากรูที่ไม่ว่างกลับเข้าไปในอาร์เรย์ดั้งเดิม
ตัวอย่าง
#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
