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