รังนกพิราบ

นี่คือตัวอย่างของเทคนิคการจัดเรียงแบบไม่เปรียบเทียบ ใช้ในกรณีที่จำนวนรายการและช่วงของค่าคีย์ที่เป็นไปได้ใกล้เคียงกัน

ในการจัดเรียงนี้ เราต้องเจาะรู จำนวนหลุมที่ต้องการจะขึ้นอยู่กับช่วงของตัวเลข ในแต่ละหลุมจะมีการแทรกรายการ ในที่สุดก็ลบออกจากหลุมและเก็บไว้ในอาร์เรย์เพื่อเรียงลำดับ

ความซับซ้อนของเทคนิคการจัดเรียง Pigeon-Hole

• ความซับซ้อนของเวลา:O(n+2^k)
• ความซับซ้อนของอวกาศ:O(2^k)

อินพุตและเอาต์พุต

Input:The unsorted list:802 630 20 745 52 300 612 932 78 187Output:Data before Sorting:802 630 20 745 52 300 612 932 78 187Data after Sorting:20 52 78 187 300 612 630 745 802 932

อัลกอริทึม

pigeonHoleSort(อาร์เรย์, ขนาด)

ป้อนข้อมูล - อาร์เรย์ของข้อมูลและจำนวนทั้งหมดในอาร์เรย์

ผลลัพธ์ − อาร์เรย์ที่เรียงลำดับ

เริ่มต้นค้นหา max และ min จากรายการอาร์เรย์ holeRange :=max – min +1 กำหนด holeRange number ของ Lists for i :=0 ถึง n-1 do hole[array[i]-min].append(array[i) ]) นับเสร็จแล้ว :=0 สำหรับ j :=0 ถึง holeRange-1 ทำในขณะที่ hole[j] ไม่ว่างเปล่า ทำ array[count] :=รับโหนดแรกของรู[j] และลบมันนับ :=นับ +1 เสร็จแล้ว เสร็จสิ้น

ตัวอย่าง

#include#include#includeusing เนมสเปซ std;void getMaxMin(int *arr, int n, int &maximum, int &minimum) { maximum =maximum =arr[0]; //เริ่มต้น max และ min arr[0] สำหรับ (int i =1; i maximum) maximum =arr[i]; // รับข้อมูลสูงสุด if(arr[i] <ขั้นต่ำ) ขั้นต่ำ =arr[i]; // รับข้อมูลขั้นต่ำ }} เป็นโมฆะ pegionHoleSort (int * arr, int n) { int max, min; getMaxMin(arr, n, สูงสุด, นาที); int holeRange =สูงสุด - นาที +1; รายการ รู[holeRange]; //สร้างอาร์เรย์ของรูสำหรับ(int i =0; i> น; int arr[n]; //สร้างอาร์เรย์ด้วยจำนวนองค์ประกอบที่กำหนด cout <<"ป้อนองค์ประกอบ:" <> arr[i]; } cout <<"ข้อมูลก่อนจัดเรียง:"; แสดง(arr, n); pegionHoleSort(arr, n); cout <<"ข้อมูลหลังการเรียงลำดับ:"; display(arr, n);}

ผลลัพธ์

ป้อนจำนวนองค์ประกอบ:10ป้อนองค์ประกอบ:802 630 20 745 52 300 612 932 78 187ข้อมูลก่อนจัดเรียง:802 630 20 745 52 300 612 932 78 187ข้อมูลหลังการจัดเรียง:20 52 78 187 300 612 630 745 802 932