خوارزمية الفرز (الترتيب) الفقاعي (Bubble Sort)

ذكرنا في مقالٍ سابقٍ (خوارزمية البحث الثنائي) مثالًا عن أهمية ترتيب العناصر ضمن بنية تخزين المعطيات كالمصفوفة مثلاً، إذًا الغاية من خوارزميات الفرز (الترتيب) هي ترتيب أو فهرسة العناصر تصاعديًا أو تنازليًا. يمكن أن تكون هذه العناصر مجموعات من الأعداد، أو المحارف، أو أي بنيةٍ تحوي أحد هذه الأنماط.

للفرز أنواع عدّة منها: الفرز بالاختيار، والفرز بالإضافة، والفرز بالدمج، والفرز السريع، والفرز الفقاعيّ، وغيرها من الخوارزميات التي سنأتي على ذكرها في المقالات القادمة.

في هذا المقال سنبدأ بخوارزمية الفرز الفقاعي التي سُمّيت كذلك، ببساطة، لأن العناصر في هذه الخوارزمية تستقر في مكانها الصحيح بطريقةٍ تشبه فقاعة الهواء التي تعلو خارج الماء، فلنرَ كيف ذلك!

إقرأ أيضا: خوارزمية البحث الثنائي – Binary Search

ما هي خوارزمية الفرز الفقاعي؟

خوارزمية الترتيب الفقاعي هي خوارزميةٌ مبنيةٌ على فكرة المقارنة المتكررة بين زوجٍ من العناصر المتجاورة، وتبديل مواقعهم إذا كانوا في ترتيبٍ خاطئ.

ما هي آلية عمل الخوارزمية؟

فلنفترض أنّ لدينا مصفوفة A غير مرتبةٍ تحتوي على n عنصر، والمطلوب هو ترتيب العناصر تصاعديًا، فلنفرض أنّ المصفوفة تحتوي على العناصر الآتية: {7, 4, 5, 2}

في الخطوة الأولى: مقارنة الرقم 4 مع الرقم 7، وبما أنّ 4 < 7، سيتم تبديل موقعيهما فيما بينهما، ولأن باقي العناصر أصغر من الـ 7، ستكرر العملية حتى يصبح رقم 7 في آخر المصفوفة.

الآن أصبحت المصفوفة بالشكل الآتي : {4, 5, 2, 7}

في الخطوة الثانية: مقارنة الرقم 5 مع الرقم 4 ، وبما أنّ 4 < 5، ومرتبين ترتيبًا تصاعديًا لن يتم تبديل موقعيهما. ثم مقارنة الرقم 5 مع الرقم 2، طبعًا بما أنّ 2 < 5، سيتمّ تبديل موقعيهما فيما بينهما.

 الآن أصبحت المصفوفة بالشكل الآتي: {4, 2, 5, 7}

في الخطوة الثالثة: مقارنة الرقم 4 مع الرقم 2، بما أنّ 2 < 4، سيتمّ تبديل موقعيهما فيما بينهما. لتصبح المصفوفة مرتبةً تصاعديًا بالشكل التالي: {2,4,5,7}.

مثالٌ برمجيٌّ لتوضيح آلية العمل:

 

https://gist.github.com/YassineBajdou/e6ee0fd5fd4d777cff283eae5a84be32

درجة تعقيد الخوارزمية (Time Complexity):

تعقيد تربيعيO(n²) من رتبة n²: لأنه يتمّ المرور على كامل المصفوفة من أجل كل عنصر (أي: قراءة n عنصر n مرة).