מיריחיפוש ומיון איך מחשב מוצא ומסדר
חנות עם אלף מוצרים, טבלת שיאים במשחק, רשימת ציונים: המחשב צריך למצוא ערך ולסדר רשימות כל הזמן. כאן משווים שתי דרכים לחפש, סופרים כמה בדיקות כל אחת עושה, ומסדרים רשימה במיון בועות. כדאי להכיר קודם רשימות ולולאות.
הרעיון
חיפוש לינארי
עוברים על הרשימה מההתחלה, איבר אחרי איבר, עד שמוצאים. עובד בכל רשימה, גם לא מסודרת. ברשימה של 1000 איברים זה יכול לקחת 1000 בדיקות.
חיפוש בינארי
עובד רק ברשימה ממוינת. בודקים את האמצע. אם הערך שם, סיימנו. אם הוא גדול יותר, ממשיכים רק בחצי הימני, ואם קטן, בחצי השמאלי. כל בדיקה זורקת חצי. ב-1000 איברים מספיקות 10 בדיקות.
מיון בועות
עוברים על הרשימה ומשווים כל שני שכנים. אם הם בסדר הפוך, מחליפים ביניהם. אחרי כל מעבר הגדול ביותר "מבעבע" לסוף. חוזרים על זה עד שאין יותר החלפות.
מעבדה: מי מוצא מהר יותר?
ברשימה יש מחירים ממוינים של מוצרים בחנות. בחרו שיטת חיפוש, את אורך הרשימה ואת המחיר שמחפשים. הריצו שורה אחרי שורה: הקופסה הצהובה היא האיבר שבודקים עכשיו, והקופסאות החיוורות כבר לא רלוונטיות.
מתחת לכל קופסה: האינדקס שלה
נסו את אלה:
הריצו בעצמכם
אפשר לשנות את הקוד ולהריץ פייתון אמיתי. בפעם הראשונה הטעינה לוקחת כמה שניות.
טעויות שכולם עושים
חיפוש בינארי ברשימה לא ממוינת
החיפוש זורק חצי לפי ההשוואה לאמצע. אם הרשימה לא ממוינת, הוא עלול לזרוק בדיוק את החצי שבו הערך נמצא.
✗ לא נכון
nums = [9, 2, 7, 4, 5]
# binary search for 9
# → not found!✓ נכון
nums = [9, 2, 7, 4, 5]
nums.sort()
# [2, 4, 5, 7, 9]high מתחיל ב-len
האינדקס האחרון הוא len(nums) - 1. אם high מתחיל ב-len(nums), האמצע עלול לצאת מחוץ לרשימה.
✗ לא נכון
high = len(nums)✓ נכון
high = len(nums) - 1לולאה שלא נגמרת
אחרי בדיקת האמצע חייבים לזוז מעבר לו: mid + 1 או mid - 1. אם כותבים low = mid, אפשר להיתקע על אותו איבר לנצח.
✗ לא נכון
low = mid✓ נכון
low = mid + 1החלפה שמוחקת ערך
במיון בועות מחליפים שני שכנים. אם כותבים שתי השמות רגילות, הערך הראשון נדרס. בפייתון מחליפים בשורה אחת.
✗ לא נכון
a[i] = a[i + 1]
a[i + 1] = a[i]✓ נכון
a[i], a[i + 1] = a[i + 1], a[i]דוגמה פתורה: מיון בועות
ממיינים ארבעה ציונים במבחן מהקטן לגדול. בכל מעבר משווים שכנים ומחליפים אם צריך. שימו לב לשורה swaps: היא סופרת כמה החלפות היו במעבר. כשמעבר שלם עובר בלי החלפות, הרשימה ממוינת ועוצרים.
תרגול
שאלות שכולם שואלים
מה ההבדל בין חיפוש לינארי לחיפוש בינארי?
חיפוש לינארי בודק איבר אחרי איבר מההתחלה, ועובד בכל רשימה. חיפוש בינארי בודק את האמצע וזורק חצי בכל צעד, אבל עובד רק ברשימה ממוינת. ברשימה של 1000 איברים לינארי עלול לבדוק 1000 פעמים, ובינארי לא יותר מ-10. נסו במעבדה.
איך עובד מיון בועות?
משווים כל שני שכנים ברשימה ומחליפים אותם אם הם בסדר הפוך. אחרי מעבר אחד האיבר הגדול ביותר מגיע לסוף. חוזרים על המעברים עד שעובר מעבר שלם בלי אף החלפה. השיטה פשוטה להבנה, אבל איטית ברשימות ארוכות.
למה חיפוש בינארי כל כך מהיר?
כי כל בדיקה מחלקת את מה שנשאר לשניים. 1000 הופך ל-500, אחר כך 250, 125 וכן הלאה. אחרי כ-10 חלוקות נשאר איבר אחד. גם ברשימה של מיליון איברים מספיקות בערך 20 בדיקות. תרגלו למטה.