الفرز الفقاعي
يمرّ على القائمة مرة بعد مرة، ويبدّل كل قيمتين متجاورتين في غير ترتيبهما. بعد كل جولة تصل أكبر قيمة متبقية إلى النهاية.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- نعم
- نعم
الأفضل: كيف يزداد الوقت مع حجم القائمة n عندما تكون المدخلات هي الأسهل لهذه الخوارزمية.
المتوسط: النمو المعتاد للوقت مع n. في n² إذا تضاعف عدد القيم صار الوقت نحو أربعة أضعاف، أما n log n فينمو أبطأ بكثير.
الأسوأ: نمو الوقت مع أصعب المدخلات. مفيد عندما يجب ألا تنخفض السرعة أبدًا.
الذاكرة: كم يحتاج من ذاكرة إضافية غير القائمة. 1 يعني بضعة متغيرات، و n يعني نسخة من القائمة.
مستقر: تحافظ القيمتان المتساويتان على ترتيبهما الأصلي. يهم هذا عند الفرز حسب حقل واحد من السجل.
بلا ذاكرة إضافية: يرتّب داخل القائمة نفسها، دون قائمة ثانية.
- قيد المقارنة
- قيد النقل
- في مكانه النهائي
جرّب هذا: اختر قائمة شبه مرتّبة. بعد جولة واحدة بلا أي تبديل، تتوقف الخوارزمية مبكرًا.
كيف يعمل
يقارن قيمتين متجاورتين في كل مرة، ويبدّلهما إذا كانت اليسرى أكبر. لذلك تنتقل أكبر قيمة في كل جولة إلى أقصى اليمين، كفقاعة تصعد. وإذا مرّت جولة بلا أي تبديل، فالقائمة مرتّبة أصلًا.
متى يكون خيارًا جيدًا
لا يكاد يُستخدم في البرامج الحقيقية، لأنه بطيء مع القوائم الطويلة. لكنه ممتاز للتعلّم، فهو يوضح فكرة الفرز الأساسية: المقارنة ثم التبديل. ولا يكون سريعًا إلا إذا كانت القائمة مرتّبة أصلًا.