אלגוריתמי מיון מוסברים בפשטות

מיון זו אחת הבעיות הראשונות שכל מתכנת פוגש, ולמרות זה היא נשארת נושא שגורם לבלבול. הסיבה היא שרוב האנשים מלמדים אתכם חמישה אלגוריתמי מיון שונים בבת אחת, בלי לעצור ולהסביר למה בכלל צריך יותר מאחד. אז בואו נעשה את זה הפוך.

למה יש בכלל כמה שיטות למיין רשימה

בהינתן רשימה של מספרים לא מסודרים, המטרה תמיד זהה - לסדר אותם מהקטן לגדול (או הפוך). אבל הדרך להגיע לשם משנה דרמטית את המהירות, במיוחד כשהרשימה גדולה. שיטה שעובדת מצוין על עשרה מספרים יכולה להיתקע לדקות שלמות על מיליון מספרים. זו הסיבה שיש כמה שיטות - כל אחת מציעה פשרה שונה בין פשטות לביצועים.

מיון בועות - Bubble Sort: השיטה הכי אינטואיטיבית

תדמיינו שאתם עוברים על שורה של אנשים לפי גובה, ובכל פעם שאתם רואים שני אנשים סמוכים בסדר הפוך - הגבוה לפני הנמוך - אתם מחליפים ביניהם. אתם עוברים ככה שוב ושוב על כל השורה, עד שאף החלפה לא נדרשת יותר, מה שאומר שהכל מסודר.

זה מיון בועות, וזה נקרא ככה כי הערכים הגדולים "מבעבעים" לאט לאט לסוף הרשימה. השיטה הזו קלה מאוד להבנה ולכתיבה, אבל היא איטית מאוד על רשימות גדולות - כי בגרוע ביותר, אתם עוברים על הרשימה שוב ושוב פעמים רבות. בעולם האמיתי כמעט אף אחד לא משתמש בה, אבל היא נהדרת ללימוד כי היא חושפת בדיוק את הרעיון של "השוואה והחלפה".

מיון מיזוג - Merge Sort: חלק, כבוש, אחד

הנה רעיון הרבה יותר חכם. אם יש לכם ערימה גדולה של דפים לא ממוספרים למיין, במקום להשוות כל דף לכל דף, תחלקו את הערימה לשתיים, תבקשו מחבר למיין חצי, אתם תמיינו את החצי השני, ואז פשוט תמזגו בין שתי הערימות הממוינות - משווים כל פעם רק את שני הדפים העליונים ובוחרים את הקטן מביניהם.

זה בדיוק מיון מיזוג. הוא מחלק את הרשימה לחצאים שוב ושוב עד שנשארים איברים בודדים, ואז מאחד אותם בחזרה תוך שמירה על סדר. הגישה הזו נקראת "חלק ומשול" - divide and conquer - והיא אחד הרעיונות החזקים ביותר במדעי המחשב, כי היא מנצלת רקורסיה כדי להפוך בעיה גדולה לכמה בעיות קטנות וזהות.

התוצאה היא שיפור עצום בביצועים על רשימות גדולות, במחיר של קוד קצת יותר מורכב.

מיון מהיר - Quick Sort: הכוכב בפועל

מיון מהיר עובד לפי רעיון דומה של חלק ומשול, אבל בצורה שונה. בוחרים איבר "ציר" מהרשימה, מעבירים את כל האיברים הקטנים ממנו שמאלה ואת כל הגדולים ממנו ימינה, ואז חוזרים על אותו תהליך בכל צד בנפרד. בממוצע הוא מהיר מאוד, וזו הסיבה שהוא נמצא מאחורי הקלעים של רוב הפונקציות המובנות למיון בשפות תכנות מודרניות.

אז איזה מהם כדאי לדעת

התשובה הכנה: בעבודה יומיומית, אתם כמעט אף פעם לא תכתבו אלגוריתם מיון בעצמכם. בפייתון פשוט כותבים sorted(list) והמערכת עושה את העבודה עבורכם, עם מימוש מהיר ומעולה שכבר נבדק ואופטם על ידי אנשים חכמים מאוד. אז למה בכלל ללמוד את זה?

כי הרעיונות שמאחורי אלגוריתמי המיון - השוואה, חלוקה, רקורסיה, ניתוח יעילות - הם בדיוק סוג החשיבה שנדרש כדי לפתור כל בעיה אלגוריתמית אחרת. וכן, זו גם שאלה קלאסית בראיונות עבודה בהייטק, אז שווה לדעת להסביר לפחות את הרעיון מאחורי מיון מיזוג ומיון מהיר, גם בלי לשנן כל שורת קוד בעל פה.

איך לתרגל את זה נכון

תכתבו מיון בועות מאפס, זה הכי קל. אחר כך תנסו לממש מיון מיזוג - זה מאתגר יותר כי דורש חשיבה רקורסיבית, אבל ברגע שזה "נופל" לכם, זו אחת התחושות הכי מספקות בלימוד תכנות.

בקורס התכנות הבסיסי שלנו יש תרגילים בדיוק על זה, שבונים אתכם בהדרגה מהיסודות ועד לאלגוריתמים האלה.

תתחילו את קורס התכנות הבסיסי כאן

לסיכום

מיון בועות מלמד אתכם את הרעיון הבסיסי, מיון מיזוג ומיון מהיר מראים לכם איך חושבים בחכמה יותר עם חלק ומשול. בפועל תשתמשו בפונקציית מיון מובנית כמעט תמיד, אבל ההבנה של מה שקורה מאחוריה היא מה שהופכת אתכם למתכנתים טובים יותר.

יש לכם שאלה בדרך? בואו לדיסקורד שלנו ותשאלו.

הצטרפו לקהילה בדיסקורד