الإعلام الآلي — الخوارزميات: خوارزمية الترتيب الفقاعي — الأولى ثانوي — المنهاج الجزائري

الخوارزميات: خوارزمية الترتيب الفقاعي

الترتيب الفقاعي (Bubble Sort) هو خوارزمية بسيطة لترتيب عناصر مصفوفة. تقوم بمقارنة عنصرين متجاورين وتبديلهما اذا كانا في الترتيب الخطأ، وتكرر العملية حتى تصبح المصفوفة مرتبة.

مبدأ العمل

الخوارزمية: تقارن العنصر الاول مع الذي يليه. اذا كان العنصر الاول اكبر من الثاني، تبدلهما. تنتقل إلى الزوج التالي (الثاني والثالث) وتكرر المقارنة والتبديل. بعد المرور الاول، يكون اكبر عنصر في اخر موضع. تكرر العملية على باقي المصفوفة (بدون اخر عنصر) حتى تكتمل.

مثال

رتب المصفوفة [5, 3, 8, 1] تصاعديا: المرور 1: (5,3) → [3,5,8,1]، (5,8) لا تبديل، (8,1) → [3,5,1,8]. المرور 2: (3,5) لا تبديل، (5,1) → [3,1,5,8]. المرور 3: (3,1) → [1,3,5,8]. المصفوفة مرتبة.

تحليل الاداء

التعقيد الزمني: O(n2) في اسوأ حالة (مصفوفة معكوسة). O(n) في افضل حالة (مصفوفة مرتبة بالفعل). مناسبة للمصفوفات الصغيرة لكنها بطيئة في المصفوفات الكبيرة. خوارزميات مثل Quick Sort و Merge Sort اسرع.

تمارين

تمرين 1: طبق خوارزمية الترتيب الفقاعي على [7, 2, 9, 1, 5] خطوة بخطوة.

تمرين 2: كم مرة مقارنة تحتاج لترتيب مصفوفة من 5 عناصر في اسوأ حالة؟

للمزيد: الخوارزميات الأساسية: البحث والترتيب و مفهوم الخوارزمية وخصائصها.