מיון מהיר

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

הנפשה של מיון מהיר

מיון מהיר (באנגלית: Quicksort) הוא אלגוריתם מיון השוואתי אקראי מהיר במיוחד.

סיבוכיות הזמן הממוצעת של האלגוריתם היא $\Theta \left(logn\right)$ פעולות (כמו, למשל, מיון מיזוג), אך במקרה הגרוע עלול האלגוריתם לדרוש $O\left(n\right)$ פעולות (כמו, למשל, מיון בועות).

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

פרטי האלגוריתם

אלגוריתם מיון מהיר הוא אלגוריתם רקורסיבי הפועל בשיטת הפרד ומשול. צעדיו הם כדלקמן:

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

מימוש האלגוריתם בפשטותו בפסאודו קוד נראה כדלקמן:

function quicksort(array)
    var list less, greater
    if length(array) ≤ 1
        return array
    select and remove a pivot value pivot from array
    for each x in array
        if x ≤ pivot then append x to less
        else append x to greater
    return concatenate(quicksort(less), pivot, quicksort(greater))

מימוש האלגוריתם בגירסתו החכמה יותר (סידור על המערך) בפסאודו קוד נראה כדלקמן:

function quicksort(array, left, right)
    var pivot, leftIdx = left, rightIdx = right
    if right - left > 0
        pivot = (left + right) / 2
        while leftIdx <= pivot and rightIdx >= pivot
            while array[leftIdx] < array[pivot] and leftIdx <= pivot
                leftIdx = leftIdx + 1
            while array[rightIdx] > array[pivot] and rightIdx >= pivot
                rightIdx = rightIdx - 1;
            swap array[leftIdx] with array[rightIdx]
            leftIdx = leftIdx + 1
            rightIdx = rightIdx - 1
            if leftIdx - 1 == pivot
                pivot = rightIdx = rightIdx + 1
            else if rightIdx + 1 == pivot
                pivot = leftIdx = leftIdx - 1
        quicksort(array, left, pivot - 1)
        quicksort(array, pivot + 1, right)

שיפורים ווריאציות של האלגוריתם

יעילות האלגוריתם תלויה בבחירת איבר הציר. אם - כתוצאה מ"מזל טוב" - איבר הציר הוא תמיד האיבר האמצעי בגודלו בסדרה, האלגוריתם לוקח $\Theta \left(n\log n\right)$ . אם, מאידך - כתוצאה מ"מזל רע" - איבר הציר הוא האיבר הקטן ביותר או האיבר הגדול ביותר, אזי האלגוריתם לוקח $O\left(n^{2}\right)$. לכן, ישנה חשיבות רבה למציאת איבר הציר:

• לעתים משתמשים אלגוריתמים בפועל בשיטת "חציון משלושה" על מנת לבחור איבר שעשוי להיות "מתאים יותר" מאשר איבר שרירותי.
• באופן תאורטי, ניתן למצוא את האיבר האמצעי בסדרה בזמן לינארי, מה שמבטיח זמן ריצה של $\Theta \left(n\log n\right)$, (USING SELECT)אולם אין שימוש רב בשיטה זו בפועל בשל זמן הריצה הגדול בפועל של תהליך זה^{[דרושה הבהרה]}.

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

קיימת גרסה איטרטיבית (לא רקורסיבית) של המיון המהיר, אולם היא מורכבת לכתיבה ולא אינטואיטיבית.

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

• סרטון אנימציה שמסביר את האלגוריתמים מיון מהיר ומיון בועות ומשווה ביניהם