Algorithms/pigeonhole sort

تلائم خوارزمية الترتيب ببرج الحمام Pigeonhole sort قوائم العناصر التي يكون فيها عدد العناصر وعدد القيم المفتاحية الممكنة possible key values متساويين تقريبًا.

هذه الخوارزمية مشابهة لخوارزمية الترتيب بالعد، باستثناء أنّها تحرّك العناصر مرتين: مرّة إلى مصفوفة الدلو ومرة أخرى إلى الوجهة النهائية.

تستخدم خوارزمية الترتيب ببرج الحمام استخدامًا محدودًا وذلك لصعوبة تحقيق متطلباتها، ويفضّل استخدام خوارزمية الترتيب بالدلو -والتي تعدّ تعميمًا أكثر فعالية من ناحية المساحة والوقت- إن كانت المصفوفة المراد ترتيبها كبيرة في الحجم.

خطوات الخوارزمية

1. إيجاد القيمتين العظمى (لتكن max) والصغرى (لتكن min)، وحساب النطاق max-min-1.
2. إنشاء مصفوفة "أبراج الحمام" فارغة ذات حجم مساوٍ للنطاق المحسوب في الخطوة السابقة.
3. الوصول إلى كل عنصر في المصفوفة ووضعه في برج الحمام الخاص به. يوضع العنصر arr[i]‎ في الخانة ذات الموقع arr[i] - min.
4. تنفيذ حلقة تكرارية تمر على جميع العناصر في مصفوفة أبراج الحمام بالترتيب وتعيد العناصر من الخانات غير الفارغة إلى المصفوفة الأصلية.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

void pigeonholeSort(int arr[], int n) 
{ 
	// إيجاد القيمتين العظمى والصغرى في المصفوفة المعطاة 
	int min = arr[0], max = arr[0]; 
	for (int i = 1; i < n; i++) 
	{ 
		if (arr[i] < min) 
			min = arr[i]; 
		if (arr[i] > max) 
			max = arr[i]; 
	} 
	int range = max - min + 1; // حساب النطاق

	// إنشاء مصفوفة من المتجهات. حجم المصفوفة يساوي النطاق المحسوب
	// في الخطوة السابقة. يمثل كل متجه خانة ستحتوي على العناصر المطابقة
	vector<int> holes[range]; 

	// المرور على عناصر المصفوفة المدخلة
	// ووضع كل عنصر في الخانة الخاصة به
	for (int i = 0; i < n; i++) 
		holes[arr[i]-min].push_back(arr[i]); 

	// المرور على جميع الخانات واحدة تلو الأخرى
	// تعاد عناصر كلّ خانة إلى المصفوفة
	int index = 0; // موقع العنصر في المصفوفة المرتبة
	for (int i = 0; i < range; i++) 
	{ 
	vector<int>::iterator it; 
	for (it = holes[i].begin(); it != holes[i].end(); ++it) 
			arr[index++] = *it; 
	} 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int arr[] = {8, 3, 2, 7, 4, 6, 8}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	pigeonholeSort(arr, n); 

	printf("Sorted order is : "); 
	for (int i = 0; i < n; i++) 
		printf("%d ", arr[i]); 

	return 0; 
}

• بايثون:

def pigeonhole_sort(a): 
	# حجم نطاق القيم في القائمة
	# أي عدد أبراج الحمام المطلوبة
	my_min = min(a) 
	my_max = max(a) 
	size = my_max - my_min + 1

	# قائمة أبراج الحمام
	holes = [0] * size 

	# إضافة العناصر إلى أبراج الحمام
	for x in a: 
		assert type(x) is int, "integers only please"
		holes[x - my_min] += 1

	# إعادة العناصر إلى المصفوفة بالترتيب
	i = 0
	for count in range(size): 
		while holes[count] > 0: 
			holes[count] -= 1
			a[i] = count + my_min 
			i += 1
			

a = [8, 3, 2, 7, 4, 6, 8] 
print("Sorted order is : ", end = ' ') 

pigeonhole_sort(a) 
		
for i in range(0, len(a)): 
	print(a[i], end = ' ')

• جافا:

import java.lang.*; 
import java.util.*; 

public class GFG 
{ 
	public static void pigeonhole_sort(int arr[], int n) 
	{ 
		// إيجاد القيمتين العظمى والصغرى في المصفوفة المعطاة
		int min = arr[0]; 
		int max = arr[0]; 
		int range, i, j, index; 

		for(int a=0; a<n; a++) 
		{ 
			if(arr[a] > max) 
				max = arr[a]; 
			if(arr[a] < min) 
				min = arr[a]; 
		} 

		range = max - min + 1; // حساب النطاق
		int[] phole = new int[range]; 
		Arrays.fill(phole, 0); 
    	// المرور على عناصر المصفوفة المدخلة
	    // ووضع كل عنصر في الخانة الخاصة به
		for(i = 0; i<n; i++) 
			phole[arr[i] - min]++; 
    	// المرور على جميع الخانات واحدة تلو الأخرى
    	// تعاد عناصر كلّ خانة إلى المصفوفة
		
		index = 0; // موقع العنصر في المصفوفة المرتبة

		for(j = 0; j<range; j++) 
			while(phole[j]-->0) 
				arr[index++]=j+min; 

	} 
    // اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		GFG sort = new GFG(); 
		int[] arr = {8, 3, 2, 7, 4, 6, 8}; 

		System.out.print("Sorted order is : "); 

		sort.pigeonhole_sort(arr,arr.length); 
		
		for(int i=0 ; i<arr.length ; i++) 
			System.out.print(arr[i] + " "); 
	} 

}

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(n + Range)‎ وتمثّل n عدد العناصر في المصفوفة المدخلة وRange عدد القيم المحتملة في المصفوفة.

مصادر

• صفحة Pigeonhole Sort في توثيق الخوارزميات في موقع GeeksforGeeks.