عرض مصدر Algorithms/odd even sort

<noinclude>{{DISPLAYTITLE:الترتيب فردي-زوجي (الترتيب بالقرميد)}}</noinclude>
خوارزمية الترتيب فردي-زوجي Odd-Even Sort (أو الترتيب بالقرميد Brick sort) هي تحوير على خوارزمية الترتيب بالفقاعات.

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

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

في الطور الفردي تنفّذ خوارزمية الترتيب بالفقاعات على العناصر ذات المواقع الفردية، وفي الطور الزوجي تنفّذ الخوارزمية على العناصر ذات المواقع الزوجية.

ترتّب هذه الخوارزمية عناصر المصفوفة في نفس المصفوفة in-place كما هو الحال مع خوارزمية الترتيب بالفقاعات. 

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

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

* C++‎:

<source lang="c++">#include<bits/stdc++.h> 
using namespace std; 

void oddEvenSort(int arr[], int n) 
{ 
	bool isSorted = false; // المصفوفة غير مرتبة في البداية

	while (!isSorted) 
	{ 
		isSorted = true; 

		// تنفيذ خوارزمية الترتيب بالفقاعات 
	    // على العناصر ذات المواقع الفردية
		for (int i=1; i<=n-2; i=i+2) 
		{ 
			if (arr[i] > arr[i+1]) 
			{ 
				swap(arr[i], arr[i+1]); 
				isSorted = false; 
			} 
		} 

		// تنفيذ خوارزمية الترتيب بالفقاعات 
	    // على العناصر ذات المواقع الزوجية
		for (int i=0; i<=n-2; i=i+2) 
		{ 
			if (arr[i] > arr[i+1]) 
			{ 
				swap(arr[i], arr[i+1]); 
				isSorted = false; 
			} 
		} 
	} 

	return; 
} 

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

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

	oddEvenSort(arr, n); 
	printArray(arr, n); 

	return (0); 
} 
</source>
* بايثون:

<source lang="python">def oddEvenSort(arr, n): 
	# المصفوفة غير مرتبة في البداية
	isSorted = 0
	while isSorted == 0: 
		isSorted = 1
		temp = 0
		
		# تنفيذ خوارزمية الترتيب بالفقاعات 
		# على العناصر ذات المواقع الفردية
		for i in range(1, n-1, 2): 
			if arr[i] > arr[i+1]: 
				arr[i], arr[i+1] = arr[i+1], arr[i] 
				isSorted = 0
        # تنفيذ خوارزمية الترتيب بالفقاعات 
        # على العناصر ذات المواقع الزوجية
		for i in range(0, n-1, 2): 
			if arr[i] > arr[i+1]: 
				arr[i], arr[i+1] = arr[i+1], arr[i] 
				isSorted = 0
	
	return


arr = [34, 2, 10, -9] 
n = len(arr) 

oddEvenSort(arr, n); 
for i in range(0, n): 
	print(arr[i], end = ' ') </source>
* جافا:

<source lang="java">import java.io.*; 

class GFG 
{ 
	public static void oddEvenSort(int arr[], int n) 
	{ 
		boolean isSorted = false; // المصفوفة غير مرتبة في البداية

		while (!isSorted) 
		{ 
			isSorted = true; 
			int temp =0; 

			// تنفيذ خوارزمية الترتيب بالفقاعات 
			//  على العناصر ذات المواقع الفردية
			for (int i=1; i<=n-2; i=i+2) 
			{ 
				if (arr[i] > arr[i+1]) 
				{ 
					temp = arr[i]; 
					arr[i] = arr[i+1]; 
					arr[i+1] = temp; 
					isSorted = false; 
				} 
			} 

			// تنفيذ خوارزمية الترتيب بالفقاعات 
			//  على العناصر ذات المواقع الزوجية
			for (int i=0; i<=n-2; i=i+2) 
			{ 
				if (arr[i] > arr[i+1]) 
				{ 
					temp = arr[i]; 
					arr[i] = arr[i+1]; 
					arr[i+1] = temp; 
					isSorted = false; 
				} 
			} 
		} 

		return; 
	} 
	public static void main (String[] args) 
	{ 
		int arr[] = {34, 2, 10, -9}; 
		int n = arr.length; 

		oddEvenSort(arr, n); 
		for (int i=0; i < n; i++) 
			System.out.print(arr[i] + " "); 

		System.out.println(" "); 
	} 
} </source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">-9 2 10 34 </source>
== التعقيد الزمني ==

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

تحتاج هذه الخوارزمية إلى مساحة ساندة قدرها <code>O(1)‎</code>.

== مصادر ==
* صفحة [https://www.geeksforgeeks.org/odd-even-sort-brick-sort/ Odd-Even sort] في توثيق الخوارزميات في موقع GeeksforGeeks.
[[تصنيف: الخوارزميات]]
[[تصنيف: خوارزميات الترتيب]]