إن Bubble Sort عبارة عن خوارزمية فرز بسيطة تتنقل بشكل متكرر عبر القائمة وتقارن العناصر المتجاورة وتتبادلها إذا كانت بالترتيب الخاطئ. تم تسميته بـ 'Bubble Sort' لأن العناصر الأصغر 'فقاعة' تصل إلى أعلى القائمة. على الرغم من أنها ليست خوارزمية الفرز الأكثر كفاءة، إلا أنها سهلة الفهم والتنفيذ، مما يجعلها نقطة انطلاق جيدة للتعرف على خوارزميات الفرز. في هذه المقالة، سوف نتعمق في مفهوم فرز الفقاعات، ونوفر تنفيذ بايثون مع المخرجات، ونناقش التعقيد الزمني للخوارزمية.
فهم نوع الفقاعة
الفكرة الأساسية وراء فرز الفقاعات هي تكرار القائمة عدة مرات، ومقارنة العناصر المتجاورة وتبديلها إذا كانت خارج الترتيب. تستمر العملية حتى لا تكون هناك حاجة لمزيد من المبادلات، مما يشير إلى أنه تم فرز القائمة الآن. تحصل الخوارزمية على اسمها من الطريقة التي تنتقل بها العناصر الأصغر تدريجيًا إلى أعلى القائمة، تمامًا مثل الفقاعات التي ترتفع إلى السطح.
دعونا نحلل خطوات خوارزمية فرز الفقاعات:
- التكرار عبر القائمة: ابدأ من بداية القائمة وقارن بين كل زوج من العناصر المتجاورة.
- المقارنة والتبديل: إذا كانت العناصر في ترتيب خاطئ، قم بتبديلها. وهذا يضمن أن العنصر الأكبر 'يطفو على السطح' ويتحرك العنصر الأصغر إلى الأسفل.
- متابعة التكرار: كرر العملية لكل زوج من العناصر المتجاورة حتى الوصول إلى نهاية القائمة.
- كرر حتى يتم الفرز: استمر في التكرار خلال القائمة حتى لا تكون هناك حاجة إلى المزيد من المقايضات. في هذه المرحلة، يتم فرز القائمة.
على الرغم من سهولة فهم طريقة فرز الفقاعات، إلا أنها ليست خوارزمية الفرز الأكثر كفاءة، خاصة بالنسبة لمجموعات البيانات الكبيرة. تعقيدها الزمني هو O(n^2) في أسوأ الحالات، حيث 'n' هو عدد العناصر في القائمة. هذا التعقيد الزمني التربيعي يجعله أقل ملاءمة لمجموعات البيانات الكبيرة بالمقارنة مع خوارزميات الفرز الأكثر تقدمًا.
تنفيذ بايثون لفرز الفقاعات
الآن، دعونا ننفذ عملية فرز الفقاعات في لغة بايثون ونلاحظ سلوكها من خلال قائمة نماذج:
def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list)
في هذا التنفيذ، تأخذ الدالة bubble_sort قائمة (arr) كمعلمة لها وتقوم بفرزها في مكانها. تقارن الحلقة المتداخلة العناصر المتجاورة وتتبادلها إذا كانت بالترتيب الخاطئ. تضمن الحلقة الخارجية تكرار العملية حتى يتم فرز القائمة بأكملها.
الإخراج والشرح
لنقم بتشغيل كود Python المقدم باستخدام قائمة العينات ونلاحظ الإخراج:
Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90]
هنا، تم فرز القائمة الأصلية [64، 34، 25، 12، 22، 11، 90] بنجاح باستخدام خوارزمية فرز الفقاعات، مما أدى إلى ظهور القائمة المرتبة [11، 12، 22، 25، 34، 64، 90].
تتكرر الخوارزمية عبر القائمة عدة مرات، وتقارن العناصر وتتبادلها حتى يتم فرز القائمة بأكملها. في كل تمريرة، 'يطفو' أكبر عنصر غير مصنف إلى موضعه الصحيح. تستمر هذه العملية حتى لا تكون هناك حاجة لمزيد من المبادلات، مما يشير إلى أن القائمة قد تم فرزها بالكامل.
بينما يقوم Bubble Sort بفرز القائمة بنجاح، فمن المهم ملاحظة أن التعقيد الزمني الخاص به يجعله أقل كفاءة لمجموعات البيانات الكبيرة مقارنة بخوارزميات الفرز الأخرى مثل Merge Sort أو Quick Sort.
التعقيد الزمني للفرز الفقاعي
يعد فهم التعقيد الزمني للخوارزمية أمرًا بالغ الأهمية لتقييم كفاءتها، خاصة عند التعامل مع مجموعات البيانات الكبيرة. التعقيد الزمني لفرز الفقاعات هو O(n^2) في أسوأ الحالات، حيث 'n' هو عدد العناصر في القائمة.
دعونا نحلل تحليل التعقيد الزمني:
- يتم تشغيل الحلقة الخارجية لتكرارات 'n'، حيث 'n' هو عدد العناصر في القائمة.
- يتم تشغيل الحلقة الداخلية أيضًا للتكرارات 'n' في أسوأ الحالات. ومع ذلك، مع تقدم الخوارزمية، يتناقص عدد التكرارات في الحلقة الداخلية، حيث يتم وضع أكبر عنصر غير مصنف في موضعه الصحيح في كل تمريرة.
- في أسوأ الحالات، يتناسب عدد المقارنات والمقايضات مع مربع عدد العناصر في القائمة، مما يؤدي إلى التعقيد الزمني O(n^2). وهذا يجعل فرز الفقاعات غير فعال بالنسبة لمجموعات البيانات الكبيرة، وغالبًا ما يتم تفضيل خوارزميات الفرز الأكثر تقدمًا ذات التعقيدات الزمنية الأفضل في تطبيقات العالم الحقيقي.
خاتمة
في هذه المقالة، استكشفنا مفهوم فرز الفقاعات، وهي خوارزمية فرز بسيطة تقوم بشكل متكرر بمقارنة العناصر المتجاورة وتبديلها حتى يتم فرز القائمة بأكملها. لقد قدمنا تطبيق Python لـ Bubble Sort، وقمنا بتشغيله باستخدام قائمة عينة، وقمنا بتحليل المخرجات. بالإضافة إلى ذلك، ناقشنا التعقيد الزمني لفرز الفقاعات، مع تسليط الضوء على التعقيد الزمني لأسوأ حالة O(n^2) وآثاره على الكفاءة.