מיון הכנסה (Insertion sort) הוא אלגוריתם יעיל למיון מספר קטן של איברים.
 |
| מקור:https://en.wikipedia.org/wiki/File:Insertion-sort-example-300px.gif |
המיון עובד כפי שרובנו ממיינים קלפים באופן טבעי. נניח וקיבלנו 6 קלפים רנדומליים ואנחנו רוצים למיין אותם בסדר גודל עולה. משמאל לימין נסתכל על הקלף שני ונשווה אותו לקלף הראשון, אם הוא קטן ממנו אז נשים אותו משמאלו, אם לא אז נמשיך לקלף הבא. את הקלף השלישי נשווה לקלפים משמאלו עד שנמצא קלף קטן ממנו ושים אותו מימינו. וכך הלאה עד שנגיע לקלף השישי.
קלט: סדרה בעלת $n$ מספרים $\left(a_{1},a_{2},\ldots,a_{n}\right)$.
פלט: סדרה בעלת $n$ מספרים $\left(a_{1}',a_{2}',\ldots,a_{n}'\right)$ כך שמתקיים $a_{1}'\le a_{2}'\le\cdots\le a_{n}'$.
 |
| מקור: https://en.wikipedia.org/wiki/File:Insertion_sort.gif |
הוכחת נכונות
בתחילת כל איטרציה של לולאת ה-for, שהאינדקס שלו הוא $i$, תת-מערך $\text{num_array}\left[0:i-1\right]$ מכיל קלפים שמויינו, ושאר האיברים בתת-מערך $\text{num_array}\left[i+1:n\right]$ הם הקלפים שבאים אחרי קלף $i$ שעוד לא מויינו. ובפרט האיברים במערך $\text{num_array}\left[0:i-1\right]$ הם אותם איברים שהיו באינדקסים 0 עד $i-1$ לפני שהתחלנו למיין, נגדיר את התכונה הזאת של תת המערך $\text{num_array}\left[0:i-1\right]$ כשמורת לולאה.
שמורת לולאה:
בתחילת כל איטרציה של לולאה ה-for, תת-מערך $\text{num_array[0:i-1]}$ מורכב מאיברים שבמקור היו בתת המערך אך בסדר ממויין.
נשתמש בשמורת הלולאה כדי להוכיח את נכונות האלגוריתם. נצטרך להראות שלושה דברים:
- שמורת הלולאה נכונה לפני האיטרציה הראשונה של הלולאה:
- כאשר $i=1$, תת המערך $\text{num_array}[0:i-1]$ מורכב רק מאיבר אחד, $\text{num_array}[0]$. הוא ממויין ומכיל רק איברים מ-$\text{num_array}[0]$, ולכן שמורת הלולאה מתקיימת.
- אם שמורת הלולאה נכונה לפני איטרציה של הלולאה, אז היא נכונה גם לפני האיטרציה הבאה.
- עבור $i$ כלשהו, הלולאה מזיזה את כל האיברים באינדקס הקטן מ-$i$ צעד אחד ימינה ($+1$) עד שנמצא מקום מתאים ל-$\text{num_array}[i]$. לכן תת המערך $\text{num_array}[0:i]$ מכיל רק את האיברים המקוריים שהיו ב-$\text{num_array}[0:i]$, רק בצורה ממויינת. ולכן איטרציה של הלולאה משמרת את שמורת הלולאה.
- כאשר הלולאה מסתיימת, שמורת הלולאה נותנת לנו תכונה שימושית שעוזרת להוכיח את נכונות האלגוריתם.
- התנאי שעוצר את הלולאה הוא $i > \text{len(num_array)}$, משום שהלולאה מגדילה את $i$ ב-$1$ כל איטרציה בהכרח נגיעה ל-$i=\text{len(num_array)}+1$. לפי שמורת הלולאה תת המערך $\text{num_array}[0:i-1]$ מורכב מאיברים שבמקור היו בתת המערך אך בסדר ממויין, ולכן $\text{num_array}[0:\text{len(num_array)}]$ מערך ממויין.
זמן ריצה
במקרה הטוב ביותר
|
בממוצע
|
במקרה הגרוע
|
$O(n)$
|
$O\left(n^{2}\right)$
|
$O\left(n^{2}\right)$
|
אין תגובות:
הוסף רשומת תגובה