ישנם מספר אלגוריתמים בסיסיים לפתרון הבעיה של מיון מערך. אחד המפורסמים שבהם הוא מיון ההכנסה. בשל הבהירות והפשטות שלה, אך היעילות הנמוכה, שיטה זו משמשת בעיקר בהוראת תכנות. זה מאפשר לך להבין את מנגנוני המיון הבסיסיים.
תיאור האלגוריתם
מהות אלגוריתם מיון ההוספה היא שקטע מסודר כהלכה נוצר בתוך המערך הראשוני. כל אלמנט מושווה בזה אחר זה עם החלק המסומן ומוכנס למקום הנכון. לפיכך, לאחר איטרציה בין כל האלמנטים, הם מסתדרים בסדר הנכון.
סדר בחירת האלמנטים יכול להיות כל אחד, ניתן לבחור אותם באופן שרירותי או לפי אלגוריתם כלשהו. לרוב, נעשה שימוש בספירה רציפה מתחילת המערך, שם נוצר קטע מסודר.
תחילת המיון עשויה להיראות כך:
- קח את הרכיב הראשון של המערך.
- מכיוון שאין מה להשוות איתו, קח את האלמנט עצמו כפי שהוזמןרצף.
- עבור לפריט השני.
- השווה אותו עם הראשון בהתבסס על כלל המיון.
- במידת הצורך, החליפו רכיבים במקומות.
- קח את שני האלמנטים הראשונים כרצף מסודר.
- עבור לפריט השלישי.
- השווה אותו עם השני, החלף במידת הצורך.
- אם בוצעה ההחלפה, השווה אותה לזו הראשונה.
- קח שלושה אלמנטים כרצף מסודר.
וכך הלאה עד סוף המערך המקורי.
הכנסת חיים אמיתית
לצורך הבהירות, כדאי לתת דוגמה כיצד מנגנון המיון הזה משמש בחיי היומיום.
קח, למשל, ארנק. שטרות של מאה, חמש מאות ואלפי דולר מונחים בחוסר סדר בתא השטרות. זה בלאגן, בהודג'פודג' כזה קשה למצוא מיד את פיסת הנייר הנכונה. יש למיין את מערך השטרות.
הראשון הוא שטר של 1000 רובל, ומיד אחריו - 100. אנחנו לוקחים מאה ומניחים אותו מלפנים. השלישי בשורה הוא 500 רובל, המקום הנכון עבורו הוא בין מאה לאלף.
באותו אופן אנחנו ממיינים את הקלפים שהתקבלו כשמשחקים ב"שוטה" כדי להקל על הניווט ביניהם.
מפעילים ופונקציות עוזר
שיטת מיון ההוספה לוקחת כקלט מערך ראשוני למיון, פונקציית השוואה, ובמידת הצורך פונקציה שקובעת את הכלל לספירת אלמנטים. לרוב משתמשים במקוםמשפט לולאה רגיל.
הרכיב הראשון הוא עצמו סט מסודר, כך שההשוואה מתחילה מהשני.
האלגוריתם משתמש לעתים קרובות בפונקציית עוזר כדי להחליף שני ערכים (החלפה). הוא משתמש במשתנה זמני נוסף, שצורך זיכרון ומאט מעט את הקוד.
אלטרנטיבה היא להזיז מסה של קבוצת אלמנטים ואז להכניס את הנוכחי לחלל הפנוי. במקרה זה, המעבר לאלמנט הבא מתרחש כאשר ההשוואה נתנה תוצאה חיובית, המעידה על הסדר הנכון.
דוגמאות ליישום
היישום הספציפי תלוי במידה רבה בשפת התכנות שבה נעשה שימוש, בתחביר ובמבנים שלה.
יישום C קלאסי באמצעות משתנה זמני להחלפת ערכים:
int i, j, temp; for (i=1; i =0; j--) { if (מערך[j] < temp) break; array[j + 1]=מערך[j]; array[j]=temp; } }
PHP יישום:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
כאן, ראשית, כל הרכיבים שאינם תואמים לתנאי המיון מוזזים ימינה, ולאחר מכן הרכיב הנוכחי מוכנס לשטח הפנוי.
קוד Java באמצעות לולאת while:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
המשמעות הכללית של הקוד נשארת ללא שינוי: כל רכיב של המערך מושווה ברצף עם הקודמים ומוחלף איתם במידת הצורך.
זמן ריצה משוער
ברור שבמקרה הטוב ביותר, הקלט של האלגוריתם יהיה מערך שכבר מסודר בצורה הנכונה. במצב זה, האלגוריתם פשוט יצטרך לבדוק כל אלמנט כדי לוודא שהוא נמצא במקום הנכון מבלי לבצע החלפות. לפיכך, זמן הריצה יהיה תלוי ישירות באורך המערך המקורי O(n).
הקלט במקרה הגרוע הוא מערך הממוין בסדר הפוך. זה ידרוש מספר רב של תמורות, פונקציית זמן הריצה תהיה תלויה במספר האלמנטים בריבוע.
ניתן לחשב את המספר המדויק של תמורות עבור מערך לא מסודר לחלוטין באמצעות הנוסחה:
n(n-1)/2
כאשר n הוא אורך המערך המקורי. לפיכך, יידרשו 4950 תמורות כדי לסדר 100 אלמנטים בסדר הנכון.
שיטת ההכנסה יעילה מאוד למיון מערכים קטנים או ממוינים חלקית. עם זאת, לא מומלץ ליישם אותו בכל מקום בגלל המורכבות הגבוהה של החישובים.
האלגוריתם משמש כעזר בשיטות מיון רבות אחרות מורכבות יותר.
מיין ערכים שווים
אלגוריתם ההחדרה שייך למיונים הנקראים יציבים. זה אומר,שהוא לא מחליף אלמנטים זהים, אלא שומר על הסדר המקורי שלהם. מדד היציבות חשוב במקרים רבים להזמנה נכונה.
האמור לעיל הוא דוגמה ויזואלית נהדרת למיון הכנסה בריקוד.
