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

ترتيب الفقاعات (إنكليزي: Bubble sort) هي خوارزمية ترتيب منتقدة لبطئها[1][2][3] ، هي تعمل على رفع العنصر الأكبر كفقاعة الهواء التي ترتفع إلى أعلى وذلك بترتيب العناصر بتتابع، أي نقوم بمقارنة العنصرين الأول والثاني، ونحتفظ بالعنصر الأكبر، ونبدل الأماكن إذا كانا غير مرتبين، ونقوم بهذه العملية إلى آخر عنصر، وبعد ذلك نعيد العمليات إلى المكان ما قبل الأخير وهكذا دواليك، ثم نتوقف عند وجود جدول بالبعد 1 أو عندما لا نقوم بالتبديلات عند آخر عملية.

ترتيب فقاعي
ترتيب الفقاعات
بيانات عامّة
الصنف خوارزمية ترتيب
بنية البيانات مصفوفة
الأداء في أسوء حالة О(n2)
الأداء في الحالة المُثلى О(n)
الأداء الوسطي О(n2)
أسوء حالة في تعقيد الفضاء О(1)
ترتيب_الفقاعات

لترتيب N عناصر في المصفوفة A ،عدد المقارنات سيكون: .

أما عدد التبديلات فهو في المتوسط . حيث N هي عدد العناصر.

تعقيد الخوارزم هو في المعدل، و في الحالة المثلى.

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

 

procedure bubbleSort( A : list of sortable items ) defined as:
 do
  swapped := false
  for each i in 0 to length(A) - 2 inclusive do:
   if A[ i ] > A[ i + 1 ] then
    swap( A[ i ], A[ i + 1 ] )
    swapped := true
   end if
  end for
 while swapped
end procedure


في الاستخدام العملي

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

بسبب بساطة الخوارزم يتم استخدامه كأول مثال لخوارزم ترتيب يتعلمه طلاب علم الحاسوب. لكن بعض الباحثين مثل Owen Astrachan ينصحون بالابتعاد عن هذا الخوارزم وعدم استخدامه حتى في التعليم.[4]

قاموس The Jargon File الذي سمى خوارزم Bogosort ب"المثال الأعلى لخوارزم شنيع" سمى خوارزم الترتيب بالفقاعات "خوارزم سيء".[5] في كتاب فن برمجة الحاسوب يستنتج دونالد كانوث "لا يوجد سبب للنظر في خوارزم ترتيب الفقاعات الا اسمه الجميل وكونه يولد بعض المشاكل النظرية المثيرة للاهتمام", ثم يقوم بذكر بعض هذه المشاكل النظرية.

ترتيب الفقاعات بلغات مختلفة

كود ترتيب الفقاعات بلغة C

 
 typedef int tab_entiers[MAX];
 void bubble_sort(tab_entiers t) {
 	int i، j، tmp;
 	for(i = 1 ; i < MAX ; i++)
 		for(j = 0 ; j < MAX - i ; j++)
 			if(t[j] > t[j+1]) {
 				tmp = t[j+1];
 				t[j+1] = t[j];
 				t[j] = tmp;
 			}
 }

كود ترتيب الفقاعات بلغة Java

 
 [MAX];
 public class Bubble_sort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int name[]= {20,10,-5,6,2,1};
		int a = 0 ;
		for (int x = 0; x < name.length; x++) 
			System.out.print(name[x]+"   ");
		System.out.println();

		 for (int x = name.length - 1 ; x > 0; x--) {
			for (int y = 0; y < name.length-1; y++) {
				int temp = name[y];
				int temp2 = name[y+1]; 
				if(name[y] > name[y+1]) {
					name[y]  = temp2;
					name[y+1]= temp ;
					a++ ;
					for (int m = 0; m < name.length; m++) 
						System.out.print(name[m]+"   ");
					System.out.println(); 
					

				}			
			} 					System.out.println(); 

		}
	    for (int v = 0; v < name.length; v++) 
			System.out.print(name[v]+"   ");
		System.out.println();
		System.out.println("the num of changes of the array is "+a);

		
	}
	}
}
 }

مراجع
  1. Donald Knuth.<ref>Cortesi, Aldo (27 April 2007). "Visualising Sorting Algorithms". مؤرشف من الأصل في 07 يوليو 2017. اطلع عليه بتاريخ 16 مارس 2017. الوسيط |CitationClass= تم تجاهله (مساعدة); تحقق من التاريخ في: |تاريخ أرشيف= (مساعدة)
  2. "jargon, node: bogo-sort". مؤرشف من الأصل في 05 مايو 2017. الوسيط |CitationClass= تم تجاهله (مساعدة); تحقق من التاريخ في: |تاريخ أرشيف= (مساعدة)
  3. Astrachan, Owen (2003). "Bubble sort: an archaeological algorithmic analysis" (PDF). ACM SIGCSE Bulletin. 35 (1): 1–5. doi:10.1145/792548.611918. ISSN 0097-8418. مؤرشف من الأصل (PDF) في 23 سبتمبر 2015. الوسيط |CitationClass= تم تجاهله (مساعدة)
  4. Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. SIGCSE 2003 Hannan Akhtar . (pdf) نسخة محفوظة 15 سبتمبر 2009 على موقع واي باك مشين.
  5. "jargon, node: bogo-sort". www.jargon.net. مؤرشف من الأصل في 5 مايو 2017. اطلع عليه بتاريخ 30 ديسمبر 2016. الوسيط |CitationClass= تم تجاهله (مساعدة)


    • بوابة خوارزميات
    • بوابة رياضيات
    • بوابة علم الحاسوب
    في كومنز صور وملفات عن: ترتيب الفقاعات
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.