בחירה מהירה (אלגוריתם)
בחירה מהירה (באנגלית: Quickselect) הוא אלגוריתם בחירה למציאת האיבר ה-k הכי קטן במערך או ברשימה בלתי ממויינות. לשיטת האלגוריתם קשר ישיר למיון מהיר. בדומה למיון מהיר, הביצועים שלו טובים בדרך כלל ויש לו סיבוכיות זמן ריצה ממוצעת טובה, אך ביצועים לא מרשימים במובן של זמן ריצה במקרה הגרוע.
בחירה מהירה משתמשת באותו רעיון שעליו מבוסס מיון מהיר – בחירת איבר כציר (pivot), וחלוקה של שאר האיברים לשתי קבוצות – איברים שגדולים מהציר ואיברים שקטנים ממנו. עם זאת, מכיוון שמטרתו של אלגוריתם הבחירה הוא למצוא איבר בודד ולא לסדר את האיברים, בניגוד למיון מהיר שמופעל רקורסיבית על האיברים של שתי הקבוצות הוא יופעל בכל פעם רק על הקבוצה שבה נמצא האיבר שמחפשים. לפיכך יורד זמן הריצה הממוצע מ- במקרה של מיון מהיר ל-. זמן הריצה במקרה הגרוע ביותר נותר .
בדומה למיון מהיר, גם בחירה מהירה ממומש בדרך כלל כאלגוריתם תוך-מקומי.
האלגוריתם
במיון מהיר נעשה שימוש באלגוריתם עזר בשם חלוקה (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
