Algorithms/radix sort

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

أما خوارزمية الترتيب بالعد Counting Sort فهي خوارزمية خطية (التعقيد الزمني لها هو O(n+k)‎ عندما تكون العناصر ضمن النطاق 1 إلى k.

لا يمكن استخدام خوارزمية الترتيب بالعدّ ضمن النطاق 1 إلى n2 وذلك لأن التعقيد الزمني سيصبح O(n2)‎ وهو أسوأ من التعقيد الزمني لخوارزميات الترتيب التي تعتمد على المقارنة.

يمكن إجراء هذا النوع من الترتيب (أي ضمن النطاق 1 إلى n2) باستخدام خوارزمية الترتيب بالجذر Radix Sort.

تتلخص هذه الخوارزمية بإجراء ترتيب للعناصر رقمًا تلو الآخر بدءًا من الرقم الأقل أهمية إلى الرقم الأكثر أهمية. تستخدم خوارزمية الترتيب بالجذر خوارزمية الترتيب بالعد counting sort كدالة فرعية في عملية الترتيب.

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

تؤدي الخوارزمية الخطوة التالية لكل عدد i بحيث تتغير قيمة i من الرقم الأقل أهمية إلى الرقم الأكثر أهمية:

ترتيب مدخلات المصفوفة باستخدام خوارزمية الترتيب بالعد (أو أي خوارزمية ثابتة أخرى) بالاعتماد على ترتيب i.

يمكن توضيح طريقة عمل الخوارزمية بالمثال التالي:

لنفترض أن لدينا المصفوفة التالية (مصفوفة غير مرتبة):

170, 45, 75, 90, 802, 24, 2, 66

تعطي عملية ترتيب العناصر بدءًا من العنصر الأقل أهمية (الآحاد) النتيجة التالية: (لاحظ أنّنا أبقينا على 802 قبل 2 وذلك لأنّ 802 أتت قبل 2 في المصفوفة الأصلية، وكذلك الأمر بالنسبة للأزواج 170 و 90، و 45 و 75).

170, 90, 802, 2, 24, 45, 75, 66

نرتّب العناصر الآن بالاعتماد على الرقم التالي (العشرات) فتكون النتيجة: (لاحظ أنّ 802 أتت مرة أخرى قبل 2 وذلك لأنّ 802 قد أتت قبل 2 في المصفوفة السابقة).

802, 2, 24, 45, 66, 170, 75, 90

نرتّب العناصر الآن بالاعتماد على الرقم الأكثر أهمية (المئات) فتكون النتيجة:

2, 24, 45, 66, 75, 90, 170, 802

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

لنفترض أنّ لدينا d من الأعداد في المدخلات. تستغرق خوارزمية الترتيب بالجذر الزمن O(d*(n+b))‎ وb هي الأساس المستخدم لتمثيل الأرقام، فمثلًا قيمة b هي ‎10.‎ في النظام العشري. إن كانت k هي أكبر قيمة ممكنة، فإنّ قيمة d ستكون O(logb(k))‎؛ لذا فإنّ التعقيد الزمني الكلي سيكون O((n+b) * logb(k))‎، والذي يبدو أكبر من التعقيد الزمني لخوارزميات الترتيب المعتمدة على المقارنة عندما تكون قيمة k كبيرة.

لو حدّدنا قيمة k لتصبح k <= nc و(c هو ثابت) فإنّ التعقيد الزمني لهذه الخوارزمية يصبح O(nLogb(n))‎، ولكنّه لا يزال أعلى من التعقيد الزمني لخوارزميات الترتيب المعتمدة على على المقارنة.

إن كانت قيمة b هي n فإنّ التعقيد الزمني سيصبح O(n)‎، وبعبارة أخرى، يمكن ترتيب عناصر مصفوفة من الأعداد الصحيحة ضمن النطاق 1 إلى nc إن كانت الأعداد ممثّلة على الأساس n (أو أي عدد يأخذ log2(n)‎ من البتات).

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

أمثلة

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

توخيًا للسهولة، فإنّ الأمثلة التالية تفترض أنّ قيمة d هي ‎10‎. ينصح بمراجعة خوارزمية الترتيب بالعدّ للاطلاع على المزيد من التفاصيل حول الدالة countSort()‎ المستخدمة في الأمثلة التالية:

• C++‎:

#include<iostream> 
using namespace std; 

// دالة مساعدة مهمتها الحصول على القيمة العظمى في المصفوفة المعطى
int getMax(int arr[], int n) 
{ 
	int mx = arr[0]; 
	for (int i = 1; i < n; i++) 
		if (arr[i] > mx) 
			mx = arr[i]; 
	return mx; 
} 

// الدالة المسؤولة عن إجراء عملية الترتيب بالعد للمصفوفة المعطاة
// exp بالاعتماد على الأس المعطى
void countSort(int arr[], int n, int exp) 
{ 
	int output[n]; // مصفوفة المخرجات
	int i, count[10] = {0}; 

	// count[] البدء بعدّ المرات التي تظهر فيها العناصر الموجودة في المصفوفة
	for (i = 0; i < n; i++) 
		count[ (arr[i]/exp)%10 ]++; 

	// تغيير قيمة العنصر
	// count[i]
	// ليتضمّن الآن الموقع الفعلي لهذا العدد في مصفوفة المخرجات
	for (i = 1; i < 10; i++) 
		count[i] += count[i - 1]; 

	// بناء مصفوفة المخرجات
	for (i = n - 1; i >= 0; i--) 
	{ 
		output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
		count[ (arr[i]/exp)%10 ]--; 
	} 
	
	// arr[] نسخ محتويات مصفوفة المخرجات إلى المصفوفة المعطاة
	// لتتضمن الآن الأعداد المرتّبة بالاعتماد على العدد الحالي
	
	for (i = 0; i < n; i++) 
		arr[i] = output[i]; 
} 

// الدالة المسؤولة عن إجراء عملية الترتيب بالجذر على المصفوفة المعطاة والتي تمتلك الحجم المعطى
void radixsort(int arr[], int n) 
{ 
	// إيجاد العدد الأقصى من الأعداد لمعرفة عدد الأرقام الموجودة في المصفوفة
	int m = getMax(arr, n); 

	// إجراء عملية الترتيب بالعدّ لكل رقم في المصفوفة المعطاة
	// لاحظ تمرير الأس عوضًا عن الرقم
	// i الرقم الحالي هو 
	for (int exp = 1; m/exp > 0; exp *= 10) 
		countSort(arr, n, exp); 
} 

// دالة مساعدة لطباعة محتويات المصفوفة
void print(int arr[], int n) 
{ 
	for (int i = 0; i < n; i++) 
		cout << arr[i] << " "; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	radixsort(arr, n); 
	print(arr, n); 
	return 0; 
}

• بايثون:

# الدالة المسؤولة عن عملية الترتيب بالعدّ على المصفوفة المعطاة
# exp بالاعتماد على الأس المعطى
def countingSort(arr, exp1): 

	n = len(arr) 

	# مصفوفة المخرجات والتي ستتضمّن المصفوفة المعطاة بعد ترتيبها
	output = [0] * (n) 

	# تهيئة مصفوفة العد لتكون صفرًا
	count = [0] * (10) 

	# count[] تخزين تعداد ظهور العنصر في المصفوفة
	for i in range(0, n): 
		index = (arr[i]/exp1) 
		count[ (index)%10 ] += 1
	
	# تغيير قيمة العنصر
	# count[i]
	# ليتضمّن الآن الموقع الفعلي لهذا العدد في مصفوفة المخرجات
	for i in range(1,10): 
		count[i] += count[i-1] 

	# بناء مصفوفة المخرجات
	i = n-1
	while i>=0: 
		index = (arr[i]/exp1) 
		output[ count[ (index)%10 ] - 1] = arr[i] 
		count[ (index)%10 ] -= 1
		i -= 1

	# arr[] نسخ محتويات مصفوفة المخرجات إلى المصفوفة 
	# 
	# Copying the output array to arr[], 
	# لتتضمن الآن الأعداد المرتّبة بالاعتماد على العدد الحالي
	i = 0
	for i in range(0,len(arr)): 
		arr[i] = output[i] 

# الدالة المسؤولة عن إجراء عملية الترتيب بالجذر
def radixSort(arr): 

	# إيجاد العدد الأقصى لمعرفة عدد الأرقام في المصفوفة
	max1 = max(arr) 

	# إجراء عملية الترتيب بالعدّ لكل رقم في المصفوفة.
	# لاحظ تمرير الأس عوضًا عن العدد
	# i العدد الحالي هو
	exp = 1
	while max1/exp > 0: 
		countingSort(arr,exp) 
		exp *= 10

# اختبار الدوال السابقة
arr = [ 170, 45, 75, 90, 802, 24, 2, 66] 
radixSort(arr) 

for i in range(len(arr)): 
	print(arr[i]),

• جافا:

import java.io.*; 
import java.util.*; 

class Radix { 

	// دالة مساعدة مهمتها الحصول على القيمة العظمى في المصفوفة المعطى
	static int getMax(int arr[], int n) 
	{ 
		int mx = arr[0]; 
		for (int i = 1; i < n; i++) 
			if (arr[i] > mx) 
				mx = arr[i]; 
		return mx; 
	} 

	// الدالة المسؤولة عن إجراء عملية الترتيب بالعد للمصفوفة المعطاة
// exp بالاعتماد على الأس المعطى 
	static void countSort(int arr[], int n, int exp) 
	{ 
		int output[] = new int[n]; // مصفوفة المخرجات 
		int i; 
		int count[] = new int[10]; 
		Arrays.fill(count,0); 

		// count[] تخزين تعداد ظهور العنصر في المصفوفة
		for (i = 0; i < n; i++) 
			count[ (arr[i]/exp)%10 ]++; 

		// تغيير قيمة العنصر
	// count[i]
	// ليتضمّن الآن الموقع الفعلي لهذا العدد في مصفوفة المخرجات 
		for (i = 1; i < 10; i++) 
			count[i] += count[i - 1]; 

		// بناء مصفوفة المخرجات
		for (i = n - 1; i >= 0; i--) 
		{ 
			output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
			count[ (arr[i]/exp)%10 ]--; 
		} 

		// arr[] نسخ محتويات مصفوفة المخرجات إلى المصفوفة المعطاة
	// لتتضمن الآن الأعداد المرتّبة بالاعتماد على العدد الحالي
		for (i = 0; i < n; i++) 
			arr[i] = output[i]; 
	} 

	// الدالة المسؤولة عن إجراء عملية الترتيب بالجذر على المصفوفة المعطاة والتي تمتلك الحجم المعطى 
	static void radixsort(int arr[], int n) 
	{ 
		// إيجاد العدد الأقصى من الأعداد لمعرفة عدد الأرقام الموجودة في المصفوفة
		int m = getMax(arr, n); 

		// إجراء عملية الترتيب بالعدّ لكل رقم في المصفوفة المعطاة
	// لاحظ تمرير الأس عوضًا عن الرقم
	// i الرقم الحالي هو 
		for (int exp = 1; m/exp > 0; exp *= 10) 
			countSort(arr, n, exp); 
	} 

	// دالة مساعدة لطباعة محتويات المصفوفة 
	static void print(int arr[], int n) 
	{ 
		for (int i=0; i<n; i++) 
			System.out.print(arr[i]+" "); 
	} 


	/* اختبار الدوال السابقة */
	public static void main (String[] args) 
	{ 
		int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; 
		int n = arr.length; 
		radixsort(arr, n); 
		print(arr, n); 
	} 
}

مصادر

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