מיון של

המחשה של מיון באמצעות מיון של

מיון של (באנגלית: Shell Sort) הוא אלגוריתם מיון הבא לשפר את אלגוריתם מיון הכנסה (Insertion Sort), שיעילותו רבה רק כאשר הקלט שעליו למיין כבר ממוין ברובו ואילו במקרה הממוצע יעילותו פחותה.

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

אופן פעולה

האלגוריתם נועד לשפר את אלגוריתם מיון ההכנסה, ומבוסס עליו. בקצרה, פעולתו של מיון ההכנסה מבוססת על מעבר על המערך, כאשר אם נמצא ערך שאינו במקומו, הוא מוזז למיקומו הנכון. כאמור, אלגוריתם זה יעיל בעיקר רק עבור מערכים שכבר ממוינים ברובם. אלגוריתם מיון של פועל בשלבים, בהם הוא ממיין תאי מערך הרחוקים זה מזה מרחק שהולך וקטן בכל שלב, כשהמיון עצמו מתבצע בצורת מיון הכנסה. לדוגמה (דוגמה אפשרית התלויה במימוש) - במערך שגודלו 12 (בהנחה שמספרי התאים מתחילים ב-1 ונגמרים ב-12) יתחיל המיון בתאים שרחוקים 6 מקומות זה מזה. האלגוריתם ימיין רק את התאים 1 ו-7, לאחר מכן את 2 ו-8, 3 ו-9, וכן הלאה עד 5 ו-11, כאשר הוא פועל בכל פעם על שני תאים בלבד. בשלב השני יעבור האלגוריתם למיון התאים שמרחקם זה מזה הוא שלוש, ולכן ימיין את התאים 1, 4, 7, ו-10, לאחר מכן את 2, 5, 8, ו-11, ולבסוף את 3, 6, ו-9. בשלב הבא והאחרון יבצע האלגוריתם מיון הכנסה רגיל על המערך. לסיכום - מספר רב של מעברים על הקלט נלקחים במרווחים יותר ויותר קטנים, עד שלבסוף מתבצע מיון הכנסה רגיל על כל המערך, כשבשלב זה המערך כמעט ממוין לגמרי.

יעילות

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

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

דוגמה

נתונה הרשימה הבאה למיון:

[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]

נתחיל עם מיון ב-5 צעדים. נהפוך את הרשימה לטבלה בעלת 5 עמודות:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

לאחר מיון כל עמודה בנפרד נקבל את הטבלה הבאה:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

כעת כשנחזיר את הטבלה לצורת רשימה נקבל [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. ניתן לראות שהערך 10 זז מהסוף להתחלה. כעת נוכל למיין את הרשימה ב-3 צעדים ואחר כך על ידי צעד ואז נקבל אותה ממוינת לחלוטין.

סיבוכיות

פרק זה לוקה בחסר. אנא תרמו למכלול והשלימו אותו.

הסיבוכיות של אלגוריתם זה, במקרה הגרוע ביותר תהיה O(n²)‎.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

34139747מיון של