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

ملف:Bubble sort animation.gif

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

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

لترتيب N عناصر في المصفوفة A ،عدد المقارنات سيكون: $\sum _{i=0}^N{x}_i$ = $\frac{N(N-1)}{2}$.

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

تعقيد الخوارزم هو ${𝒪}\left(n^2\right)$ في المعدل, و${𝒪}\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

<source lang="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;
			}
}

</source>

ملف:Nuvola apps edu mathematics-ar.svg

بوابة رياضيات تصفح مقالات ويكيبيديا المهتمة بالرياضيات.

bg:Метод на мехурчето ca:Bubble-sort cs:Bublinkové řazení da:Boblesortering de:Bubblesort el:Ταξινόμηση φυσαλίδας Bubble sort]] es:Ordenamiento de burbuja et:Mullsortimine fa:مرتب‌سازی حبابی fi:Kuplalajittelu fr:Tri à bulles he:מיון בועות hu:Buborékrendezés is:Víxlunarröðun it:Bubble sort ja:バブルソート kk:Көпіршіктік сүрыптау (көпіршік әдісімен сүрыптау) ko:거품 정렬 ku:Rêzkerdişê çimokan lt:Burbulo rikiavimo algoritmas ml:ബബിൾ സോർട്ട് nl:Bubblesort no:Sorteringsalgoritme#Boblesortering pl:Sortowanie bąbelkowe pt:Bubble sort ru:Сортировка пузырьком simple:Bubble sort sk:Bublinkové triedenie sl:Mehurčno urejanje sv:Bubbelsortering th:การเรียงลำดับแบบฟอง tr:Kabarcık sıralaması uk:Сортування бульбашкою vi:Sắp xếp nổi bọt zh:冒泡排序