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

ترتب خوارزمية الترتيب بالتدوير Cycle sort العناصر في مكانها in-place وهي خوارزمية ترتيب غير مستقرة وتعتمد على المقارنة التي تكون مثالية من الناحية النظرية بالنسبة إلى عدد مرات الكتابة في المصفوفة الأصلية، وهي مثالية كذلك من ناحية عدد مرات الكتابة في الذاكرة، إذ أنّ كل عنصر يُكتب في الذاكرة مرة واحدة إن لم يكن في مكانه الصحيح، وإما أن لا يكتب إطلاقًا إن كان في موقعه الصحيح).

مبدأ عمل هذه الخوارزمية هو أنّه لتكون المصفوفة مرتبة فيمكن تقسيمها إلى دورات، ويمكن تصوّر الدورات كرسم بياني، إذ يكون هناك n من العقد والأضلاع الموجّهة من العقدة i إلى العقدة j إن كان المفروض أن يكون العنصر في الموقع i موجودًا في الموقع j في المصفوفة المرتبة.

تكون خوارزمية الترتيب بالتدوير ملائمة في الحالات التي تكون فيها عملية الكتابة إلى الذاكرة أو عمليات التبديل swapping مكلفة.

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

يجري البحث عن الدورات في المصفوفة واحدة تلو الأخرى، إذ تبدأ الخوارزمية بالبحث عن الدورة الأولى والتي تتضمن العنصر الأول، ثم تبحث عن الموقع الصحيح لهذا العنصر في المصفوفة وتضعه فيه (ليكن j). ثم تنظر الخوارزمية في القيمة القديمة للعنصر arr[j]‎ وتبحث عن موقعه الصحيح في المصفوفة، وتستمر الخوارزمية في هذه الخطوات إلى توضع جميع العناصر في الدورة الحالية في مواقعها الصحيحة، أي عندما لا تعود الخوارزمية إلى تدوير العنصر الأول.

يوضّح المثال التالي الخطوات التي تتبعها الخوارزمية في ترتيب عناصر المصفوفة المدخلة:

arr[] = {10, 5, 2, 3}
index =  0   1   2   3
cycle_start = 0 
item = 10 = arr[0]

نبحث عن الموقع الذي نضع فيه العنصر:

pos = cycle_start
while (arr[i] < item)  
    pos++;

يوضع العنصر 10 في الموقع arr[3]‎ وتغيير العنصر إلى القيمة القديمة للعنصر arr[3]‎.

arr[] = {10, 5, 2, 10} 
item = 3

مرة أخرى تدوّر الدورة الباقية والتي تبدأ في الموقع 0. إيجاد الموقع الذي يوضع فيه العنصر 3.

يجري التبديل بين العنصر 3 والعنصر في الموقع arr[1]‎.

arr[] = {10, 3, 2, 10} 
item = 5

مرة أخرى تدوّر الدورة الباقية والتي تبدأ في الموقع 0. إيجاد الموقع الذي يوضع فيه العنصر 5.

يجري التبديل بين العنصر 3 والعنصر في الموقع arr[2]‎.

arr[] = {10, 3, 5, 10 } 
item = 2

مرة أخرى تدوّر الدورة الباقية والتي تبدأ في الموقع 0. إيجاد الموقع الذي يوضع فيه العنصر 2.

arr[] = {2, 3,  5, 10}

يمثّل ما سبق دورة واحدة، وتعاد الخطوات السابقة للدورات المتبقية.

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

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

• C++‎:

#include <iostream> 
using namespace std; 

void cycleSort(int arr[], int n) 
{ 
	// إحصاء عدد مرات الكتابة في الذاكرة
	int writes = 0; 

	// المرور على عناصر المصفوفة ووضعها في مواضعها الصحيحة
	for (int cycle_start = 0; cycle_start <= n - 2; cycle_start++) { 
		// تهيئة العنصر ليكون نقطة البداية
		int item = arr[cycle_start]; 

		// إيجاد الموقع الذي يوضع فيه العنصر
		// يجري تعداد جميع العناصر الأصغر على الجانب الأيمن من هذا العنصر
		int pos = cycle_start; 
		for (int i = cycle_start + 1; i < n; i++) 
			if (arr[i] < item) 
				pos++; 

		// إن كان العنصر في موقعه الصحيح أصلًا
		if (pos == cycle_start) 
			continue; 

		// تجاهل العناصر المكررة
		while (item == arr[pos]) 
			pos += 1; 

		// وضع العنصر في موقعه الصحيح
		if (pos != cycle_start) { 
			swap(item, arr[pos]); 
			writes++; 
		} 

		// تدوير بقية الدورة
		while (pos != cycle_start) { 
			pos = cycle_start; 

			// إيجاد الموقع الذي سيوضع فيه العنصر
			for (int i = cycle_start + 1; i < n; i++) 
				if (arr[i] < item) 
					pos += 1; 

			// تجاهل جميع العناصر المكرّرة
			while (item == arr[pos]) 
				pos += 1; 

			// وضع العنصر في موقعه الصحيح
			if (item != arr[pos]) { 
				swap(item, arr[pos]); 
				writes++; 
			} 
		} 
	} 

} 

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

	cout << "After sort : " << endl; 
	for (int i = 0; i < n; i++) 
		cout << arr[i] << " "; 
	return 0; 
}

• بايثون:

def cycleSort(array): 
writes = 0
	
# المرور على عناصر المصفوفة بحثًا عن الدورات
for cycleStart in range(0, len(array) - 1): 
	item = array[cycleStart] 
	
	# إيجاد الموقع الذي سيوضع فيه العنصر
	pos = cycleStart 
	for i in range(cycleStart + 1, len(array)): 
	if array[i] < item: 
		pos += 1
	
	# إن كان العنصر موجودًا في ذلك الموقع فلن تكون هناك دورة
	if pos == cycleStart: 
	continue
	
	# وإلا، فإنّ العنصر يوضع في ذلك الموقع أو إلى يمين العناصر المكررة 
	while item == array[pos]: 
	pos += 1
	array[pos], item = item, array[pos] 
	writes += 1
	
	# تدوير بقية الدورة
	while pos != cycleStart: 
		
	# إيجاد الموقع الذي سيوضع فيه العنصر

	pos = cycleStart 
	for i in range(cycleStart + 1, len(array)): 
		if array[i] < item: 
		pos += 1
		
	# وضع العنصر في ذلك الموقع أو إلى يمين العناصر المكررة
	while item == array[pos]: 
		pos += 1
	array[pos], item = item, array[pos] 
	writes += 1
	
return writes 
	
# اختبار الدالة السابقة
arr = [1, 8, 3, 9, 10, 10, 2, 4 ] 
n = len(arr) 
cycleSort(arr) 

print("After sort : ") 
for i in range(0, n) : 
	print(arr[i], end = ' ')

• جافا:

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

class GFG { 
	public static void cycleSort(int arr[], int n) 
	{ 
		// إحصاء عدد مرات الكتابة في الذاكرة
		int writes = 0; 

		// المرور على عناصر المصفوفة ووضعها في مواضعها الصحيحة 
		for (int cycle_start = 0; cycle_start <= n - 2; cycle_start++) { 
			// تهيئة العنصر ليكون نقطة البداية
			
			int item = arr[cycle_start]; 

			// إيجاد الموقع الذي يوضع فيه العنصر 
			// يجري تعداد جميع العناصر الأصغر على الجانب الأيمن من هذا العنصر 
			int pos = cycle_start; 
			for (int i = cycle_start + 1; i < n; i++) 
				if (arr[i] < item) 
					pos++; 

			// إن كان العنصر في موقعه الصحيح أصلًا 
			if (pos == cycle_start) 
				continue; 

			// تجاهل العناصر المكررة
			while (item == arr[pos]) 
				pos += 1; 

			// وضع العنصر في موقعه الصحيح
			if (pos != cycle_start) { 
				int temp = item; 
				item = arr[pos]; 
				arr[pos] = temp; 
				writes++; 
			} 

			// تدوير بقية الدورة 
			while (pos != cycle_start) { 
				pos = cycle_start; 

				// إيجاد الموقع الذي سيوضع فيه العنصر 
				for (int i = cycle_start + 1; i < n; i++) 
					if (arr[i] < item) 
						pos += 1; 

				// تجاهل جميع العناصر المكرّرة 
				while (item == arr[pos]) 
					pos += 1; 

				// وضع العنصر في موقعه الصحيح
				if (item != arr[pos]) { 
					int temp = item; 
					item = arr[pos]; 
					arr[pos] = temp; 
					writes++; 
				} 
			} 
		} 
	} 

	// اختبار التابع السابق 
	public static void main(String[] args) 
	{ 
		int arr[] = { 1, 8, 3, 9, 10, 10, 2, 4 }; 
		int n = arr.length; 
		cycleSort(arr, n); 

		System.out.println("After sort : "); 
		for (int i = 0; i < n; i++) 
			System.out.print(arr[i] + " "); 
	} 
}

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

1 2 3 4 8 9 10 10

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

يبلغ التعقيد الزمني لخوارزمية الترتيب بالتدوير المقدار O(n^2)‎.

مصادر

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