عرض مصدر Algorithms/cycle sort

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

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

Cycle in arr[] = {2, 4, 5, 1, 3}

Cycle in arr[] = {4, 3, 2, 1}

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

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

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

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

<source lang="text">arr[] = {10, 5, 2, 3}
index =  0   1   2   3
cycle_start = 0 
item = 10 = arr[0]</source>
نبحث عن الموقع الذي نضع فيه العنصر:

<source lang="text">pos = cycle_start
while (arr[i] < item)  
    pos++;</source>
يوضع العنصر <code>10</code> في الموقع <code>arr[3]‎</code> وتغيير العنصر إلى القيمة القديمة للعنصر <code>arr[3]‎</code>.

<source lang="text">arr[] = {10, 5, 2, 10} 
item = 3 </source>
مرة أخرى تدوّر الدورة الباقية والتي تبدأ في الموقع <code>0</code>. إيجاد الموقع الذي يوضع فيه العنصر <code>3</code>.

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

<source lang="text">arr[] = {10, 3, 2, 10} 
item = 5</source>
مرة أخرى تدوّر الدورة الباقية والتي تبدأ في الموقع <code>0</code>. إيجاد الموقع الذي يوضع فيه العنصر <code>5</code>.

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

<source lang="text">arr[] = {10, 3, 5, 10 } 
item = 2</source>
مرة أخرى تدوّر الدورة الباقية والتي تبدأ في الموقع <code>0</code>. إيجاد الموقع الذي يوضع فيه العنصر <code>2</code>.

<source lang="text">arr[] = {2, 3,  5, 10}  </source>
يمثّل ما سبق دورة واحدة، وتعاد الخطوات السابقة للدورات المتبقية.

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

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

* C++‎:

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

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

<source lang="java">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] + " "); 
	} 
} </source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">1 2 3 4 8 9 10 10 </source>
== التعقيد الزمني ==

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

== مصادر ==

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

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