পিজনহোল সোর্ট একটি নন-কম্প্যারিজন (তুলনামূলক নন) সোর্টিং টেকনিক। এটি তখন কার্যকর হয় যখন আইটেমের সংখ্যা এবং সম্ভাব্য কি ভ্যালুর রেঞ্জ প্রায় একই হয়।
পিজনহোল সোর্টের জটিলতা
- টাইম কমপ্লেক্সিটি: O(n + 2^k)
- স্পেস কমপ্লেক্সিটি: O(2^k)
ইনপুট এবং আউটপুট
Input: The unsorted list: 802 630 20 745 52 300 612 932 78 187
Output: Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932
অ্যালগরিদম
pigeonHoleSort(array, size)
Input: ডেটার অ্যারে, এবং অ্যারেতে মোট এলিমেন্ট
Output: সর্ট করা অ্যারে
Begin
array থেকে max এবং min বের করুন
holeRange := max - min + 1
holeRange সংখ্যক লিস্ট (হোল) ডিফাইন করুন
for i := 0 to n-1 do
hole[array[i] - min].append(array[i])
done
count := 0
for j := 0 to holeRange-1 do
while hole[j] খালি নয় do
array[count] := hole[j] এর প্রথম নোড পাওয়া এবং ডিলিট করা
count := count + 1
done
done
End
C++ উদাহরণ
#include <iostream>
#include <list>
#include <cmath>
using namespace std;
void getMaxMin(int *arr, int n, int &maximum, int &minimum) {
maximum = minimum = arr[0];
for(int i = 1; i < n; i++) {
if(arr[i] > maximum) maximum = arr[i];
if(arr[i] < minimum) minimum = arr[i];
}
}
void pegionHoleSort(int *arr, int n) {
int max, min;
getMaxMin(arr, n, max, min);
int holeRange = max - min + 1;
list<int> hole[holeRange];
for(int i = 0; i < n; i++) {
hole[arr[i] - min].push_back(arr[i]);
}
int count = 0;
for(int j = 0; j < holeRange; j++) {
while(!hole[j].empty()) {
arr[count] = *(hole[j].begin());
hole[j].erase(hole[j].begin());
count++;
}
}
}
void display(int *array, int size) {
for(int i = 0; i < size; i++) cout << array[i] << " ";
cout << endl;
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n];
cout << "Enter elements:" << endl;
for(int i = 0; i < n; i++) cin >> arr[i];
cout << "Data before Sorting: "; display(arr, n);
pegionHoleSort(arr, n);
cout << "Data after Sorting: "; display(arr, n);
}
আউটপুট
Enter the number of elements: 10
Enter elements: 802 630 20 745 52 300 612 932 78 187
Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932
