Algorithms/cocktail sort

خوارزمية الترتيب المخلوط Cocktail Sort هي تحوير على خوارزمية الترتيب بالفقاعات.

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

تجري عملية الترتيب في نفس المصفوفة in-place وهي عملية ترتيب مستقرّة stable.

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

تقسم كل دورة في خوارزمية الترتيب المخلوط إلى مرحلتين:

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

مثال:

لنفترض أنّ المصفوفة المراد ترتيبها هي: ‎(5 1 4 2 8 0 2)‎.

الدورة الأولى (من اليسار إلى اليمين):

(5 1 4 2 8 0 2) ? (1 5 4 2 8 0 2), Swap since 5 > 1
(1 5 4 2 8 0 2) ? (1 4 5 2 8 0 2), Swap since 5 > 4
(1 4 5 2 8 0 2) ? (1 4 2 5 8 0 2), Swap since 5 > 2
(1 4 2 5 8 0 2) ? (1 4 2 5 8 0 2)
(1 4 2 5 8 0 2) ? (1 4 2 5 0 8 2), Swap since 8 > 0
(1 4 2 5 0 8 2) ? (1 4 2 5 0 2 8), Swap since 8 > 2

سينتقل العنصر الأكبر في المصفوفة بعد الدورة الأولى إلى الموقع الأخير في المصفوفة:

الدورة الأولى (من اليمين إلى اليسار):

(1 4 2 5 0 2 8) ? (1 4 2 5 0 2 8)
(1 4 2 5 0 2 8) ? (1 4 2 0 5 2 8), Swap since 5 > 0
(1 4 2 0 5 2 8) ? (1 4 0 2 5 2 8), Swap since 2 > 0
(1 4 0 2 5 2 8) ? (1 0 4 2 5 2 8), Swap since 4 > 0
(1 0 4 2 5 2 8) ? (0 1 4 2 5 2 8), Swap since 1 > 0

سينتقل العنصر الأصغر في المصفوفة بعد الدورة الأولى إلى الموقع الأول في المصفوفة.

الدورة الثانية (من اليسار إل اليمين):

(0 1 4 2 5 2 8) ? (0 1 4 2 5 2 8)
(0 1 4 2 5 2 8) ? (0 1 2 4 5 2 8), Swap since 4 > 2
(0 1 2 4 5 2 8) ? (0 1 2 4 5 2 8)
(0 1 2 4 5 2 8) ? (0 1 2 4 2 5 8), Swap since 5 > 2

الدورة الثانية (من اليمين إلى اليسار):

(0 1 2 4 2 5 8) ? (0 1 2 2 4 5 8), Swap since 4 > 2

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

(0 1 2 2 4 5 8) ? (0 1 2 2 4 5 8)
(0 1 2 2 4 5 8) ? (0 1 2 2 4 5 8)

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

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

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

void CocktailSort(int a[], int n) 
{ 
	bool swapped = true; 
	int start = 0; 
	int end = n - 1; 

	while (swapped) { 
		// يستخدم هذا المتغير كإشارة عند الدخول في الحلقة التكرارية
		// يعاد تعريف قيمة هذا المتغير لأنّه قد يصبح قيمة صحيحة في دورة سابقة
		swapped = false; 

		// التنقل عبر المصفوفة من اليسار إلى اليمين
		// بنفس الطريقة المتبعة في خوارزمية الترتيب بالفقاعات
		for (int i = start; i < end; ++i) { 
			if (a[i] > a[i + 1]) { 
				swap(a[i], a[i + 1]); 
				swapped = true; 
			} 
		} 

		// إن لم تبدل الخوارزمية موقع أي عنصر فإنّ المصفوفة تكون مرتّبة
		if (!swapped) 
			break; 

		// وإلا، يعاد تعيين قيمة الإشارة ليكون بالإمكان
		// استخدامها في المرحلة القادمة
		swapped = false; 

		// تحريك نقطة النهاية إلى الخلف بمقدار واحد
		// وذلك لأن العنصر الموجود في نهاية المصفوفة قد أخذ موقعه الصحيح
		--end; 

		// التنقل عبر المصفوفة من اليمين إلى اليسار
		// مع إجراء المقارنة ذاتها من المرحلة السابقة
		for (int i = end - 1; i >= start; --i) { 
			if (a[i] > a[i + 1]) { 
				swap(a[i], a[i + 1]); 
				swapped = true; 
			} 
		} 

		// زيادة موقع البدء بمقدار واحد
		// وذلك لأن المرحلة الأخيرة قد حرّكت ثاني أصغر عنصر
		// إلى موقعه الصحيح في المصفوفة
		++start; 
	} 
} 

/* طباعة عناصر المصفوفة */
void printArray(int a[], int n) 
{ 
	for (int i = 0; i < n; i++) 
		printf("%d ", a[i]); 
	printf("\n"); 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int arr[] = { 5, 1, 4, 2, 8, 0, 2 }; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	CocktailSort(a, n); 
	printf("Sorted array :\n"); 
	printArray(a, n); 
	return 0; 
}

• بايثون:

def cocktailSort(a): 
	n = len(a) 
	swapped = True
	start = 0
	end = n-1
	while (swapped == True): 

		# يستخدم هذا المتغير كإشارة عند الدخول في الحلقة التكرارية
		# يعاد تعريف قيمة هذا المتغير لأنّه قد يصبح قيمة صحيحة في دورة سابقة
		swapped = False

		# التنقل عبر المصفوفة من اليسار إلى اليمين
		#  بنفس الطريقة المتبعة في خوارزمية الترتيب بالفقاعات
		for i in range (start, end): 
			if (a[i] > a[i + 1]) : 
				a[i], a[i + 1]= a[i + 1], a[i] 
				swapped = True

		# إن لم تبدل الخوارزمية موقع أي عنصر فإنّ المصفوفة تكون مرتّبة
		if (swapped == False): 
			break

		# وإلا، يعاد تعيين قيمة الإشارة ليكون بالإمكان
		# استخدامها في المرحلة القادمة
		swapped = False

		# تحريك نقطة النهاية إلى الخلف بمقدار واحد
		# وذلك لأن العنصر الموجود في نهاية المصفوفة قد أخذ موقعه الصحيح
		end = end-1

		# التنقل عبر المصفوفة من اليمين إلى اليسار 
		# مع إجراء المقارنة ذاتها من المرحلة السابقة 
		for i in range(end-1, start-1, -1): 
			if (a[i] > a[i + 1]): 
				a[i], a[i + 1] = a[i + 1], a[i] 
				swapped = True

		# زيادة موقع البدء بمقدار واحد
		# وذلك لأن المرحلة الأخيرة قد حرّكت ثاني أصغر عنصر
		# إلى موقعه الصحيح في المصفوفة 
		start = start + 1

# طباعة عناصر المصفوفة 
a = [5, 1, 4, 2, 8, 0, 2] 
cocktailSort(a) 
print("Sorted array is:") 
for i in range(len(a)): 
	print ("% d" % a[i]),

• جافا:

public class CocktailSort { 
	void cocktailSort(int a[]) 
	{ 
		boolean swapped = true; 
		int start = 0; 
		int end = a.length; 

		while (swapped == true) { 
			// يستخدم هذا المتغير كإشارة عند الدخول في الحلقة التكرارية
			// يعاد تعريف قيمة هذا المتغير لأنّه قد يصبح قيمة صحيحة في دورة سابقة 
			swapped = false; 

			// التنقل عبر المصفوفة من اليسار إلى اليمين 
			//  بنفس الطريقة المتبعة في خوارزمية الترتيب بالفقاعات 
			for (int i = start; i < end - 1; ++i) { 
				if (a[i] > a[i + 1]) { 
					int temp = a[i]; 
					a[i] = a[i + 1]; 
					a[i + 1] = temp; 
					swapped = true; 
				} 
			} 

			// إن لم تبدل الخوارزمية موقع أي عنصر فإنّ المصفوفة تكون مرتّبة
			if (swapped == false) 
				break; 

			// وإلا، يعاد تعيين قيمة الإشارة ليكون بالإمكان
			// استخدامها في المرحلة القادمة
			swapped = false; 

			//  تحريك نقطة النهاية إلى الخلف بمقدار واحد
			// وذلك لأن العنصر الموجود في نهاية المصفوفة قد أخذ موقعه الصحيح
			end = end - 1; 

			// التنقل عبر المصفوفة من اليمين إلى اليسار 
			// مع إجراء المقارنة ذاتها من المرحلة السابقة
			for (int i = end - 1; i >= start; i--) { 
				if (a[i] > a[i + 1]) { 
					int temp = a[i]; 
					a[i] = a[i + 1]; 
					a[i + 1] = temp; 
					swapped = true; 
				} 
			} 

			// زيادة موقع البدء بمقدار وحد
			// وذلك لأن المرحلة الأخيرة قد حرّكت ثاني أصغر عنصر
			// إلى موقعه الصحيح في المصفوفة
			start = start + 1; 
		} 
	} 

	/* طباعة عناصر المصفوفة */
	void printArray(int a[]) 
	{ 
		int n = a.length; 
		for (int i = 0; i < n; i++) 
			System.out.print(a[i] + " "); 
		System.out.println(); 
	} 

	// اختبار الدوال السابقة
	public static void main(String[] args) 
	{ 
		CocktailSort ob = new CocktailSort(); 
		int a[] = { 5, 1, 4, 2, 8, 0, 2 }; 
		ob.cocktailSort(a); 
		System.out.println("Sorted array"); 
		ob.printArray(a); 
	} 
}

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

Sorted array is:
0 1 2 2 4 5 8

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

يبلغ التعقيد الزمني لهذه الخوارزمية في الحالة السوأى المقدار O(n^2)‎، ويبلغ في الحالة الفضلى المقدار O(n)‎ وهي الحالة التي تكون فيها المصفوفة مرتبة أصلًا.

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

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

التعقيد الزمني لكلا الخوارزميتين متساوٍ، ولكنّ خوارزمية الترتيب المخلوط تؤدي أداءً أفضل من خوارزمية الترتيب بالفقاعات، وتكون خوارزمية الترتيب المخلوط أسرع بمرتين عادة من خوارزمية الترتيب بالفقاعات، فلترتيب المصفوفة ‎(2, 3, 4, 5, 1)‎ تحتاج خوارزمية الترتيب بالفقاعات إلى المرور على المصفوفة أربع مرات، أما خوارزمية الترتيب المخلوط فستمرّ على هذه المصفوفة مرتين فقط.

مصادر

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