מיון מסרק

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

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

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

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

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

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

 פסאודו קוד 
<div style="direction: ltr;">

 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
<div style="direction: rtl;">

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

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

 הערות שוליים 

קטגוריה:אלגוריתמי מיון