מיון מהיר

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

מיון מהיר (quicksort בלעז) הוא אלגוריתם מיון השוואתי אקראי מהיר במיוחד.

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

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

[עריכה] פרטי האלגוריתם

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

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

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

partition(a, left, right, pivotIndex)
   pivotValue := a[pivotIndex]
   swap(a[pivotIndex], a[right]) // Move pivot to end
   storeIndex := left
   for i = left to right-1
       if a[i] <= pivotValue
           swap(a[storeIndex], a[i])
           storeIndex := storeIndex + 1
   swap(a[right], a[storeIndex]) // Move pivot to its final place
   return storeIndex

quicksort(a, left, right)
   if right > left
       select a pivot value a[pivotIndex]
       pivotNewIndex := partition(a, left, right, pivotIndex)
       quicksort(a, left, pivotNewIndex-1)
       quicksort(a, pivotNewIndex+1, right)

[עריכה] שיפורים ווריאציות של האלגוריתם

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

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

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

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