בחירה מהירה (אלגוריתם)

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

בחירה מהירה משתמשת באותו רעיון שעליו מבוסס מיון מהיר – בחירת איבר כציר (pivot), וחלוקה של שאר האיברים לשתי קבוצות – איברים שגדולים מהציר ואיברים שקטנים ממנו. עם זאת, מכיוון שמטרתו של אלגוריתם הבחירה הוא למצוא איבר בודד ולא לסדר את האיברים, בניגוד למיון מהיר שמופעל רקורסיבית על האיברים של שתי הקבוצות הוא יופעל בכל פעם רק על הקבוצה שבה נמצא האיבר שמחפשים. לפיכך יורד זמן הריצה הממוצע מ-$O(nlogn)$ במקרה של מיון מהיר ל-$O(n)$. זמן הריצה במקרה הגרוע ביותר נותר $O(n^{2})$.

בדומה למיון מהיר, גם בחירה מהירה ממומש בדרך כלל כאלגוריתם תוך-מקומי.

האלגוריתם

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

להלן פסואודו קוד עבור אלגוריתם החלוקה. האיבר שלפיו מתבצעת החלוקה נקרא list[pivotIndex]:

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

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

  // Returns the n-th smallest element of list within left..right inclusive
  // (i.e. left <= n <= right).
  // The search space within the array is changing for each round - but the list
  // is still the same size. Thus, n does not need to be updated with each round.
  function select(list, left, right, n)
     if left = right        // If the list contains only one element,
         return list[left]  // return that element
     pivotIndex  := ...     // select a pivotIndex between left and right,
                            // e.g., left + floor(rand() % (right - left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     // The pivot is in its final sorted position
     if n = pivotIndex
         return list[n]
     else if n < pivotIndex
         return select(list, left, pivotIndex - 1, n)
     else
         return select(list, pivotIndex + 1, right, n)

ניתן גם להחליף את הרקורסיה בלולאה:

 function select(list, left, right, n)
     loop
         if left = right
             return list[left]
         pivotIndex := ...     // select pivotIndex between left and right
         pivotIndex := partition(list, left, right, pivotIndex)
         if n = pivotIndex
             return list[n]
         else if n < pivotIndex
             right := pivotIndex - 1
         else
             left := pivotIndex + 1

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

19436257בחירה מהירה (אלגוריתם)