מה זה QuickSelect?
QuickSelect הוא אלגוריתם בחירה למציאת האלמנט הקטן ביותר ברשימה לא ממוינת.
האלגוריתם הסביר
לאחר מציאת הציר (מיקום המחלק את הרשימה לשני חלקים: כל אלמנט משמאל קטן מהציר וכל אלמנט מימין הוא יותר מהציר) האלגוריתם חוזר רק על החלק המכיל את ה- k-th האלמנט הקטן ביותר.
אם האינדקס של האלמנט המחולק (ציר) הוא יותר מ- k, אז האלגוריתם חוזר לחלק השמאלי. אם האינדקס (ציר) זהה ל- k, אז מצאנו את האלמנט הקטן ביותר k והוא מוחזר. אם האינדקס קטן מ- k, אז האלגוריתם יחזור לחלק הנכון.
בחירת פסודוקוד
Input : List, left is first position of list, right is last position of list and k is k-th smallest element. Output : A new list is partitioned. quickSelect(list, left, right, k) if left = right return list[left] // Select a pivotIndex between left and right pivotIndex := partition(list, left, right, pivotIndex) if k = pivotIndex return list[k] else if k < pivotIndex right := pivotIndex - 1 else left := pivotIndex + 1 חֲלוּקָה
המחיצה היא למצוא את הציר כאמור לעיל. (כל אלמנט משמאל הוא פחות מהציר וכל אלמנט בצד ימין הוא יותר מציר) יש שני אלגוריתמים למציאת ציר המחיצה.
- מחיצת לומוטו
- מחיצת הארה
מחיצת לומוטו
מחיצה זו בוחרת ציר שהוא בדרך כלל האלמנט האחרון במערך. האלגוריתם שומר על אינדקס i כאשר הוא סורק את המערך באמצעות אינדקס אחר j כך שהאלמנטים lo דרך i (כולל) קטנים או שווים לציר, והאלמנטים i + 1 עד j-1 (כולל) גדולים מה צִיר.
תכנית זו מתדרדרת O(n^2)כאשר המערך כבר בסדר.
algorithm Lomuto(A, lo, hi) is pivot := A[hi] i := lo for j := lo to hi - 1 do if A[j] < pivot then if i != j then swap A[i] with A[j] i := i + 1 swap A[i] with A[hi] return i מחיצת הארה
Hoare משתמש בשני מדדים שמתחילים בקצוות המערך המחולק, ואז נעים זה לזה עד שהם מגלים היפוך: זוג אלמנטים, אחד גדול או שווה לציר, אחד פחות או שווה לציר, ש נמצאים בסדר הלא נכון ביחס זה לזה.
לאחר מכן מוחלפים האלמנטים ההפוכים. כאשר המדדים נפגשים, האלגוריתם נעצר ומחזיר את המדד הסופי. ישנן גרסאות רבות של אלגוריתם זה.
algorithm Hoare(A, lo, hi) is pivot := A[lo] i := lo - 1 j := hi + 1 loop forever do i := i + 1 while A[i] pivot if i >= j then return j swap A[i] with A[j]