Bubblه فرز الخوارزمية مع Python باستخدام مثال القائمة

ما هو Bubblه فرز؟

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

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

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

تنفيذ Bubblخوارزمية الفرز

سنقوم بتقسيم التنفيذ إلى ثلاث (3) خطوات، وهي المشكلة والحل والخوارزمية التي يمكننا استخدامها لكتابة التعليمات البرمجية لأي لغة.

المشكلة

تم تقديم قائمة من العناصر بترتيب عشوائي، ونرغب في ترتيب العناصر بطريقة منظمة.

خذ بعين الاعتبار القائمة التالية:

[21, 6, 9, 33, 3]

الحل

قم بالمرور على القائمة ومقارنة عنصرين متجاورين ثم تبديلهما.ping يتم تطبيق ذلك عليهما إذا كانت القيمة الأولى أعلى من القيمة الثانية.

يجب أن تكون النتيجة كما يلي:

[3, 6, 9, 21, 33]

خوارزمية

تعمل خوارزمية فرز الفقاعات على النحو التالي:

الخطوة 1) احصل على العدد الإجمالي للعناصر. احصل على العدد الإجمالي للعناصر في القائمة المعطاة.

الخطوة 2) حدد عدد مرات المرور الخارجية (n – 1) المطلوب إجراؤها. طولها يساوي القائمة ناقص واحد.

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

الخطوة 4) كرر الخطوات من 3 حتى تصل إلى المرحلة الخارجية (n – 1). احصل على العنصر التالي في القائمة، ثم كرر العملية التي تم تنفيذها في الخطوة 3 حتى يتم وضع جميع القيم بترتيبها التصاعدي الصحيح.

الخطوة 5) أعد النتيجة بعد إتمام جميع العمليات. أعد نتائج القائمة المرتبة.

الخطوة 6) تحسين الخوارزمية.

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

الأمثل Bubblخوارزمية الفرز

بشكل افتراضي، خوارزمية فرز الفقاعات في Python يقارن كل العناصر في القائمة بغض النظر عما إذا كانت القائمة مرتبة بالفعل أم لا. إذا كانت القائمة المقدمة مرتبة بالفعل، فإن مقارنة كل القيم تعتبر مضيعة للوقت والموارد.

يساعدنا تحسين نوع الفقاعة على تجنب التكرارات غير الضرورية وتوفير الوقت والموارد.

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

تتم عملية التحسين باستخدام الخطوات التالية:

الخطوة 1) أنشئ متغيرًا للعلامة لمراقبة ما إذا كان هناك أي تبديلping حدث ذلك في الحلقة الداخلية.

الخطوة 2) إذا تبادلت القيم مواقعها، فانتقل إلى التكرار التالي.

الخطوة 3) إذا لم تتبادل القيم مواقعها، فقم بإنهاء الحلقة الداخلية، واستمر في الحلقة الخارجية.

يعد فرز الفقاعات المحسّن أكثر كفاءة لأنه ينفذ فقط الخطوات الضرورية ويتخطى تلك غير المطلوبة.

التمثيل المرئي

بالنظر إلى قائمة مكونة من خمسة عناصر، توضح الصور التالية كيف يقوم فرز الفقاعات بالتكرار عبر القيم عند فرزها.

تُظهر الصورة التالية القائمة غير المصنفة:

التكرار الأول

الخطوة 1)

تتم مقارنة القيمتين 21 و6 للتحقق من أيهما أكبر من الآخر.

العدد 21 أكبر من العدد 6، لذا فإن العدد 21 يأخذ الموضع الذي كان يشغله العدد 6 بينما يأخذ العدد 6 الموضع الذي كان يشغله العدد 21.

تبدو قائمتنا المعدلة الآن مثل تلك المذكورة أعلاه.

الخطوة 2)

تتم مقارنة القيمتين 21 و9.

العدد 21 أكبر من العدد 9، لذلك نقوم بتبديل موضعي العددين 21 و9.

القائمة الجديدة هي كما هو موضح أعلاه.

الخطوة 3)

تتم مقارنة القيمتين 21 و33 للعثور على القيمة الأكبر.

القيمة 33 أكبر من 21، لذا لا يوجد تبديل.ping تأخذ مكان.

الخطوة 4)

تتم مقارنة القيمتين 33 و3 للعثور على القيمة الأكبر.

القيمة 33 أكبر من 3، لذلك نقوم بتبديل مراكزهم.

القائمة المرتبة في نهاية التكرار الأول تشبه القائمة أعلاه.

التكرار الثاني

القائمة الجديدة بعد التكرار الثاني هي كالتالي:

التكرار الثالث

القائمة الجديدة بعد التكرار الثالث هي كالتالي:

التكرار الرابع

القائمة الجديدة بعد التكرار الرابع هي كالتالي:

Python أمثلة

يوضح الكود التالي كيفية تنفيذ Bubblه خوارزمية الفرز في Python.

def bubbleSort(theSeq):
    n = len(theSeq)

    for i in range(n - 1):
        flag = 0

        for j in range(n - 1):
            if theSeq[j] > theSeq[j + 1]:
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21, 6, 9, 33, 3]
result = bubbleSort(el)
print(result)

تنفيذ برنامج فرز الفقاعات أعلاه في Python ينتج عنه النتائج التالية:

[3, 6, 9, 21, 33]

Code تفسير

التفسير ل Python Bubblشفرة برنامج الفرز الإلكتروني هي كما يلي:

هنا،

1. يحدد وظيفة bubbleSort التي تقبل المعلمة theSeq. الكود لا يخرج أي شيء.
2. يحصل على طول المصفوفة ويسند القيمة إلى متغير n. لا يُخرج الكود أي شيء.
3. يبدأ حلقة تكرارية (for loop) تُنفّذ خوارزمية فرز الفقاعات (n – 1) مرة. هذه هي الحلقة الخارجية. لا يُخرج الكود أي شيء.
4. يُعرّف هذا الكود متغيرًا يُستخدم لتحديد ما إذا كان قد حدث تبديل أم لا، وذلك لأغراض تحسين الأداء. ولا يُخرج الكود أي بيانات.
5. يبدأ الحلقة الداخلية التي تقارن كل القيم في القائمة من الأولى إلى الأخيرة. لا ينتج الكود أي شيء.
6. يستخدم عبارة if للتحقق مما إذا كانت القيمة الموجودة على الجانب الأيسر أكبر من القيمة الموجودة على الجانب الأيمن مباشرة. الكود لا يخرج أي شيء.
7. يُسند قيمة `theSeq[j]` إلى متغير مؤقت `tmp` إذا كان الشرط صحيحًا. لا يُخرج الكود أي شيء.
8. تُسند قيمة `theSeq[j + 1]` إلى موضع `theSeq[j]`. لا يُخرج الكود أي شيء.
9. تُسند قيمة المتغير tmp إلى الموضع theSeq[j + 1]. لا يُخرج الكود أي شيء.
10. يُسند للمتغير flag القيمة 1 للإشارة إلى حدوث عملية تبديل. لا يُخرج البرنامج أي بيانات.
11. يستخدم عبارة شرطية للتحقق مما إذا كانت قيمة المتغير flag تساوي 0. لا يُخرج الكود أي شيء.
12. إذا كانت القيمة 0، فإننا نسمي عبارة Break التي تخرج من الحلقة الداخلية.
13. إرجاع قيمة theSeq بعد فرزها. يقوم الكود بإخراج القائمة التي تم فرزها.
14. يحدد متغير el يحتوي على قائمة من الأرقام العشوائية. لا يقوم الكود بإخراج أي شيء.
15. يعين قيمة الدالة bubbleSort لنتيجة متغيرة.
16. طباعة قيمة النتيجة المتغيرة.

Bubblمزايا الفرز

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

• إنها سهلة لتفهم.
• يؤدي أداءً جيداً للغاية عندما تكون القائمة مرتبة بالفعل أو شبه مرتبة.
• أنها لا تتطلب ذاكرة واسعة النطاق.
• من السهل كتابة الكود الخاص بالخوارزمية.
• متطلبات المساحة ضئيلة مقارنة بخوارزميات الفرز الأخرى.

Bubblه فرز العيوب

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

• لا يعمل بشكل جيد عند فرز القوائم الكبيرة. يستغرق الكثير من الوقت والموارد.
• يُستخدم في الغالب لأغراض أكاديمية وليس للتطبيقات العملية.
• عدد الخطوات المطلوبة لفرز القائمة هو بالترتيب n².

تحليل التعقيد Bubblه فرز

هناك ثلاثة أنواع من التعقيد:

1) تعقيد الفرز

يُستخدم تعقيد الفرز للتعبير عن مقدار وقت التنفيذ والمساحة اللازمة لفرز القائمة. يقوم فرز الفقاعات بإجراء (n – 1) تكرارًا لفرز القائمة، حيث n هو العدد الإجمالي للعناصر في القائمة.

2) تعقيد الوقت

التعقيد الزمني لفرز الفقاعات هو O(n)²).

يمكن تصنيف التعقيدات الزمنية على النحو التالي:

• الحالة الأسوأ - هذا هو المكان الذي تكون فيه القائمة المقدمة بترتيب تنازلي. تنفذ الخوارزمية الحد الأقصى لعدد عمليات التنفيذ التي يتم التعبير عنها بـ [Big-O] O(n²).
• افضل حالة يحدث هذا عندما تكون القائمة المُقدمة مُرتبة بالفعل. تُنفذ الخوارزمية أقل عدد من عمليات التنفيذ، والذي يُعبر عنه بـ [Big-Omega] Ω(n).
• حالة متوسطة يحدث هذا عندما تكون القائمة مرتبة عشوائيًا. يُعبَّر عن متوسط ​​التعقيد بالصيغة [Big-theta] ⊝(n²).

3) تعقيد الفضاء

يقيس تعقيد المساحة مقدار المساحة الإضافية اللازمة لفرز القائمة. لا يتطلب فرز الفقاعات سوى مساحة إضافية واحدة (1) للمتغير الزمني المستخدم في عملية التبديل.ping القيم. لذلك، فإن تعقيد المساحة له هو O(1).

الأسئلة الشائعة