|
[[קובץ:Sorting shellsort anim.gif|שמאל|ממוזער|250px|המחשה של מיון באמצעות מיוןShell שלsort]]
'''מיון של''' (ב[[אנגלית]]: '''Shell Sort''') הוא [[אלגוריתם]] [[מיון (מדעי המחשב)|מיון]] הבאהאלגוריתם בא לשפר את אלגוריתם [[מיון הכנסה]] (Insertion Sort), שיעילותו רבה רק כאשר הקלט שעליו למיין כבר ממוין ברובו ואילו במקרה הממוצע יעילותו פחותה.
האלגוריתם הוצג לראשונה ב-[[1959]] על ידי [[מדעי המחשב|מדען המחשב]] ה[[ארצות הברית|אמריקאי]] ''דונלד של'' שהציג את האלגוריתם כחלק מעבודת [[דוקטור]]ט, ב[[אוניברסיטה|אוניברסיטת]] [[סינסינטי]], [[אוהיו]].
== אופן פעולה ==
האלגוריתם בא לשפר את אלגוריתם מיון ההכנסה, ומבוסס עליו. בקצרה, פעולתו של מיון ההכנסה מבוססת על מעבר על המערך, כאשר אם נמצא ערך שאינו במקומו, הוא מוזז למיקומו הנכון. כאמור, אלגוריתם זה יעיל בעיקר רק עבור מערכים שכבר ממוינים ברובם. אלגוריתם מיוןה-Shell שלSort פועל בשלבים, בהם הוא ממיין תאי מערך הרחוקים זה מזה מרחק שהולך וקטן בכל שלב, כשהמיון עצמו מתבצע בצורת מיון הכנסה. לדוגמה (דוגמה אפשרית התלויה במימוש) - במערך שגודלו 12 (בהנחה שמספרי התאים מתחילים ב-1 ונגמרים ב-12) יתחיל המיון בתאים שרחוקים 6 מקומות זה מזה. האלגוריתם ימיין רק את התאים 1 ו-7, לאחר מכן את 2 ו-8, 3 ו-9, וכן הלאה עד 5 ו-11, כאשר הוא פועל בכל פעם על שני תאים בלבד. בשלב השני יעבור האלגוריתם למיון התאים שמרחקם זה מזה הוא שלוש, ולכן ימיין את התאים 1, 4, 7, ו-10, לאחר מכן את 2, 5, 8, ו-11, ולבסוף את 3, 6, ו-9. בשלב הבא והאחרון יבצע האלגוריתם מיון הכנסה רגיל על המערך. לסיכום - מספר רב של מעברים על הקלט נלקחים במרווחים יותר ויותר קטנים, עד שלבסוף מתבצע מיון הכנסה רגיל על כל המערך, כשבשלב זה המערך כמעט ממוין לגמרי.
== יעילות ==
נאמר שהערך הקטן ביותר במערך שגודלו <math>N</math> נמצא במקום האחרון, ואילו אנחנו מעוניינים לסדר את המערך מהקטן אל הגדול, כך שערך זה יעבור אל התא הראשון במערך. בשימוש ב[[מיון בועות]] (Bubble Sort) או [[מיון הכנסה]] (Insertion Sort) זה ייקח בערך <math>N</math> השוואות והחלפות כדי להביא את אותו ערך למיקומו המתאים.
במיוןב-Shell שלSort אנו מזיזים את הערך בצעדים גדולים (בשלבי המיון הראשוניים) כך שערך קטן ינוע דרך ארוכה לקראת המיקום הסופי שלו באמצעות השוואות בודדות. אם כך, למרות שבמיון זה מתבצעים מעברים רבים על המערך, בכל פעם המערך ממוין יותר ולכן גם יעילות מיון ההכנסה שמתבצע בכל שלב רבה יותר. כתוצאה מכך, יעילותו של מיון זה רבה יותר מזו של אלגוריתם מיון ההכנסה.
דרך אחת לתאר זאת היא זו: ארגן את הרשימה למיון לטבלה ומיין כל עמודה בנפרד, תוך שימוש במיון הכנסה. חזור על התהליך כשכל פעם עשה זאת עם מספר קטן יותר של תורים ארוכים יותר. לבסוף תקבל טבלה עם עמודה אחת. על ידי הפיכת הרשימה לטבלה יותר פשוט לראות זאת: האלגוריתם עצמו מבצע את המיון במקום (על ידי הגדלת האינדקס בגודל הצעדים).
=== דוגמה ===
== סיבוכיות ==
{{להשלים}}
הסיבוכיות של אלגוריתם זה, במקרה הגרוע ביותר תהיה O(n²){{D}}.
[[קטגוריה:אלגוריתמי מיון|של]]הסיבוכיות של אלגוריתם זה, במקרה הגרוע ביותר יהיה (n²)O
|
