הצגת המקור של הדף "מיון מהיר"


<div style="text-align: left; direction: ltr;float: left; margin-left: 1em;">
{| class="wikitable"
|+מיון מהיר
!מחלקה
![[מיון (אלגוריתם)]]
|-
!סיבוכיות ממוצעת
!<math>O\left(n\log n\right)</math>
|-
!סיבוכיות במקרה הגרוע
!<math>O\left(n^2\right)</math>
|}
</div>
[[קובץ:Partition example.svg|שמאל|ממוזער|250px|[[איטרציה]] אחת של [[אלגוריתם]] מיון מהיר. 5 הוא "איבר הציר"; האיברים הצבועים באדום הם האיברים הגדולים מ-5; האיברים הצבועים בכחול הם האיברים שקטנים או שווים ל-5.]]
[[קובץ:Sorting quicksort anim.gif|שמאל|ממוזער|250px|הנפשה של מיון מהיר]]
'''מיון מהיר''' (ב[[אנגלית]]: '''Quicksort''') הוא [[אלגוריתם]] [[מיון (מדעי המחשב)|מיון]] השוואתי [[אלגוריתם אקראי|אקראי]] מהיר במיוחד בסדרות איברים גדולות. 

האלגוריתם פותח על ידי איש מדעי המחשב הבריטי טוני הואר ב-1959<ref>{{קישור כללי|כתובת=https://web.archive.org/web/20150403184558/http://www.computerhistory.org/fellowawards/hall/bios/Antony,Hoare/|כותרת=Sir Antony Hoare {{!}} Computer History Museum|אתר=web.archive.org|תאריך=2015-04-03|תאריך_וידוא=2024-04-11}}</ref> ופורסם ב-1961. האלגוריתם עדיין נמצא בשימוש נפוץ למשימות מיון.  

[[סיבוכיות זמן|סיבוכיות הזמן]] הממוצעת של האלגוריתם היא <math>O\left(n\log n\right)</math> פעולות (כמו, למשל, [[מיון מיזוג]]), אך במקרה הגרוע עלול האלגוריתם לדרוש <math>O\left(n^2\right)</math> פעולות (כמו, למשל, [[מיון בועות]]).

בפועל, אלגוריתם מיון מהיר נחשב ל[[אלגוריתם]] ה[[מיון (מדעי המחשב)|מיון]] ההשוואתי היעיל ביותר הידוע<ref>{{צ-ספר|שם=The Algorithm Design Manual|קישור=https://books.google.com/books?id=7XUSn0IKQEgC|מו"ל=Springer Science & Business Media|שנת הוצאה=2009-04-05|ISBN=978-1-84800-070-4|מחבר=Steven S. Skiena|שפה=en|עמ=129|פרק=4.6.3}}</ref>, זאת מאחר שהסיכוי למקרה הגרוע הוא מאוד נמוך.

==פרטי האלגוריתם==
אלגוריתם מיון מהיר הוא אלגוריתם [[רקורסיה|רקורסיבי]] הפועל בשיטת [[אלגוריתם הפרד ומשול|הפרד ומשול]].<ref>{{צ-מאמר|מחבר=C. A. R. Hoare|שם=Algorithm 64: Quicksort|כתב עת=Communications of the ACM|כרך=4|שנת הוצאה=1961-07-01|עמ=321|doi=10.1145/366622.366644|קישור=https://dl.acm.org/doi/10.1145/366622.366644}}</ref> צעדיו הם כדלקמן:
#בהינתן [[סדרה (מתמטיקה)|סדרת]] איברים, בחר איבר מהסדרה באקראי (נקרא: pivot, או "איבר ציר").
#סדר את כל האיברים כך שהאיברים הגדולים מאיבר הציר יופיעו אחרי האיברים הקטנים מאיבר הציר.
#באופן רקורסיבי, הפעל את האלגוריתם על סדרת האיברים הגדולים יותר ועל סדרת האיברים הקטנים יותר.
#תנאי העצירה של האלגוריתם הוא כאשר ישנו איבר אחד, ואז האלגוריתם מודיע כי הסדרה ממוינת.
{{-}}
מימוש האלגוריתם בפשטותו ב[[פסאודו קוד]] נראה כדלקמן:
<div style="text-align: left; direction: ltr; margin-left: 1em;">
 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))
</div>

מימוש האלגוריתם בגרסתו החכמה יותר (מיון [[אלגוריתם תוך-מקומי|In Place]], שבו העבודה מתבצעת על המערך המקורי) ב[[פסאודו קוד]] נראה כדלקמן:
<div style="text-align: left; direction: ltr; margin-left: 1em;">
 function quicksort(array, left, right)
     var pivotIdx, leftIdx = left, rightIdx = right
     if right - left > 0
         pivotIdx = (left + right) / 2
         while leftIdx <= pivotIdx and rightIdx >= pivotIdx
             while array[leftIdx] < array[pivotIdx] and leftIdx <= pivotIdx
                 leftIdx = leftIdx + 1
             while array[rightIdx] > array[pivotIdx] and rightIdx >= pivotIdx
                 rightIdx = rightIdx - 1;
             swap array[leftIdx] with array[rightIdx]
             leftIdx = leftIdx + 1
             rightIdx = rightIdx - 1
             if leftIdx - 1 == pivotIdx
                 pivotIdx = rightIdx = rightIdx + 1
             else if rightIdx + 1 == pivotIdx
                 pivotIdx = leftIdx = leftIdx - 1
         quicksort(array, left, pivotIdx - 1)
         quicksort(array, pivotIdx + 1, right)
</div>



מימוש האלגוריתם ב[[פייתון]]:

הפונקציה הראשית היא quicksort והיא קוראת לפונקציה שעושה את המיון באמת partition. 
הפונקציה exchange היא פונקציית עזר בשביל הנוחות של המימוש בלבד.
<div style="text-align: left; direction: ltr; margin-left: 1em;">
<syntaxhighlight lang="python3">
def quicksort(arr, left, right):
    if left < right: # stopping point
        index = partition(arr, left, right)
        quicksort(arr, left, index-1)
        quicksort(arr, index+1, right)
        
def partition(arr, left, right):
    x = arr[right]
    i = left - 1
    j = left
    while j <= right-1:
        if arr[j] <= x:
            i += 1
            exchange(arr, i, j)
        j += 1
    exchange(arr, i+1, right)
    return i+1

def exchange(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
</syntaxhighlight></div>


==שיפורים ווריאציות של האלגוריתם==
יעילות האלגוריתם תלויה בבחירת איבר הציר. אם - כתוצאה מ"מזל טוב" - איבר הציר הוא תמיד האיבר האמצעי בגודלו בסדרה, האלגוריתם לוקח <math>\Theta\left(n\log n\right)</math> . אם, מאידך - כתוצאה מ"מזל רע" - איבר הציר הוא האיבר הקטן ביותר או האיבר הגדול ביותר, אזי האלגוריתם לוקח  <math>O\left(n^2\right)</math>. לכן, ישנה חשיבות רבה למציאת איבר הציר:
* לעיתים משתמשים אלגוריתמים בפועל בשיטת "חציון משלושה" על מנת לבחור איבר שעשוי להיות "מתאים יותר" מאשר איבר שרירותי.
* באופן תאורטי, ניתן למצוא את החציון בסדרה ב[[זמן ריצה ליניארי|זמן ליניארי]], מה שמבטיח זמן ריצה של <math>\Theta\left(n\log n\right)</math>, אך על אף העובדה שהאלגוריתם למציאת החציון רץ בזמן ליניארי, הגורמים הקבועים הכרוכים בו גבוהים למדי, מה שמוביל לזמן ריצה גבוה, ולחוסר שימוש בשיטה זו בפועל.
*לעיתים משתמשים במימוש של בחירת איבר הציר באופן [[אקראיות|אקראי]] כדי לאפשר סיכוי שווה לכל אחד מהאיברים בתחום להיבחר וכך לאפשר חלוקה מאוזנת יותר. במקרה בו המערך כבר ממוין, בחירת האיבר באופן אקראי דווקא תפגע ביעילות ותגדיל את זמן הריצה שלו. המימוש ב[[פייתון]] של האלגוריתם האקראי הוא:
<div style="text-align: left; direction: ltr; margin-left: 1em;">
<syntaxhighlight lang="python3">
import random
def rand_partition(arr, left, right):
    i = random.randint(left, right)
    exchange(arr, i, right)
    return partition(arr, right, left)


def randomized_quicksort(arr, left, right):
    if left < right: # stopping point
        index = rand_partition(arr, left, right) # changed to rand_partition instead of partition
        quicksort(arr, left, index-1)
        quicksort(arr, index+1, right)

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

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

== ראו גם ==

* [[טוני הואר]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* [http://www.youtube.com/watch?v=o2dm4X-t8L0 סרטון אנימציה] שמסביר את האלגוריתמים מיון מהיר ומיון בועות ומשווה ביניהם
* [https://web.archive.org/web/20150302145415/http://www.sorting-algorithms.com/quick-sort אנימציה של אלגוריתם המיון המהיר Quicksort בסוגי קלט שונים]
* {{MathWorld}}

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}

{{אלגוריתמי מיון}}

[[קטגוריה:אלגוריתמי מיון|מהיר]]
[[קטגוריה:רקורסיה]]