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

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

ترتيب الفقاعات (إنكليزي: 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)$ في الحالة المثلى.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .