מיון מסרק

{{#invoke:ParamValidator|validateparams|module_options=יחידה:PV-options}} {{#invoke:תבנית מידע|מידע| | טבלה-עיצוב = width: 22em; font-size: 95%; | כותרת תבנית-עיצוב =background: #B2C6FF; border:1px solid #aaaaaa; border-bottom:0px; | כותרת-עיצוב = background: #B2C6FF; | תמונה = | כיתוב=המחשה של מיון מסרק | תווית-מידע10=מחלקה | תווית-מידע20=סוג | תווית-מידע30=מבנה נתונים | תווית-מידע40=סיבוכיות זמן |סיבוכיות זמן-ויקינתונים=P3752 | תווית-מידע50=סיבוכיות מקום |סיבוכיות מקום-ויקינתונים=P3755 | תווית-מידע60=ממציא |ממציא-ויקינתונים-מרובה=P61 |ממציא-ויקינתונים-פרטים=P577 | תווית-מידע70=נקרא על שם |נקרא על שם-ויקינתונים-מרובה=P138 | תווית-מידע80=הומצא |הומצא-ויקינתונים=P575

}}

מיון מסרק הוא אלגוריתם מיון פשוט יחסית שתוכנן במקור על ידי Włodzimierz Dobosiewicz ב-1980.תבנית:הערה לאחר מכן הוא התגלה מחדש על ידי סטיבן לייסי וריצ'רד בוקס בשנת 1991.תבנית:הערה מיון מסרק הוא שיפור של מיון בועות.

האלגוריתם

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

במיון מסרק, כל שני איברים שמושווים, תמיד נמצאים במרחק של 1 זה מזה. הרעיון העומד בבסיס מיון בועות הוא שהמרחק יכול להיות הרבה יותר מ-1. את הלולאה הפנימית של מיון בועות, אשר מבצעת בפועל את ההחלפה, מחליפה במיון מסרק, לולאה בה המרחק בין זוג איברים מוחלפים הולך וקטן (בכל איטרציה של הלולאה החיצונית) בצעדים של "גורם הכיווץ" $k$, כלומר: $[\frac{n}{k},\frac{n}{k^2},\frac{n}{k^3},...,1]$.

המרחק ההתחלתי הוא כאורך הרשימה הממוינת $n$ חלקי גורם הכיווץ $k$ (בדרך כלל $1.3$; ראה להלן) ועם מרחק זה מופעלת איטרציה אחת של מיון הבועות המעודכן כמובא לעיל. לאחר מכן, בכל שלב המרחק מחולק בגורם הכיווץ, הרשימה ממוינת עם המרחק החדש, והתהליך חוזר על עצמו עד שהמרחק הוא 1. בשלב זה, המיון ממשיך עם מרחק 1 עד שהרשימה ממוינת בשלמותה. השלב האחרון של המיון לפיכך הוא מקבילה של מיון בועות, אולם בשלב זה רוב הצבים כבר טופלו, ולכן מיון בועות יהיה יעיל.

לגורם הכיווץ יש השפעה גדולה על יעילות האלגוריתם. $k=1.3$ הוצע כגורם הכיווץ האידיאלי על ידי מחברי המאמר המקורי, לאחר בדיקה אמפירית של למעלה מ-200,000 רשימות אקראיות. ערך קטן מדי מאט את האלגוריתם וגורם לו לבצע השוואות רבות שלא לצורך, בעוד שערך גדול מדי לא מצליח להתמודד ביעילות עם צבים.

הרעיון של מיון במספר שלבים עם מרחק הולך וקטן דומה למיון של, אבל במיון-של המערך כולו ממוין בכל שלב לפני שעוברים למרחק הבא. השלבים במיון מסרק לא ממיינים את כל האיברים. זוהי הסיבה לכך שלסדרת המרחקים במיון-של יש גורם כיווץ אופטימלי גדול יותר, העומד על $k=2.2$ בקירוב.

פסאודו קוד

function combsort(array input)

gap := input.size // Initialize gap size
shrink := 1.3 // Set the gap shrink factor
sorted := false

loop while sorted = false
// Update the gap value for a next comb
gap := floor(gap / shrink)
if gap > 1
sorted := false // We are never sorted as long as gap > 1
else
gap := 1
sorted := true // If there are no swaps this pass, we are done
end if

// A single "comb" over the input list
i := 0
loop while i + gap < input.size // See Shell sort for a similar idea
if input[i] > input[i+gap]
swap (input[i], input[i+gap])
sorted := false
// If this assignment never happens within the loop,
// then there have been no swaps and the list is sorted.
end if

i := i + 1
end loop


end loop
end function

לקריאה נוספת

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

קישורים חיצוניים

הערות שוליים