שיעור 9: מיון ומפתחות מותאמים

דמיין/י מדף ספרים בלי סדר, ואת/ה רוצה לסדר אותם לפי גובה. זה 'מיון' (sorting), וב-Python יש כלי מוכן — sorted — שעושה את העבודה. עם key=... בוחרים לפי מה למיין, ועם reverse=True הופכים את הסדר. המיון של Python 'יציב' ועולה O(n log n). הכישרון האמיתי בראיון: לזהות מתי מיון מוקדם הופך בעיה קשה לקלה.

מיון זה כמו לסדר חבילת קלפים לפי הסדר. ה-key הוא הדרך לומר 'לפי מה לסדר' — לפי המספר, לפי הצבע, או קודם לפי הצבע ואז לפי המספר. ו-reverse=True פשוט אומר 'סדר מהגדול לקטן'.

מיון: סידור אוסף לפי סדר מוגדר. מיון מבוסס-השוואות אורך O(n log n) במקרה הכללי.
מפתח מיון (key): פונקציה שמחזירה לכל איבר את הערך שלפיו ממיינים, למשל key=lambda x: x[1] ממיין לפי האיבר השני.
מיון יציב: מיון שבו איברים בעלי מפתח זהה שומרים על סדרם המקורי. המיון של Python יציב.