فحص واحد بعد الآخر
بحث خطي: تحقق عن كل واحد
تخيل أن لديك 10 بطاقات مواجهة أدناه، مرقمة من 1 إلى 10، مُشغلة في ترتيب عشوائي.
ترغب في إيجاد البطاقة التي تحتوي على الرقم 7.
تبدأ بتحريك البطاقات واحدة تلو الأخرى، من اليسار إلى اليمين، حتى تجدها.
| السيناريو | عدد التحولات المطلوبة |
|----------|-------------|
| الحالة الأفضل | 1 تحرك (حظ أول تجربة!) |
| الحالة الأسوأ | 10 تحركات (كانت هي البطاقة الأخيرة) |
| المتوسط | حوالي 5 تحركات |
انظر إلى 100 بطاقة. المتوسط حوالي 50 تحرك.
1000 بطاقة؟ المتوسط حوالي 500 تحرك.
هل ترى المُخطط؟ تضاعف عدد البطاقات، تضاعف العمل. ينمو العمل مثل السطر: مستقيم ومرتكز.
يُسمى هذا من قبل علماء الحاسوب بحث خطي - الخطي يعني أن العمل ينمو مثل السطر: مستقيم ومرتكز.
بحث خطي يعمل على أي قائمة، مرتبة أو غير مرتبة. وهذا يجعلها بسيطة. لكنها قد تصبح بطيئة.
كم عدد الأسماء؟
لدي قائمة صفوفك 20 اسمًا مكتوبة في ترتيب عشوائي.
تحتاج إلى إيجاد الاسم زوي.
تبحث في الأسماء واحدة تلو الأخرى، من أعلى القائمة إلى الأسفل.
قص القائمة إلى نصفين
البحث البيني: التوجه إلى الوسط
يحتاج البحث البيني إلى قاعدة واحدة: يجب ترتيب القائمة أولاً.
إذا كانت قائمة 20 اسمًا تذهب من أ إلى ز، يمكنك استخدام البحث البيني.
كيف يعمل: فتح إلى الاسم الوسط (اسم # 10). اسأل: هل زوي قبل هذا الاسم أو بعده؟
تأتي ز في نهاية القاموس، لذا زوي تأتي بعد الوسط. ألقِ بالنسبة الأولى. الآن لديك فقط الأسماء 11-20 المتبقية.
تحقق من الوسط من تلك 10 الأسماء (اسم # 15). تأتي ز بعد م، لذا زوي تأتي بعد اسم # 15. ألقِ بأسماء 11-14. الآن لديك الأسماء 16-20.
استمر في القص النصفية. يتم إزالة كل تحقق نصف الأسماء المتبقية.
| حجم القائمة | التحقيقات الأقصى مع البحث البيني |
|-----------|-------------------------------|
| 20 اسمًا | في أقصى حد 5 تحقيقات |
| 1,000 اسمًا | في أقصى حد 10 تحقيقات |
| 1,000,000 اسمًا | في أقصى حد 20 تحقيقات |
مقارنة ذلك بناء الخطي على 1,000,000 اسمًا: متوسط تحقيق 500,000 تحقيقات.
يقلص البحث البيني القائمة إلى النصف كل مرة. يصل القص النصفية إلى 1 بسرعة - وهذا هو السبب في أن يظل سريعًا.
إيجاد 'fig' في قائمة ترتيبها
هنا قائمة ترتيبها مرتبة:
1. توت 2. موز 3. شوكرة 4. تاج 5. شجرة العنب 6. fig 7. زهرة 8. تفاح المليون
ترغب في إيجاد fig باستخدام البحث البيني.
تذكّر: التحقق من الوسط، وسؤال إذا جاء الهدف قبل هذا أو بعد ذلك، ثم القص النصفية للقائمة.
تبديل الجيران إلى الترتيب
ترتيب فقاعات: مقارنة الجيران وتبديلها
Bubble sort puts a list in order by comparing two neighboring items at a time.
If two neighbors are out of order — swap them.
Keep making passes through the list until nothing needs swapping.
Example: sort [5, 3, 8, 1]
Pass 1:
- Compare 5 & 3. 5 > 3, so swap → [3, 5, 8, 1]
- Compare 5 & 8. 5 < 8, no swap → [3, 5, 8, 1]
- Compare 8 & 1. 8 > 1, so swap → [3, 5, 1, 8]
Pass 2:
- Compare 3 & 5. OK → [3, 5, 1, 8]
- Compare 5 & 1. 5 > 1, swap → [3, 1, 5, 8]
- Compare 5 & 8. OK → [3, 1, 5, 8]
Pass 3:
- Compare 3 & 1. 3 > 1, swap → [1, 3, 5, 8]
- Compare 3 & 5. OK. Compare 5 & 8. OK.
Done! [1, 3, 5, 8] ✓
Notice: the biggest number bubbles to the end of the list on each pass. That is how bubble sort gets its name.
Bubble sort works. It is not the fastest for big lists, but it is easy to understand — perfect for learning.
Sort [4, 2, 7, 1] with Bubble Sort
Sort this list using bubble sort: [4, 2, 7, 1]
Show the list after each pass. Count how many passes it takes to finish.