מימוש (חלק 2)
שיעור 6 מתוך 9 בקורס מיון הכנסה - סדרת DSA של Coddy.
תרחיש: מיון [5, 2, 9, 1, 5]
שלב 1: מצב התחלתי
- המערך המקורי: [5, 2, 9, 1, 5]
- דמיינו שזו היד שלנו עם הקלפים (או מערך המספרים).
שלב 2: האיבר הראשון (i=1, key=2)
- מתחילים בקלף השני (האיבר): key = 2.
- משווים את 2 ל-5 (האיבר היחיד שמוין עד כה).
- מכיוון ש-2 קטן יותר, מזיזים את 5 ימינה ומכניסים את 2 במקומו.
- המערך המעודכן: [2, 5, 9, 1, 5]
שלב 3: האיבר השני (i=2, key=9)
- עוברים לקלף הבא: key = 9.
- משווים את 9 ל-5.
- מכיוון ש-9 גדול יותר, אין צורך להזיז אותו.
- המערך המעודכן: [2, 5, 9, 1, 5] (ללא שינוי)
שלב 4: האיבר השלישי (i=3, key=1)
- עוברים לקלף הבא: key = 1.
- משווים את 1 ל-9, ואז ל-5.
- מזיזים את 9 ואת 5 ימינה, כדי לפנות מקום ל-1.
- המערך המעודכן: [1, 2, 5, 9, 5]
שלב 5: האיבר הרביעי (i=4, key=5)
- עוברים לקלף הבא: key = 5.
- משווים את 5 ל-9.
- מכיוון ש-5 קטן יותר, אין צורך להזיז אותו.
- המערך המעודכן: [1, 2, 5, 9, 5] (ללא שינוי)
שלב 6: האיבר החמישי (i=5, key=5)
- עוברים לקלף האחרון: key = 5.
- משווים את 5 ל-9.
- מכיוון ש-5 קטן יותר, אין צורך להזיז אותו.
- המערך המעודכן: [1, 2, 5, 5, 9]
התוצאה הסופית:
- המערך הממויין: [1, 2, 5, 5, 9]
בכל שלב בוחרים קלף (איבר), משווים אותו לאיברים שכבר מוינו וממקמים אותו במקום המתאים, תוך הזזת האחרים אם צריך. חוזרים על התהליך עד שכל המערך ממוין.
אתגר
קלכעת, מימשו את הלולאה הפנימית, שמבצעת את המיון עבור כל איבר.
השלימו את המיון בתוך הפונקציה insertionSort.
הפונקציה צריכה גם להדפיס את איברי המערך בסוף, אחד אחד, עם שורה חדשה ביניהם.
היעזרו בשיעורים הקודמים וברמז :)
נסו בעצמכם
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
print(key)
כל השיעורים ביחידה מיון הכנסה - סדרת DSA
תרגלו בעצמכם: קומפיילר C אונליין