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