17. تحليل كفاءة فرز الفقاعة (Bubble Sort)

كما رأينا، يستخدم Bubble Sort حلقات متداخلة، مما يشير عادةً إلى تعقيد زمني تربيعي.

تحليل التعقيد الزمني

• أسوأ حالة (Worst Case): O(N²)
  • يحدث عندما تكون المصفوفة مفرزة بترتيب عكسي. يجب أن تقوم الحلقة الداخلية بأقصى قدر من المقارنات في كل تمريرة.
• أفضل حالة (Best Case): O(N)
  • يحدث إذا كانت المصفوفة مفرزة بالفعل. إذا أضفنا علامة (flag) لاكتشاف ما إذا حدثت أي عمليات تبديل في تمريرة، يمكننا التوقف مبكراً بعد التمريرة الأولى O(N)، مما يحقق وقتاً خطياً.
• الحالة المتوسطة (Average Case): O(N²)

التعقيد المكاني

• التعقيد المكاني (Space Complexity): مساحة مساعدة O(1).
  • Bubble sort هي خوارزمية فرز في الموقع (in-place)، مما يعني أنها تتطلب حداً أدنى وثابتاً من الذاكرة الإضافية (عادةً للمتغيرات المؤقتة المستخدمة في التبديل فقط).