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

من ويكيبيديا، الموسوعة الحرة

ترتيب الفقاعات لمجموعة اعداد

ترتيب الفقاعات (إنكليزي: 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;
 			}
 }