الترتيب بالفقاعات

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

مثال:

الدورة الأولى:

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), تقارن الخوارزمية هنا أول قيمتين في المصفوفة، وتبدّل مكانيهما لأنّ 5 > 1
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), إجراء عملية التبديل لأنّ 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), إجراء عملية التبديل لأنّ 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), أصبح ترتيب العنصرين صحيحًا الآن ولن تجري الخوارزمية عملية التبديل لأنّ 5 < 8

الدورة الثانية:

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), إجراء عملية التبديل لأنّ 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

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

الدورة الثالثة:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

نظرًا لبساطة هذه الخوارزمية فإنّها تستخدم غالبًا في التعريف بمفهوم خوارزميات الترتيب. ويشيع استخدام هذه الخوارزمية في رسومات الحاسب حيث تستطيع هذه الخوارزمية الكشف عن الأخطاء الصغيرة جدًّا (مثل التبديل بين عنصرين فقط) في المصفوفات المرتّبة تقريبًا وتصحيح هذه الأخطاء بتعقيد زمني خطّي (2n).

فعلى سبيل المثال تستخدم هذه الخوارزمية في خوارزمية تعبئة المضلّع polygon filling algorithm، حيث ترتّب الخطوط الرابطة bounding lines بحسب إحداثياتها السينية على خط مسح scan line معيّن (خطّ موازٍ للمحور x) وبزيادة قيمة الإحداثي الصادي يتغير ترتيب الخطوط الرابطة (يحصل تبديل بين عنصرين) فقط عند تقاطع خطين مع بعضهما البعض.

أمثلة

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

• C++‎:

#include <stdio.h> 

void swap(int *xp, int *yp) 
{ 
	int temp = *xp; 
	*xp = *yp; 
	*yp = temp; 
} 

void bubbleSort(int arr[], int n) 
{ 
int i, j; 
for (i = 0; i < n-1; i++)	 

	for (j = 0; j < n-i-1; j++) 
		if (arr[j] > arr[j+1]) 
			swap(&arr[j], &arr[j+1]); 
} 

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

int main() 
{ 
	int arr[] = {64, 34, 25, 12, 22, 11, 90}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	bubbleSort(arr, n); 
	printf("Sorted array: \n"); 
	printArray(arr, n); 
	return 0; 
}

• بايثون:

def bubbleSort(arr): 
	n = len(arr) 

	# ألتنقل عبر جميع عناصر المصفوفة
	for i in range(n): 

		for j in range(0, n-i-1): 

			# التنقل عبر المصفوفة من الموقع 0 إلى الموقع
            # n-i-1
            # إجراء عملية التبديل إن كان العنصر الذي عُثر عليه أكبر من العنصر التالي
			if arr[j] > arr[j+1] : 
				arr[j], arr[j+1] = arr[j+1], arr[j] 

# اختبار الدال السابقة
arr = [64, 34, 25, 12, 22, 11, 90] 

bubbleSort(arr) 

print ("Sorted array is:") 
for i in range(len(arr)): 
	print ("%d" %arr[i]),

• جافا:

class BubbleSort 
{ 
	void bubbleSort(int arr[]) 
	{ 
		int n = arr.length; 
		for (int i = 0; i < n-1; i++) 
			for (int j = 0; j < n-i-1; j++) 
				if (arr[j] > arr[j+1]) 
				{ 
					// إجراء عملية التبديل
					int temp = arr[j]; 
					arr[j] = arr[j+1]; 
					arr[j+1] = temp; 
				} 
	} 

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

	//اختبار الدوال السابقة 
	public static void main(String args[]) 
	{ 
		BubbleSort ob = new BubbleSort(); 
		int arr[] = {64, 34, 25, 12, 22, 11, 90}; 
		ob.bubbleSort(arr); 
		System.out.println("Sorted array"); 
		ob.printArray(arr); 
	} 
}

تحسين عملية الترتيب

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

• ‎C++‎:

#include <stdio.h> 

void swap(int *xp, int *yp) 
{ 
	int temp = *xp; 
	*xp = *yp; 
	*yp = temp; 
} 

void bubbleSort(int arr[], int n) 
{ 
int i, j; 
bool swapped; 
for (i = 0; i < n-1; i++) 
{ 
	swapped = false; 
	for (j = 0; j < n-i-1; j++) 
	{ 
		if (arr[j] > arr[j+1]) 
		{ 
		swap(&arr[j], &arr[j+1]); 
		swapped = true; 
		} 
	} 

	// تتوقف الدالة عن العمل عند عدم حدوث أية عملية تبديل في الحلقة التكرارية الداخلية
	if (swapped == false) 
		break; 
} 
} 

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

// اختبار الدوال السابقة
int main() 
{ 
	int arr[] = {64, 34, 25, 12, 22, 11, 90}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	bubbleSort(arr, n); 
	printf("Sorted array: \n"); 
	printArray(arr, n); 
	return 0; 
}

• بايثون:

def bubbleSort(arr): 
	n = len(arr) 

	# التنقل عبر جميع عناصر المصفوفة
	for i in range(n): 
		swapped = False

		for j in range(0, n-i-1): 

			# التنقل عبر عناصر المصفوفة بدءًا من 0
            # n-i-1 وانتهاءً بالقيمة
            # نجري عملية التبديل إن كان العنصر الذي عثرنا عليه
            # أكبر من العنصر اللاحق
			if arr[j] > arr[j+1] : 
				arr[j], arr[j+1] = arr[j+1], arr[j] 
				swapped = True

		# إن لم تُجر عملية التبديل في الحلقة التكرارية الداخلية
        # تتوقف الدالة عن العمل
		if swapped == False: 
			break
		
# اختبار الدالة السابقة
arr = [64, 34, 25, 12, 22, 11, 90] 

bubbleSort(arr) 

print ("Sorted array :") 
for i in range(len(arr)): 
	print ("%d" %arr[i],end=" ")

• جافا:

import java.io.*; 

class GFG 
{ 
	static void bubbleSort(int arr[], int n) 
	{ 
		int i, j, temp; 
		boolean swapped; 
		for (i = 0; i < n - 1; i++) 
		{ 
			swapped = false; 
			for (j = 0; j < n - i - 1; j++) 
			{ 
				if (arr[j] > arr[j + 1]) 
				{ 
					// تبديل العناصر
					temp = arr[j]; 
					arr[j] = arr[j + 1]; 
					arr[j + 1] = temp; 
					swapped = true; 
				} 
			} 

			
            // إن لم تُجر عملية التبديل بواسطة الحلقة التكرارية الداخلية
			// تتوقف الدالة عن العمل
            if (swapped == false) 
				break; 
		} 
	} 

	// دالة لطباعة عناصر المصفوفة
	static void printArray(int arr[], int size) 
	{ 
		int i; 
		for (i = 0; i < size; i++) 
			System.out.print(arr[i] + " "); 
		System.out.println(); 
	} 

	// اختبار الدوال السابقة
	public static void main(String args[]) 
	{ 
		int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; 
		int n = arr.length; 
		bubbleSort(arr, n); 
		System.out.println("Sorted array: "); 
		printArray(arr, n); 
	} 
}

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

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

مصادر

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