قطع القائمة إلى النصف

البحث الثنائي: القفز إلى المنتصف

البحث الثنائي له قاعدة واحدة: يجب أن تكون القائمة مرتبة أولاً.

إذا كانت قائمتك المكونة من 20 اسماً تذهب من A إلى Z، يمكنك استخدام البحث الثنائي.

كيف يعمل: افتح في الاسم الأوسط (الاسم #10). اسأل: هل يأتي Zoe قبل أم بعد هذا الاسم؟

Z يأتي بالقرب من نهاية الأبجدية، لذا يأتي Zoe بعد المنتصف. تخلص من النصف الأول. الآن لديك فقط الأسماء 11-20 المتبقية.

تحقق من منتصف هذه الأسماء العشرة (الاسم #15). Z يأتي بعد M، لذا Zoe يأتي بعد الاسم #15. تخلص من الأسماء 11-14. الآن لديك الأسماء 16-20.

استمر في القطع إلى النصف. كل فحص يزيل نصف الأسماء المتبقية.

قارن ذلك مع البحث الخطي على 1,000,000 اسم: متوسط 500,000 فحص.

يقطع البحث الثنائي القائمة إلى النصف في كل مرة. القطع إلى النصف مراراً يصل إلى 1 بسرعة — لهذا يبقى سريعاً جداً.

ابحث عن 'fig' في قائمة مرتبة

إليك قائمة مرتبة من 8 كلمات:

1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew

تريد إيجاد fig باستخدام البحث الثنائي.

تذكر: تحقق من المنتصف، اسأل إذا كان هدفك يأتي قبل أم بعد، ثم قطع القائمة إلى النصف.

تبديل الجيران ليصبحوا مرتبين

فرز الفقاعة: قارن الجيران وبدّلهم

يرتب فرز الفقاعة القائمة بمقارنة عنصرين متجاورين في كل مرة.

إذا كان الجاران غير مرتبين — بدّلهما.

استمر في عمل جولات عبر القائمة حتى لا يحتاج شيء إلى تبديل.

مثال: رتّب [5, 3, 8, 1]

الجولة 1:

- قارن 5 و 3. 5 > 3، لذا بدّل → [3, 5, 8, 1]

- قارن 5 و 8. 5 < 8، لا تبديل → [3, 5, 8, 1]

- قارن 8 و 1. 8 > 1، لذا بدّل → [3, 5, 1, 8]

الجولة 2:

- قارن 3 و 5. حسناً → [3, 5, 1, 8]

- قارن 5 و 1. 5 > 1، بدّل → [3, 1, 5, 8]

- قارن 5 و 8. حسناً → [3, 1, 5, 8]

الجولة 3:

- قارن 3 و 1. 3 > 1، بدّل → [1, 3, 5, 8]

- قارن 3 و 5. حسناً. قارن 5 و 8. حسناً.

انتهى! [1, 3, 5, 8] ✓

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

يعمل فرز الفقاعة. إنه ليس الأسرع للقوائم الكبيرة، لكنه سهل الفهم — مثالي للتعلم.

رتّب [4, 2, 7, 1] بفرز الفقاعة

رتّب هذه القائمة باستخدام فرز الفقاعة: [4, 2, 7, 1]

أظهر القائمة بعد كل جولة كاملة. احسب كم جولة يستغرق الانتهاء.