الترتيب بالدلو

تظهر فائدة خوارزمية الترتيب بالدلو Bucket Sort عندما تكون المدخلات موزّعة بانتظام ضمن نطاق معيّن، كما هو الحال في المسألة التالية:

كيف يمكن ترتيب مجموعة كبيرة من الأعداد العشرية ذات الفاصلة العائمة float point numbers والموجودة ضمن النطاق 0.0 و 1.0 والموزّعة فيه بانتظام؟

يمكن تطبيق إحدى الخوارزميات التي تعتمد على المقارنة في عملها مثل خوارزميات الترتيب بالدمج والترتيب بالكومة والترتيب السريع وغيرها، ويبلغ الحد الأدنى للتعقيد الزمني في هذه الخوارزميات المقدار Ω(n Log n)‎ أي أنّ هذه الخوارزميات لن تعمل بتعقيد زمني أفضل من هذا.

كذلك لا يمكن استخدام خوارزمية الترتيب بالعد وذلك لأنها تستخدم المفاتيح كمواقع، والمفاتيح في هذه المسألة هي أعداد عشرية.

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

تتبع خوارزمية الترتيب بالدول الخطوات التالية:

1. إنشاء n من الدلاء (أو القوائم) الفارغة.
2. تنفيذ ما يلي لكل عنصر في المصفوفة arr[i]‎.
   • إدراج العنصر arr[i]‎ في bucket[n*array[i]]‎.
3. ترتيب الدلاء المفردة باستخدام الترتيب بالإدراج.
4. ربط الدلاء المرتّبة بعضها ببعض.

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

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

• C++‎:

#include <iostream> 
#include <algorithm> 
#include <vector> 
using namespace std; 

// ترتب الدالة المصفوفة المعطاة باستخدام خوارزمية الترتيب بالدلو
void bucketSort(float arr[], int n) 
{ 
	// 1) إنشاء الدلاء الفارغة
	vector<float> b[n]; 

	// وضع كل عنصر في المصفوفة في دلو مختلف
	for (int i=0; i<n; i++) 
	{ 
	int bi = n*arr[i]; // الموقع في الدلو 
	b[bi].push_back(arr[i]); 
	} 

	// 3) ترتيب الدلاء منفردة
	for (int i=0; i<n; i++) 
	sort(b[i].begin(), b[i].end()); 

	// 4) ربط الدلاء بعضها ببعض في المصفوفة
	int index = 0; 
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < b[i].size(); j++) 
		arr[index++] = b[i][j]; 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	bucketSort(arr, n); 

	cout << "Sorted array is \n"; 
	for (int i=0; i<n; i++) 
	cout << arr[i] << " "; 
	return 0; 
}

• بايثون:

# ترتب الدالة المصفوفة المعطاة باستخدام خوارزمية الترتيب بالدلو
def insertionSort(b): 
	for i in range(1, len(b)): 
		up = b[i] 
		j = i - 1
		while j >=0 and b[j] > up: 
			b[j + 1] = b[j] 
			j -= 1
		b[j + 1] = up	 
	return b	 
			
def bucketSort(x): 
	arr = [] 
	slot_num = 10
	# 10 مواقع شاغرة حجم كل واحد منها هو 0.1
	for i in range(slot_num): 
		arr.append([]) 
		
	# وضع عناصر المصفوفة في دلاء مختلفة
	for j in x: 
		index_b = int(slot_num * j) 
		arr[index_b].append(j) 
	
	# ترتيب الدلاء منفردة
	for i in range(slot_num): 
		arr[i] = insertionSort(arr[i]) 
		
	# ربط الدلاء بعضها ببعض في المصفوفة
	# concatenate the result 
	k = 0
	for i in range(slot_num): 
		for j in range(len(arr[i])): 
			x[k] = arr[i][j] 
			k += 1
	return x 

# اختبار الدالة السابقة
x = [0.897, 0.565, 0.656, 
	0.1234, 0.665, 0.3434] 
print("Sorted Array is") 
print(bucketSort(x)) 

# This code is contributed by 
# Oneil Hsiao

• جافا:

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

لو فرضنا أن عملية الإدراج في الدلو تستغرق O(1)‎ من الوقت فإن الخطوتين الأولى والثاني من الخوارزمية ستستغرقان O(n)‎ من الوقت. يمكن الحصول على تعقيد زمني قدره O(1)‎ باستخدام القوائم المترابطة لتمثيل الدلو (تستخدم شيفرة C++‎ أعلاه المتجهات توخيًا للبساطة).

تستغرق الخطوة 4 O(n)‎ من الوقت كذلك وذلك لوجود n من العناصر في جميع الدلاء، كذلك تستغرق الخطوة 3 O(n)‎ من الوقت كمعدل إن كانت جميع الأعداد موزّعة بانتظام.

مصادر

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