فهم حقيقة فرز فقاعي

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

لترتيب N عناصر في المصفوفة A ، عدد المقارنات سيكون:













N

(

N

−

1

)



2





=



∑



i

=

0





N







x



i









{\displaystyle {N(N-1) \over 2}=\sum _{i=0}^{N}x_{i}}



.

أما عدد التبديلات فهو في المتوسط









N

(

N

−

1

)



4





{\displaystyle N(N-1) \over 4}



. حيث N هي عدد العناصر.

تعقيد الخوارزم هو











O







(



n



2





)







{\displaystyle {\mathcal {O}}\left(n^{2}\right)}



في المعدل، و











O







(

n

)







{\displaystyle {\mathcal {O}}\left(n\right)}



في الحالة المثلى.