عرض مصدر Algorithms/pigeonhole sort

<noinclude>{{DISPLAYTITLE:الترتيب ببرج الحمام}}</noinclude>
تلائم خوارزمية الترتيب ببرج الحمام Pigeonhole sort قوائم العناصر التي يكون فيها عدد العناصر وعدد القيم المفتاحية الممكنة possible key values متساويين تقريبًا.

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

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

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

# إيجاد القيمتين العظمى (لتكن <code>max</code>) والصغرى (لتكن <code>min</code>)، وحساب النطاق <code>max-min-1</code>.
# إنشاء مصفوفة &quot;أبراج الحمام&quot; فارغة ذات حجم مساوٍ للنطاق المحسوب في الخطوة السابقة.
# الوصول إلى كل عنصر في المصفوفة ووضعه في برج الحمام الخاص به. يوضع العنصر <code>arr[i]‎</code> في الخانة ذات الموقع <code>arr[i] - min</code>.
# تنفيذ حلقة تكرارية تمر على جميع العناصر في مصفوفة أبراج الحمام بالترتيب وتعيد العناصر من الخانات غير الفارغة إلى المصفوفة الأصلية.

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

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

* C++‎:

<source lang="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; 
} 
</source>
* بايثون:

<source lang="python">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 = ' ') 
	
</source>
* جافا:

<source lang="java">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] + " "); 
	} 

} </source>
== التعقيد الزمني ==

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

== مصادر ==

* صفحة [https://www.geeksforgeeks.org/pigeonhole-sort/ Pigeonhole Sort] في توثيق الخوارزميات في موقع GeeksforGeeks.

[[تصنيف: الخوارزميات]]
[[تصنيف: خوارزميات الترتيب]]