Algorithms/counting sort

الترتيب بالعد Counting sort هو إحدى خوارزميات الترتيب التي تستند على المفاتيح الموجودة في نطاق محدد. تعمل هذه الخوارزمية عن طريق حساب عد العناصر التي تمتلك قيمة مفتاح فريدة، ثم حساب موقع كل عنصر في التسلسل المخرج.

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

لنفترض أنّ لدينا المدخلات التالية وهي ضمن النطاق 1 إلى 9.

1, 4, 1, 2, 7, 5, 2

1) ننشئ مصفوفة لتخزين عدد المرات التي يتكرر فيها كل عنصر فريد

  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  2  0   1  1  0  1  0  0

2) تعديل مصفوفة العد بطريقة تجعل كل موقع يخزّن مجموع المعدودات السابقة

  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  4  4  5  6  6  7  7  7

تحدّد مصفوفة المعدودات المعدّلة موقع كل عنصر في التسلسل المخرج.

3) إخراج كل عنصر في التلسلسل متبوعًا بإنقاص تعداده بمقدار 1.
معالجة البيانات المدخلة: ‎1, 3, 1, 2, 7, 5, 2‎.

وضع العنصر 1 في الموقع 2 في المخرجات، وتخفيض تعداده بمقدار 1 لوضع العنصر التالي في البيانات وهو 1 في موقع أقلّ من الموقع الحالي بمقدار 1.

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

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

• C++‎:

#include<bits/stdc++.h> 
#include<string.h> 
using namespace std; 
#define RANGE 255 

// الدالة الرئيسية التي ترتّب المصفوفة المعطاة ترتيبًا أبجديًّا
void countSort(char arr[]) 
{ 
	// المصفوفة التي ستعرض كمخرجات هذه الخوارزمية
	// والتي تتضمّن الحروف المرتّبة أبجديًّا
	char output[strlen(arr)]; 

	// إنشاء مصفوفة للعد وذلك لتخزين تعداد كل حرفٍ
	// في المصفوفة وتهيئة القيمة الأولية للتعداد لتكون صفرًا
	int count[RANGE + 1], i; 
	memset(count, 0, sizeof(count)); 

	// تخزين تعداد كل عنصر
	for(i = 0; arr[i]; ++i) 
		++count[arr[i]]; 

	// تغيير قيمة العنصر لتكون الموقع الحقيقي
	// للحرف الحالي في مصفوفة المخرجات
	for (i = 1; i <= RANGE; ++i) 
		count[i] += count[i-1]; 

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

	// arr نسخ مصفوفة المخرجات إلى المصفوفة
	// لتتضمّن هذه المصفوفة الحروف المرتّبة
	for (i = 0; arr[i]; ++i) 
		arr[i] = output[i]; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	char arr[] = "geeksforgeeks"; 

	countSort(arr); 

	cout<< "Sorted character array is " << arr; 
	return 0; 
}

• بايثون:

# الدالة الرئيسية التي ترتّب السلسلة النصية المعطاة ترتيبًا أبجديًّا
def countSort(arr): 

	# مصفوفة المخرجات التي ستتضمّن الحروف مرتّبةً
	output = [0 for i in range(256)] 

	
	# إنشاء مصفوفة للعد وذلك لتخزين تعداد كل حرفٍ 
	#  في المصفوفة وتهيئة القيمة الأولية للتعداد لتكون صفرًا 
	count = [0 for i in range(256)] 

	# تستخدم هذه القائمة لتخزين النتيجة
	# وذلك لأنّ السلاسل النصية غير قابلة للتغيير في بايثون
	ans = ["" for _ in arr] 

	# تخزين تعداد كل عنصر
	for i in arr: 
		count[ord(i)] += 1

	
	# تغيير قيمة العنصر لتكون الموقع الحقيقي
	# للحرف الحالي في مصفوفة المخرجات 
	for i in range(256): 
		count[i] += count[i-1] 

	# بناء مصفوفة المخرجات
	for i in range(len(arr)): 
		output[count[ord(arr[i])]-1] = arr[i] 
		count[ord(arr[i])] -= 1

	# arr نسخ مصفوفة المخرجات إلى القائمة
	# لتتضمّن هذه القائمة الحروف المرتّبة
	for i in range(len(arr)): 
		ans[i] = output[i] 
	return ans 

# اختبار الدوال السابقة
arr = "geeksforgeeks"
ans = countSort(arr) 
print "Sorted character array is %s" %("".join(ans))

• جافا:

class CountingSort 
{ 
	void sort(char arr[]) 
	{ 
		int n = arr.length; 

		// المصفوفة التي ستعرض كمخرجات هذه الخوارزمية
		// والتي تتضمّن الحروف المرتّبة أبجديًّا 
		char output[] = new char[n]; 

		// إنشاء مصفوفة للعد وذلك لتخزين تعداد كل حرفٍ
		// في المصفوفة وتهيئة القيمة الأولية للتعداد لتكون صفرًا
		int count[] = new int[256]; 
		for (int i=0; i<256; ++i) 
			count[i] = 0; 

		// تخزين تعداد كل عنصر
		for (int i=0; i<n; ++i) 
			++count[arr[i]]; 

		// تغيير قيمة العنصر لتكون الموقع الحقيقي
		// للحرف الحالي في مصفوفة المخرجات
		for (int i=1; i<=255; ++i) 
			count[i] += count[i-1]; 

		// بناء مصفوفة المخرجات
		// تنفّذ العملية التالية
		// بترتيب معكوس  طلبًا للاستقرار 
		for (int i = n-1; i>=0; i--) 
		{ 
			output[count[arr[i]]-1] = arr[i]; 
			--count[arr[i]]; 
		} 

		// arr نسخ مصفوفة المخرجات إلى المصفوفة
		// لتتضمّن هذه المصفوفة الحروف المرتّبة 
		for (int i = 0; i<n; ++i) 
			arr[i] = output[i]; 
	} 

	// اختبار التابع السابق 
	public static void main(String args[]) 
	{ 
		CountingSort ob = new CountingSort(); 
		char arr[] = {'g', 'e', 'e', 'k', 's', 'f', 'o', 
					'r', 'g', 'e', 'e', 'k', 's'
					}; 

		ob.sort(arr); 

		System.out.print("Sorted character array is "); 
		for (int i=0; i<arr.length; ++i) 
			System.out.print(arr[i]); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

Sorted character array is eeeefggkkorss

تنفيذ الخوارزمية مع المصفوفات ذات القيم السالبة

لا يمكن استخدام طريقة التنفيذ السابقة في ترتيب المصفوفات التي تحتوي على عناصر ذات قيم سالبة؛ وذلك لعدم وجود مواقع ذات قيم سالبة في المصفوفة؛ لذا سنعثر على العنصر الأصغر في المصفوفة وسنخزّن تعداد ذلك العنصر في الموقع 0.

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

//Counting sort which takes negative numbers as well 
#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

void countSort(vector <int>& arr) 
{ 
	int max = *max_element(arr.begin(), arr.end()); 
	int min = *min_element(arr.begin(), arr.end()); 
	int range = max - min + 1; 
	
	vector<int> count(range), output(arr.size()); 
	for(int i = 0; i < arr.size(); i++) 
		count[arr[i]-min]++; 
		
	for(int i = 1; i < count.size(); i++) 
		count[i] += count[i-1]; 
	
	for(int i = arr.size()-1; i >= 0; i--) 
	{ 
		output[ count[arr[i]-min] -1 ] = arr[i]; 
			count[arr[i]-min]--; 
	} 
	
	for(int i=0; i < arr.size(); i++) 
			arr[i] = output[i]; 
} 

void printArray(vector <int> & arr) 
{ 
	for (int i=0; i < arr.size(); i++) 
		cout << arr[i] << " "; 
	cout << "\n"; 
} 

int main() 
{ 
	vector<int> arr = {-5, -10, 0, -3, 8, 5, -1, 10}; 
	countSort (arr); 
	printArray (arr); 
	return 0; 
} 
‎

• جافا:

import java.util.*; 

class GFG 
{ 

	static void countSort(int[] arr) 
	{ 
		int max = Arrays.stream(arr).max().getAsInt(); 
		int min = Arrays.stream(arr).min().getAsInt(); 
		int range = max - min + 1; 
		int count[] = new int[range]; 
		int output[] = new int[arr.length]; 
		for (int i = 0; i < arr.length; i++) 
		{ 
			count[arr[i] - min]++; 
		} 

		for (int i = 1; i < count.length; i++) 
		{ 
			count[i] += count[i - 1]; 
		} 

		for (int i = arr.length - 1; i >= 0; i--) 
		{ 
			output[count[arr[i] - min] - 1] = arr[i]; 
			count[arr[i] - min]--; 
		} 

		for (int i = 0; i < arr.length; i++) 
		{ 
			arr[i] = output[i]; 
		} 
	} 

	static void printArray(int[] arr) 
	{ 
		for (int i = 0; i < arr.length; i++) 
		{ 
			System.out.print(arr[i] + " "); 
		} 
		System.out.println(""); 
	} 

	// اختبار الشيفرة
	public static void main(String[] args) 
	{ 
		int[] arr = {-5, -10, 0, -3, 8, 5, -1, 10}; 
		countSort(arr); 
		printArray(arr); 
	} 
} 

// This code is contributed by princiRaj1992

تعطي الشيفرات السابقة المخرجات التالية:

-10 -5 -3 -1 0 5 8 10

ملاحظات:

1. خوارزمية الترتيب بالعد فعّالة عندما لا يكون نطاق البيانات المدخلة أكبر من عدد العناصر المراد ترتيبها بفارق كبير. لاحظ الحالة التي يكون نطاق البيانات المدخلة فيها بين 1 و 10,000 والبيانات المدخلة هي 10، 5، 10,000 و 5000.
2. لا تعتمد هذه الخوارزمية في عملها على عقد المقارنات؛ لذا يكون التعقيد الزمني لها هو O(n)‎ وتتناسب المساحة التي تشغلها مع نطاق البيانات المعطى تناسبًا طرديًّا.
3. تستخدم هذه الخوارزمية عادةً كدالة فرعية في خوارزميات ترتيب أخرى مثل خوارزمية الترتيب بالجذر radix sort.
4. تستخدم خوارزمية الترتيب بالعدّ تقطيعًا جزئيًا لحساب عدد مرات ظهور كائن بيانات معين وبتعقيد زمني قدره O(1)‎.
5. يمكن تمديد نطاق عمل الخوارزمية ليشمل المدخلات السالبة أيضًا.

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

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

مصادر

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