מיון של – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
תקלדה |
Johnny Zoo (שיחה | תרומות) עריכה, הורדת הערה |
||
שורה 1:
'''
▲'''shellSort ''' הוא [[אלגוריתם]] [[מיון (מדעי המחשב)|מיון]] אשר עם המימוש המקורי שלו דורש זמן ריצה של O(n2) השוואות והחלפות במקרה הגרוע (בשינויים קטנים תלוי בקלט) . האלגוריתם בא לשפר את אלגוריתם insertion sort, משתי סיבות: 1. insertion sort יעיל כאשר הקלט כמעט ממוין
==אופן פעולה==
האלגוריתם בא לשפר את אלגוריתם Insertion Sort, ומבוסס עליו. בקצרה, פעולתו של ה Insertion Sort מבוססת על מעבר על המערך, כאשר אם נמצא ערך שאינו במקומו, הוא מוזז למיקומו הנכון. כאמור, אלגוריתם זה יעיל בעיקר רק עבור מערכים שכבר ממוינים ברובם. אלגוריתם ה-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. בשלב הבא והאחרון יבצע האלגוריתם מיון הכנסה רגיל על המערך. לסיכום - מספר רב של מעברים על הקלט נלקחים במרווחים יותר ויותר קטנים, עד שלבסוף מתבצע מיון הכנסה רגיל על כל המערך, כשבשלב זה המערך כמעט ממוין לגמרי.
==יעילות==
נאמר שהערך
ב Shell Sort אנו מזיזים את הערך בצעדים גדולים (בשלבי המיון הראשוניים) כך שערך קטן ינוע דרך ארוכה לקראת המיקום הסופי שלו באמצעות השוואות בודדות. אם כך, למרות שבמיון זה מתבצעים מעברים רבים על המערך, בכל פעם המערך ממוין יותר ולכן גם יעילות מיון ההכנסה שמתבצע בכל שלב רבה יותר. כתוצאה מכך, יעילותו של מיון זה רבה יותר מזו של אלגוריתם ה-Insertion Sort.
דרך אחת לתאר זאת היא זו: ארגן את הרשימה למיון לטבלה ומיין כל עמודה בנפרד, תוך שימוש ב insertion sort . חזור על התהליך כשכל פעם עשה זאת עם מספר קטן יותר של תורים ארוכים יותר. לבסוף תקבל טבלה עם עמודה אחת. ע"י הפיכת הרשימה לטבלה, יותר פשוט לראות זאת, האלגוריתם עצמו מבצע את המיון במקום (ע"י הגדלת האינדקס בגודל הצעדים כלומר שימוש ב i+=step size במקום i++)▼
לדוגמא: נתונה הרשימה הבאה למיון:▼
[ 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 ]
▲נתחיל עם מיון ב- 5 צעדים. נהפוך את הרשימה לטבלה בעלת 5 עמודות:
<pre>
שורה 27 ⟵ 31:
45
</pre>
כעת כשנחזיר את הטבלה לצורת רשימה נקבל
[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].
ניתן לראות שהערך 10 זז מהסוף להתחלה. כעת נוכל למיין את הרשימה
[[קטגוריה:אלגוריתמי מיון]]
| |||