Algorithms/odd even sort

خوارزمية الترتيب فردي-زوجي Odd-Even Sort (أو الترتيب بالقرميد Brick sort) هي تحوير على خوارزمية الترتيب بالفقاعات.

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

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

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

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

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

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

• 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); 
}

• بايثون:

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 = ' ')

• جافا:

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(" "); 
	} 
}

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

-9 2 10 34

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

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

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

مصادر

• صفحة Odd-Even sort في توثيق الخوارزميات في موقع GeeksforGeeks.