מיון של

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

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

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

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

במקרה הגרוע זמן הריצה של האלגוריתם הוא O(n²). כלומר, במקרים קשים זמן הריצה גדל בערך בריבוע גודל הקלט.

מיון של (Shell Sort) היא שיטה למיין רשימות. אלגוריתם זה היא תוכנית שעוזרת לסדר פריטים. מיון זה שיפר את מיון ההכנסה. מיון ההכנסה הוא דרך שבה מכניסים כל פריט למקום הנכון.

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

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

במקרה הכי גרוע זה יכול לקחת זמן רב. זה דומה למצב שבו הזמן גדל במהירות כשהרשימה גדולה מאוד.