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

בחירה מהירה (באנגלית: 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