कबूतर छँटाई गैर-तुलना छँटाई तकनीक का एक उदाहरण है। इसका उपयोग वहां किया जाता है जहां मदों की संख्या और संभावित कुंजी मानों की सीमा लगभग समान होती है।
ऐसा करने के लिए, हमें कुछ छेद बनाने की जरूरत है। आवश्यक छिद्रों की संख्या संख्याओं की सीमा से तय होती है। प्रत्येक छेद में, आइटम डाले जाते हैं। अंत में छेद से हटा दिया गया और क्रमबद्ध क्रम के लिए एक सरणी में संग्रहीत किया गया।
पिजनहोल सॉर्टिंग, जिसे काउंट सॉर्ट के रूप में भी जाना जाता है, एक सॉर्टिंग एल्गोरिथम है जो उन तत्वों की सूची को सॉर्ट करने के लिए उपयुक्त है जहां तत्वों की संख्या (एन) और संभावित कुंजी मानों की संख्या (एन) लगभग समान हैं। [1] इसके लिए O(n + N) समय चाहिए।
Input: arr[]={7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7 स्पष्टीकरण
-
सरणी में न्यूनतम और अधिकतम तत्व खोजें। न्यूनतम और अधिकतम तत्व क्रमशः 'न्यूनतम' और 'अधिकतम' होंगे। फिर श्रेणी को 'अधिकतम-न्यूनतम-1' के रूप में खोजें।
-
"कबूतर छेद" के लिए शुरू में खाली एक सरणी सेट करें जो कि सीमा के समान आकार की हो।
-
सरणी के प्रत्येक तत्व को पार करें और फिर प्रत्येक तत्व को उसके पिजनहोल में डालें। एक तत्व arr[i] इंडेक्स arr[i] – min.
. पर छेद में डाल दिया जाएगा -
लूप सभी पिजनहोल सरणी में क्रम से शुरू होगा और सभी तत्वों को गैर-खाली छेद से वापस मूल सरणी में डाल देगा।
उदाहरण
#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