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

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

نص غير منسق

Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016)
ترتيب الفقاعات لمجموعة اعداد
ترتيب_الفقاعات

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

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

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

كود ترتيب الفقاعات بلغة 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. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Pages 106–110 of section 5.2.2: Sorting by Exchanging. "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!" (Quote from the first edition, 1973.)
  2. ^ Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. SIGCSE 2003 Hannan Akhtar . (pdf)
  3. ^ "jargon, node: bogo-sort". www.jargon.net. اطلع عليه بتاريخ 2016-12-30. 


خوارزميات الترتيب

بالفقاعات · بالإختيار · بالإدراج · سريع · انتقائي · دمجي