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

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

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

لترتيب N عناصر في المصفوفة A ،عدد المقارنات سيكون: \sum_{i=0}^N x_i= N(N-1) \over 2.

أما عدد التبديلات فهو في المتوسط N(N-1) \over 4. حيث N هي عدد العناصر.

تعقيد الخوارزم هو  \mathcal{O} \left(n^2 \right) في المعدل, و \mathcal{O} \left(n \right) في الحالة المثلى.

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

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


كود ترتيب الفقاعات بلغة 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);
 
 
	}
	}
}
 }
خوارزميات الترتيب

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