الترتيب الفقاعي

الترتيب الفقاعي أبسط خوارزميات الترتيب وصفًا: قارن عنصرين متجاورين، وبدّلهما إذا كانا في ترتيب خاطئ، ثم كرّر. إنه بطيء على القوائم الطويلة، لكن كل خطوة فيه سهلة المتابعة، ولذلك فهو الخوارزمية الكلاسيكية الأولى التي يُبدأ بمشاهدتها.

أعمدة بأطوال مختلفة قيد الترتيب، مع تمييز عمودين متجاورين للتبديل وأطول الأعمدة في أماكنها بالفعل في النهاية
أعمدة بأطوال مختلفة قيد الترتيب، مع تمييز عمودين متجاورين للتبديل وأطول الأعمدة في أماكنها بالفعل في النهاية

الفكرة

امشِ على القائمة من اليسار إلى اليمين وانظر إلى كل زوج متجاور. إذا كانت القيمة اليسرى أكبر من اليمنى فبدّلهما. عند الوصول إلى النهاية تكون أكبر قيمة قد انتقلت حتى المكان الأخير، كما تصعد الفقاعة إلى السطح. يسمى هذا المرور جولة. كرّر الجولات حتى تصبح القائمة مرتبة.

مثال

خذ 5, 1, 4, 2, 8. تقارن الجولة الأولى 5 و1 وتبدّلهما، ثم 5 و4 (تبديل)، و5 و2 (تبديل)، و5 و8 (بلا تبديل): 1, 4, 2, 5, 8. أصبح 8 الآن في مكانه النهائي. تقارن الجولة الثانية 1 و4 (بلا تبديل)، و4 و2 (تبديل)، و4 و5 (بلا تبديل): 1, 2, 4, 5, 8. لا تحدث في الجولة الثالثة أي تبديلات، لذا فالقائمة مرتبة: 9 مقارنات و4 تبديلات.

لماذا تضع كل جولة قيمة إضافية في مكانها

خلال الجولة، تُحمل أكبر قيمة صادفناها حتى الآن معنا دائمًا: فبمجرد أن تصل الجولة إليها، تنقلها كل مقارنة مكانًا آخر إلى اليمين. لذلك تضع الجولة الأولى أكبر قيمة في الآخر، والثانية ثاني أكبر قيمة قبلها مباشرة، وهكذا. بعد الجولة k تصبح آخر k أماكن نهائية، ويمكن للجولة التالية أن تتوقف قبل ذلك بمكان واحد. ولهذا تقصر الجولات تدريجيًا.

التبديلات تساوي الانقلابات

الانقلاب زوج من القيم في ترتيب خاطئ: قيمة أكبر تقع في موضع ما قبل قيمة أصغر. تبديل عنصرين متجاورين في ترتيب خاطئ يزيل انقلابًا واحدًا بالضبط ولا ينشئ أي انقلاب جديد. لذا يجري الترتيب الفقاعي من التبديلات بقدر ما في القائمة الأولية من انقلابات تمامًا، أيًّا كان ترتيب المقارنات. القائمة المرتبة لا انقلابات فيها؛ والقائمة المعكوسة من n قيمة فيها n(n − 1)/2، وهو أكبر عدد ممكن.

التوقف المبكر والتكلفة

إذا خلت جولة كاملة من التبديلات، فكل زوج متجاور في ترتيبه الصحيح والقائمة مرتبة. وبفحص ذلك ينهي الترتيب الفقاعي القائمة المرتبة في جولة واحدة من n − 1 مقارنة. أما في أسوأ حالة فما زال يحتاج إلى n − 1 جولة وn(n − 1)/2 مقارنة، ومتوسط عدد التبديلات n(n − 1)/4. وكلاهما ينمو مع n²، فمضاعفة طول القائمة تجعل الترتيب يستغرق نحو أربعة أضعاف الوقت.

الترتيب الفقاعي مستقر: القيم المتساوية لا تتبادل أبدًا، فتحافظ على ترتيبها. وهو يرتب في المكان دون ذاكرة إضافية. يشترك معه الترتيب بالإدراج في هذه الخصائص ويحتاج عادةً إلى خطوات أقل، أما الترتيب بالدمج والترتيب السريع فيستغرقان وقتًا يتناسب مع n log n، وهو أقل بكثير على القوائم الطويلة.

استكشفه بنفسك

افتح التطبيق واضغط تشغيل، أو اضغط خطوة للتقدم مقارنةً واحدة في كل مرة. تُميَّز القيمتان قيد المقارنة، ويظهر التبديل بلون خاص به، وتتحول القيم التي وصلت إلى أماكنها إلى اللون الأخضر. جرّب قائمة معكوسة لترى أسوأ حالة، أو قائمة شبه مرتبة لترى التوقف المبكر ينهي الترتيب بعد جولات قليلة، أو اكتب أرقام المثال أعلاه.

الأسئلة المتداولة

ما التعقيد الزمني للترتيب الفقاعي؟

O(n²) في أسوأ حالة وفي المتوسط: حتى n(n − 1)/2 مقارنة مع n قيمة. مع التوقف المبكر تستغرق القائمة المرتبة مسبقًا O(n)، أي جولة واحدة. ولا يحتاج إلا إلى O(1) من الذاكرة الإضافية.

هل الترتيب الفقاعي مستقر؟

نعم. فهو لا يبدّل عنصرين متجاورين إلا إذا كان الأيسر أكبر تمامًا، لذا لا تتجاوز القيم المتساوية بعضها أبدًا وتحافظ على ترتيبها الأصلي.

ما الفرق بين الترتيب الفقاعي والترتيب بالإدراج؟

كلاهما يبدّل العناصر المتجاورة، وكلاهما يجري من التبديلات بقدر عدد الانقلابات. يمر الترتيب الفقاعي جولات كاملة على الجزء غير المرتب؛ أما الترتيب بالإدراج فيُرجع كل قيمة جديدة إلى الخلف بالقدر اللازم فقط، لذا يجري عادةً مقارنات أقل، خصوصًا على القوائم شبه المرتبة.

متى يكون الترتيب الفقاعي خيارًا جيدًا؟

غالبًا للتعليم، وللقوائم القصيرة جدًا حيث تهم البساطة أكثر من السرعة. أما لأي شيء أكبر، فدالة الترتيب المدمجة في لغة البرمجة التي تستخدمها أسرع بكثير.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

جرّب الترتيب الفقاعي