מיון מסרק

מיון מסרק

המחשה של מיון מסרק
מחלקה	אלגוריתם מיון
סיבוכיות זמן	במקרה הטוב: $\Theta (n\log n)$, במקרה הממוצע: $\Omega (n^{2}/2^{p})$, כאשר $p$ הוא מספר ההגדלות במקרה הגרוע: $O(n^{2})$
סיבוכיות מקום	$\Theta (1)$

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

האלגוריתם

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

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

המרחק ההתחלתי הוא כאורך הרשימה הממוינת $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

לקריאה נוספת

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

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

מדיה וקבצים בנושא מיון מסרק בוויקישיתוף

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

33917934מיון מסרק