طريقة الفقاعة هي واحدة من أبسط خوارزميات الفرز. ويستند عمله على فكرة تدريجيا" ظهرت " أكبر عناصر القائمة ، ونقلها إلى النهاية. ومع ذلك ، قد تصبح هذه الطريقة غير فعالة إذا تم فرز القائمة بالفعل. في هذه الحالة ، سيستمر البرنامج في إجراء تمريرات غير ضرورية دون تغيير ترتيب العناصر.
من أجل تحسين تشغيل طريقة الفقاعة ، يمكنك إضافة شرط إيقاف يتحقق مما إذا كان قد تم إجراء تبديل واحد على الأقل في الخطوة التالية من الحلقة الخارجية. إذا لم تكن هناك مثل هذه التباديل ، فيمكن اعتبار عملية الفرز مكتملة. في هذه الحالة ، يمكنك الخروج من الحلقة الخارجية وإنهاء الفرز.
يسمح لك الإصدار الأمثل من طريقة الفقاعة باستخدام حالة الإيقاف بتسريع عملية الفرز بشكل كبير ، خاصة في الحالات التي تم فيها فرز القائمة الأصلية جزئيا بالفعل. الآن لن يعرض البرنامج القائمة بأكملها في كل خطوة من الحلقة الخارجية ، والتي سيكون لها تأثير إيجابي على أداء الخوارزمية.
وبالتالي ، فإن طريقة الفقاعة بشرط التوقف هي نسخة أكثر كفاءة من الخوارزمية الأساسية. يسمح لك بتوفير الوقت وموارد الكمبيوتر عند فرز القوائم ، خاصة إذا كانت البيانات المصدر مرتبة جزئيا بالفعل.
- تباديل العناصر بطريقة الفقاعة بشرط التوقف
- طريقة الفقاعة بشرط التوقف: في حالة عدم وجود تبادلات في الخطوة التالية من الدورة الخارجية
- مثال على تشغيل طريقة الفقاعة مع حالة توقف
- وقف الشرط: لا التبادلات
- الحلقة الخارجية ودورها في الخوارزمية
- ملامح تنفيذ حالة التوقف
- تطبيق طريقة الفقاعة مع حالة توقف
- مزايا وعيوب الطريقة
- سؤال وجواب
- كيف تعمل طريقة الفقاعة مع حالة التوقف?
- ما هو تعقيد طريقة فقاعة مع حالة توقف?
- كيف يمكنني التحقق من أن طريقة الفقاعة مع حالة التوقف ستقوم بفرز المصفوفة بشكل صحيح?
- ماذا يحدث إذا كانت الحلقة الداخلية لطريقة الفقاعة مع حالة توقف لا تؤدي أي تبادلات في خطوة معينة?
تباديل العناصر بطريقة الفقاعة بشرط التوقف
طريقة الفقاعة هي واحدة من أبسط خوارزميات الفرز وأكثرها شيوعا. لأنه يقوم على يمر المتكررة من خلال مجموعة ومقارنة العناصر المجاورة. إذا كان العنصر الحالي أكبر من العنصر التالي ، يتم تبديلها. وهكذا ، في كل تمريرة ، "ينبثق" أكبر عنصر إلى الموضع الصحيح.
في التنفيذ الكلاسيكي لطريقة الفقاعة ، يتم تبادل العناصر في كل خطوة من الدورة الخارجية. ومع ذلك ، في ظل ظروف معينة ، يمكنك التحسين والتوقف عن الفرز مبكرا إذا لم تكن هناك تبادلات في الخطوة التالية من الدورة الخارجية.
حالة التوقف في طريقة الفقاعة مع حالة التوقف بسيطة للغاية: إذا لم يتم تبادل أي عناصر في الخطوة التالية من الحلقة الخارجية ، فقد تم فرز المصفوفة بالفعل ولا معنى لمواصلة الفرز.
يمكن تمثيل عملية فرز الفقاعة بشرط التوقف على أنها الخوارزمية التالية:
- ضع علامة تشير إلى وجود التبادلات في الممر السابق للحلقة الداخلية.
- طالما أن العلم هو الصحيح ، أداء يمر من خلال مجموعة باستخدام حلقة خارجية:
- اضبط العلم على خطأ قبل كل تمريرة من الحلقة الداخلية.
- لكل عنصر من عناصر المصفوفة ، بدءا من 0 وحتى (طول المصفوفة هو 1):
- إذا كان العنصر الحالي أكبر من العنصر التالي ، فقم بتبديله وتعيين العلم على صحيح.
وبالتالي ، تسمح لك طريقة الفقاعة بشرط التوقف بتحسين أداء الفرز ، خاصة في حالة فرز المصفوفة جزئيا بالفعل. في غياب التبادلات ، يتوقف الفرز في الخطوة التالية من الدورة الخارجية ، مما يوفر وقت تنفيذ الخوارزمية.
طريقة الفقاعة بشرط التوقف: في حالة عدم وجود تبادلات في الخطوة التالية من الدورة الخارجية
طريقة الفقاعة هي واحدة من أبسط خوارزميات الفرز. حصلت على اسمها بسبب حقيقة أنه في كل تكرار ، أكبر عنصر "الملوثات العضوية الثابتة" في مكانه ، مثل فقاعة ظهرت في الماء.
مبدأ تشغيل طريقة الفقاعة مع حالة توقف هو مقارنة العناصر المجاورة للصفيف وتبادلها بشكل متكرر حتى يتم فرز المصفوفة بالكامل. تتكون الخوارزمية من حلقتين متداخلتين: خارجية وداخلية.
تمر الحلقة الخارجية عبر جميع عناصر المصفوفة ، بدءا من الأولى وتنتهي بالعنصر قبل الأخير. في كل تكرار للحلقة الخارجية ، تتم مقارنة العنصر الحالي بالعنصر التالي ، وإذا لزم الأمر ، يتم مقايضته.
تمر الحلقة الداخلية عبر المصفوفة ، بدءا من العنصر الأول وتنتهي في نهاية المصفوفة مطروحا منها التكرار الحالي للحلقة الخارجية. في كل تكرار للحلقة الداخلية ، تتم مقارنة العنصر الحالي بالعنصر التالي ، وإذا لزم الأمر ، يتم مقايضته.
شرط التوقف هو أنه إذا لم يتم تبادل أي عناصر في الخطوة التالية من الحلقة الخارجية ، فقد تم بالفعل فرز المصفوفة ويمكن إكمال الخوارزمية. يتيح لك ذلك تسريع تشغيل طريقة الفقاعة بشكل كبير إذا تم بالفعل فرز مصفوفة المصدر أو فرزها تقريبا.
على الرغم من بساطتها ، فإن طريقة الفقاعة ليست خوارزمية فرز فعالة لكميات كبيرة من البيانات. وقت التنفيذ هو س (ن^2) ، مما يجعله غير مرغوب فيه لكميات كبيرة من البيانات. ومع ذلك ، بالنسبة للمصفوفات الصغيرة أو المصفوفات التي تم فرزها بالفعل تقريبا ، يمكن أن تكون طريقة الفقاعة خيارا فعالا وسهل التنفيذ إلى حد ما.
مثال على تشغيل طريقة الفقاعة مع حالة توقف
طريقة الفقاعة هي خوارزمية فرز بسيطة تقارن أزواج العناصر المجاورة وتبادلها إذا كانت بترتيب خاطئ. تتكرر هذه العملية حتى يتم ترتيب جميع العناصر.
ومع ذلك ، بدلا من إجراء عدد ثابت من التمريرات عبر المصفوفة ، تتحقق طريقة الفقاعة بشرط التوقف مما إذا كان قد تم إجراء التبادلات في الخطوة التالية من الحلقة الخارجية. إذا لم يكن كذلك ، يتوقف الفرز لأن المصفوفة مرتبة بالفعل. هذا يضمن تشغيل أكثر كفاءة للخوارزمية في حالة طلب المصفوفة بالفعل تقريبا.
لنلق نظرة على مثال لكيفية عمل طريقة الفقاعة مع حالة توقف في المصفوفة التالية:
| مجموعة المصدر | 1 ممر | ممر 2 | 3 ممر | 4 ممر |
|---|---|---|---|---|
| 5 | 2 | 8 | 3 | 6 |
| 2 | 5 | 3 | 6 | 8 |
| 2 | 3 | 5 | 6 | 8 |
| 2 | 3 | 5 | 6 | 8 |
| 2 | 3 | 5 | 6 | 8 |
| 2 | 3 | 5 | 6 | 8 |
في هذا المثال ، عند كل مسار للخوارزمية ، نقارن أزواج العناصر المجاورة ونبادلها إذا كانت بترتيب خاطئ. بعد كل تمريرة ، يأخذ العنصر الأكبر مكانه على اليمين. وهكذا ، في كل تمريرة لاحقة ، نقارن زوجا أقل من العناصر.
تستمر عملية الفرز حتى لا يتم إجراء أي تبادلات في الممر التالي للحلقة الخارجية. في هذه الحالة ، يتم استيفاء شرط الإيقاف واكتمال الفرز ، حيث تم بالفعل طلب جميع العناصر.
وقف الشرط: لا التبادلات
في طريقة الفقاعة ، مع حالة التوقف في غياب التبادلات في الخطوة التالية من الدورة الخارجية ، يتوقف الفرز عندما لا يكون هناك تبادل واحد للعناصر في مسار واحد.
تتكون خوارزمية فرز الفقاعة من مقارنة أزواج من عناصر المصفوفة المجاورة وإعادة ترتيبها إذا كانت بترتيب خاطئ. في كل مرة تمر فيها الحلقة الخارجية ، "ينبثق" أكبر عنصر إلى الموضع الصحيح. عندما لا يكون هناك تبادل في الممر التالي ، فهذا يعني أن المصفوفة قد تم فرزها بالفعل ، وليس هناك حاجة لمواصلة المرور عبرها.
| مجموعة المدخلات | الممر الأول | الممر الثاني | الممر الثالث |
| [5, 3, 1, 4, 2] | [3, 1, 4, 2, 5] | [1, 3, 2, 4, 5] | [1, 2, 3, 4, 5] |
في هذا المثال ، لا يتم إجراء تبادل واحد في الممر الثالث ، حيث تم فرز المصفوفة بالفعل. لذلك ، يتوقف الفرز ، وليس هناك حاجة لمواصلة العمل.
يمكن أن تؤدي حالة التوقف في غياب التبادلات إلى تسريع الخوارزمية بشكل كبير ، لأنه في حالة فرز المصفوفة بالكامل بالفعل ، لا يلزم وجود تمريرات إضافية عبرها. وبالتالي ، تسمح لك طريقة الفقاعة بشرط التوقف بتحسين الفرز وتقليل عدد العمليات لمقارنة العناصر وإعادة ترتيبها.
الحلقة الخارجية ودورها في الخوارزمية
طريقة الفقاعة بشرط التوقف ، بناء على عدم وجود تبادلات في الخطوة التالية من الدورة الخارجية ، هي تعديل لخوارزمية فرز الفقاعات الكلاسيكية. في هذه الخوارزمية ، يتم تنفيذ الدور الرئيسي بواسطة حلقة خارجية.
تقوم الحلقة الخارجية في خوارزمية الفقاعة بشرط التوقف بتنفيذ المهام التالية:
- يحدد عدد التمريرات عبر المصفوفة. عدد التمريرات يساوي عدد العناصر في المصفوفة ناقص واحد;
- يتحكم في تحقيق شرط التوقف-غياب التبادلات في الخطوة التالية;
- يدير الفهارس في الحلقة الداخلية-من 0 إلى ن-1-أنا ، أين ن هو عدد العناصر في المصفوفة ، أنا هو عدد التمرير الحالي;
في كل تمريرة ، تقارن الحلقة الخارجية لخوارزمية "الفقاعة" أزواج عناصر المصفوفة المجاورة ، وإذا لزم الأمر ، تبادلها. يحدث هذا حتى تكون هناك أزواج في الجزء المتبقي من المصفوفة تتطلب التقليب.
إذا لم يتم إجراء أي تباديل في الممر التالي ، فهذا يعني أن المصفوفة قد تم طلبها بالفعل. في هذه الحالة ، تكمل الحلقة الخارجية للخوارزمية عملها ، وتنتهي عملية فرز الفقاعة بشرط التوقف.
| يمر من خلال مجموعة | عناصر المصفوفة | التباديل |
|---|---|---|
| 1 | [9, 5, 2, 7, 3] | [5, 2, 7, 3, 9] |
| 2 | [5, 2, 7, 3, 9] | [2, 5, 3, 7, 9] |
| 3 | [2, 5, 3, 7, 9] | [2, 3, 5, 7, 9] |
| 4 | [2, 3, 5, 7, 9] | — |
في المثال المعطى ، المصفوفة [9, 5, 2, 7, 3] يتم طلبها باستخدام خوارزمية الفقاعة مع حالة توقف.
في الممر الأول ، تجد الحلقة الخارجية زوجا من 9 و 5 ، وتبادلها ، وتأخذ المصفوفة الشكل [5, 9, 2, 7, 3].
في الممر الثاني ، تجد الحلقة الخارجية الزوج 9 و 2 ، وتبادلها ، وتأخذ المصفوفة الشكل [5, 2, 9, 7, 3].
في الممر الثالث ، تجد الحلقة الخارجية زوجا من 9 و 7 ، وتبادلها ، وتأخذ المصفوفة الشكل [5, 2, 7, 9, 3].
في الممر الرابع ، تجد الحلقة الخارجية الزوج 9 و 3 ، وتبادلها ، وتأخذ المصفوفة شكلها النهائي المطلوب[5, 2, 7, 3, 9].
وهكذا ، ونتيجة لذلك ، في كل تمريرة من الحلقة الخارجية ، "ينبثق" عنصر واحد أكبر في آخر عنصر حر في المصفوفة ، ويرتب نفسه في مكانه.
تلعب الحلقة الخارجية دورا رئيسيا في خوارزمية الفقاعة بشرط توقف ، مما يسمح لك بتنظيم تباديل عناصر المصفوفة والتحكم في حالة التوقف. نظرا للحلقة الخارجية ، تقوم الخوارزمية بفرز المصفوفات بكفاءة ، وفي حالة طلب المصفوفة بالفعل ، تبطئ عملها وتتجنب التباديل غير الضروري.
ملامح تنفيذ حالة التوقف
طريقة الفقاعة هي واحدة من أبسط خوارزميات الفرز وأكثرها شيوعا. عند تنفيذه ، من المهم مراعاة ميزات حالة الإيقاف ، والتي تتيح لك توفير وقت التنفيذ وتجنب التكرارات غير الضرورية.
الفكرة الرئيسية لطريقة الفقاعة هي مقارنة أزواج عناصر الصفيف المجاورة ثم استبدالها إذا كانت بترتيب خاطئ. يتم تكرار هذا الإجراء حتى يتم فرز المصفوفة بالكامل.
تتمثل إحدى ميزات تنفيذ طريقة الفقاعة في حالة التوقف بناء على عدم وجود تبادلات في الخطوة التالية من الدورة الخارجية. أثناء كل تكرار للحلقة الخارجية ، يتم التحقق مما إذا كان قد تم تنفيذ إجراء تبادل واحد على الأقل على الممر الحالي. إذا لم يتم إجراء أي تبادلات ، فهذا يعني أن المصفوفة قد تم فرزها بالفعل ، ولا يلزم إجراء المزيد من التكرارات.
في حالة عدم تنفيذ شرط الإيقاف ، سيتم تنفيذ الخوارزمية حتى يتم فرز المصفوفة بالكامل ، بغض النظر عن ترتيبها الأولي. هذا يمكن أن يؤدي إلى عمليات تبادل غير ضرورية وزيادة كبيرة في وقت التنفيذ.
عند تنفيذ شرط الإيقاف في طريقة الفقاعة ، يوصى باستخدام علامة تشير إلى وجود تبادلات على الممر الحالي. قبل بدء الحلقة الخارجية ، يتم تعيين العلم على "خطأ". داخل الحلقة الخارجية ، يتم التحقق من وجود التبادلات ، وإذا كان هناك أي منها ، يتم تعيين العلم على "صحيح". أيضا ، بعد نهاية الحلقة الداخلية ، يتم فحص قيمة العلم ، وإذا بقيت "خاطئة" ، فستتوقف الحلقة.
وبالتالي ، فإن تنفيذ حالة التوقف يسمح لك بتسريع تنفيذ طريقة الفقاعة بشكل كبير وتقليل عدد العمليات لتبادل عناصر المصفوفة.
تطبيق طريقة الفقاعة مع حالة توقف
طريقة الفقاعة هي واحدة من أبسط الخوارزميات لفرز المصفوفات. إنه سهل التنفيذ ، لكنه قد يكون غير فعال مع وجود كميات كبيرة من البيانات.
تعتمد طريقة الفقاعة على فكرة مقارنة عناصر المصفوفة المجاورة وتبادلها ، مما يسمح لأكبر العناصر "بالطفو" تدريجيا على السطح. ومع ذلك ، يمكن أن يؤدي هذا إلى سلوك غير فعال للخوارزمية عندما يتم فرز المصفوفة بالفعل أو تحتوي على أقسام مرتبة جزئيا.
لذلك ، تم اقتراح إضافة شرط لإيقاف الحلقة الخارجية ، والتي ستتحقق مما إذا كانت التبادلات قد حدثت في التكرار التالي. إذا لم تحدث أي تبادلات ، فهذا يشير إلى أن المصفوفة قد تم فرزها بالفعل ولا يلزم إجراء المزيد من التكرارات.
يسمح لك استخدام طريقة الفقاعة بشرط التوقف بتقليل عدد التكرارات للخوارزمية بشكل كبير في الحالات التي يتم فيها فرز المصفوفة بالفعل أو فرزها جزئيا. هذا يحسن كفاءة الخوارزمية ويقلل من وقت الفرز للمصفوفة.
عادة ما يتم تنفيذ حالة التوقف بواسطة حلقة خارجية من خلال عناصر المصفوفة. إذا لم تحدث أي تبادلات أثناء التكرار التالي ، فسيظل متغير العلم دون تغيير ، وسيتم مقاطعة الحلقة الخارجية.
على سبيل المثال ، في الكود الكاذب ، قد تبدو الخوارزمية ذات حالة التوقف كما يلي:
- اضبط علامة" التبادلات موجودة " على "صحيح"
- طالما تم تعيين علامة" التبادلات " على "صحيح" ، قم بتنفيذ الإجراءات التالية:
- اضبط علامة" التبادلات " على "خطأ"
- لتجاوز المصفوفة ومقارنة العناصر المجاورة
- إذا كان من الضروري إجراء تبادل ، فقم بتعيين علامة" التبادلات " على "صحيح"
وبالتالي ، فإن استخدام طريقة الفقاعة بشرط التوقف يسمح لك بتسريع فرز المصفوفة في الحالات التي يتم فيها فرزها بالفعل أو فرزها جزئيا. هذا يجعل الخوارزمية أكثر كفاءة ويجعل من الممكن توفير الوقت عند معالجة كميات كبيرة من البيانات.
مزايا وعيوب الطريقة
المزايا:
- سهولة التنفيذ. طريقة الفقاعة سهلة الفهم والكتابة ، حتى بالنسبة للمبرمجين المبتدئين.
- القدرة على الفرز في أي اتجاه. تسمح لك طريقة الفقاعة بفرز العناصر بترتيب تصاعدي وتنازلي ببساطة عن طريق تغيير حالة المقارنة.
- أداء جيد للمصفوفات التي تم فرزها بالفعل. إذا تم فرز المصفوفة بالفعل أو كانت قريبة من الحالة التي تم فرزها ، فيمكن تنفيذ طريقة الفقاعة في ا(ن) العمليات ، أين ن هو عدد العناصر في المصفوفة.
العيوب:
- ضعف الأداء في المتوسط وأسوأ الحالات. في أسوأ الحالات ، عندما يتم فرز المصفوفة بترتيب عكسي ، تتطلب طريقة الفقاعة ا (ن^2) العمليات ، أين ن هو عدد العناصر في المصفوفة.
- عدم كفاءة المصفوفات الكبيرة. عند فرز المصفوفات الكبيرة ، قد تستغرق طريقة الفقاعة الكثير من الوقت والموارد.
- عدم الاستقرار. لا تحافظ طريقة الفقاعة على ترتيب العناصر المتساوية ، لذلك يطلق عليها طريقة الفرز غير المستقرة.
وبالتالي ، على الرغم من بساطة التنفيذ والقدرة على الفرز في كلا الاتجاهين ، فإن الأداء البطيء وعدم الاستقرار يجعل طريقة الفقاعة خيارا أقل تفضيلا لفرز المصفوفات الكبيرة. ومع ذلك ، بالنسبة للمصفوفات الصغيرة وفي حالة البيانات التي تم فرزها بالفعل ، يمكن أن تكون هذه الطريقة مفيدة وسهلة الاستخدام.
سؤال وجواب
كيف تعمل طريقة الفقاعة مع حالة التوقف?
طريقة الفقاعة بشرط التوقف هي خوارزمية فرز تعيد ترتيب العناصر عن طريق مقارنة جيرانها بالتسلسل وتبادلها إذا كانت بترتيب خاطئ. على عكس طريقة الفقاعة المعتادة ، تتوقف هذه الطريقة عن العمل إذا لم يتم إجراء أي تبادلات في الخطوة التالية من الدورة الخارجية. وبالتالي ، فإنه يسرع بشكل كبير عملية الفرز إذا تم فرز المصفوفة بالفعل أو تتطلب الحد الأدنى من التبادلات.
ما هو تعقيد طريقة فقاعة مع حالة توقف?
يعتمد تعقيد طريقة الفقاعة مع حالة التوقف على بيانات الإدخال. في أفضل الأحوال ، عندما يتم فرز المصفوفة بالفعل ، يكون تعقيد الخوارزمية س (ن) ، أين ن هو عدد العناصر في المصفوفة. في أسوأ الحالات ، عندما يتم فرز المصفوفة بترتيب عكسي ، يكون تعقيد الخوارزمية س (ن^2). في الحالة المتوسطة ، يتم تقدير التعقيد أيضا س (ن^2).
كيف يمكنني التحقق من أن طريقة الفقاعة مع حالة التوقف ستقوم بفرز المصفوفة بشكل صحيح?
للتحقق من التشغيل الصحيح لطريقة الفقاعة بشرط الإيقاف ، يمكن استخدام النهج التالي: 1) إنشاء مصفوفة اختبار بقيم معروفة ؛ 2) فرز هذه المصفوفة باستخدام طريقة الفقاعة بشرط الإيقاف ؛ 3) قارن المصفوفة المصنفة الناتجة بالنتيجة المتوقعة. إذا كانت متطابقة ، فهذا يعني أن الطريقة تعمل بشكل صحيح.
ماذا يحدث إذا كانت الحلقة الداخلية لطريقة الفقاعة مع حالة توقف لا تؤدي أي تبادلات في خطوة معينة?
إذا كانت الحلقة الداخلية لطريقة الفقاعة بشرط التوقف لا تؤدي أي تبادلات في خطوة معينة ، فهذا يعني أن المصفوفة قد تم فرزها بالفعل ولا تتطلب المزيد من التبادلات. في هذه الحالة ، تتوقف الخوارزمية عن العمل ، وتعود المصفوفة إلى حالتها الأصلية.