Pigeonhole Sort হল তুলনাহীন বাছাই কৌশলের একটি উদাহরণ। এটি ব্যবহার করা হয় যেখানে আইটেমের সংখ্যা এবং সম্ভাব্য কী মানগুলির পরিসর প্রায় একই।
এই সাজানোর জন্য, আমাদের কিছু গর্ত করতে হবে। প্রয়োজনীয় গর্ত সংখ্যা সংখ্যার পরিসীমা দ্বারা নির্ধারিত হয়। প্রতিটি গর্তে, আইটেম ঢোকানো হয়। অবশেষে গর্ত থেকে মুছে ফেলা হয়েছে এবং সাজানো অর্ডারের জন্য একটি অ্যারেতে সংরক্ষণ করা হয়েছে৷
Pigeonhole sorting, কাউন্ট সর্ট নামেও পরিচিত, হল একটি সাজানোর অ্যালগরিদম যা উপাদানগুলির তালিকা বাছাই করার জন্য উপযুক্ত যেখানে উপাদানের সংখ্যা (n) এবং সম্ভাব্য মূল মানগুলির সংখ্যা (N) প্রায় একই। এর জন্য O(n + N) সময় প্রয়োজন।
Input: arr[]={7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7 ব্যাখ্যা
-
অ্যারেতে সর্বনিম্ন এবং সর্বোচ্চ উপাদান খুঁজুন। সর্বনিম্ন এবং সর্বোচ্চ উপাদান যথাক্রমে 'মিনিট' এবং 'সর্বোচ্চ' হবে। তারপর 'max-min-1' হিসেবে রেঞ্জ খুঁজুন।
-
রেঞ্জের মতো একই আকারের "কবুতর হোল" এর জন্য প্রাথমিকভাবে খালি একটি অ্যারে সেট আপ করুন৷
-
অ্যারের প্রতিটি উপাদান অতিক্রম করুন এবং তারপর প্রতিটি উপাদানকে তার পায়রার গহ্বরে রাখুন। একটি উপাদান arr[i] index 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
