מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג
תבנית:מבני נתונים ואלגוריתמים - מחברת קורס
דף זה עוסק במיון מערכים. נתון מערך, לדוגמה זה שבתרשים הבא, ועלינו למיין אותו בסדר (עולה, לצורך הדיון). נדון בשתי שיטות מיון: מיון הכנסה ומיון מיזוג.
מיון הכנסה
הרעיון הבסיסי
מיון הכנסה מבוסס על יצירת תחומים ממוינים גדלים והולכים, משמאל לימין, כבתרשים הבא:
בכל שלב שבו תחום (שמאלי) של המערך ממוין, האיבר הנוכחי מוכנס למקומו המתאים ע"י הזזת מספר איברים ימינה, והכנסת האיבר למקומו המתאים. התרשים הבא מראה זאת עבור F שבתרשים הקודם:
פסוודו-קוד
# Insertion sort.
# Takes an array (Values).
# Sorts the array in increasing order.
Insertion-Sort(Values)
1 for i in [1, ..., Length(Values)]
2 v = Values[i]
# Insert v into the correct position of Values[1, ..., i].
3 j = i
4 while j > 1 and Values[j - 1] > v
5 Values[j] = Values[j - 1]
6 --j
7 Values[j] = v
האינדקס תבנית:קוד בשורה מציין את החלק של תבנית:קוד בשורה המכיל תבנית:קוד בשורה איברים תבנית:קוד בשורה בסדר עולה. האינדקס תבנית:קוד בשורה משמש להזזת האיברים שיש להזיז כדי להכניס את תבנית:קוד בשורה למקום המתאים.
נכונות
סיבוכיות
נקבע כ את תבנית:קוד בשורה.
מיון מיזוג
הרעיון הבסיסי
מיון מיזוג מבוסס על הרעיון הבא. אם שני מערכים כבר ממוינים, קל למדי למזג אותם למערך ממוין גדול יותר. לכן, כדי למיין מערך, מחלקים אותו לשניים, ממיינים כ"א משני החלקים, וממזגים את התוצאות (הממויינות).
מיזוג מערכים ממויינים
ראשית, הנה הדרך למזג מערכים ממוינים:
מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג/מיון מיזוג/פסוודו-קוד לMerge
בשלב זה של הקורס, לא ייקשה עליך להוכיח את שני המשפטים הבאים:
פסוודו-קוד
נכתוב את אלגוריתם המיון בעזרת אלגוריתם המיזוג:
מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון מיזוג/פסוודו-קוד
נכונות
נוכיח כעת את נכונות מיון מיזוג.
סיבוכיות
שוב, נקבע כ את תבנית:קוד בשורה.