שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2023 - מיון

נתון מערך $A$ באורך $n$ שבו כל האיברים שונים זה מזה. כתבו אלגוריתם להחזרת $k$ האיברים הקטנים ביותר של $A$ בסדר ממוין ($1 \leq k \leq n$). זמן הריצה הנדרש הינו $O(n + k \lg k)$.

רמז: השתמשו באלגוריתם SELECT למציאת האיבר ה-$k$ בגודלו בזמן $O(n)$, ואז מיינו רק את $k$ האיברים הקטנים.

פתרון: **אלגוריתם:** 1. **מצא את האיבר ה-$k$ בגודלו** באמצעות אלגוריתם SELECT (Median of Medians) בזמן $O(n)$. נסמנו $x$. 2. **בצע PARTITION** סביב $x$ בזמן $O(n)$. לאחר החלוקה, $k$ האיברים הקטנים ביותר נמצאים בצד השמאלי של המערך (מיקומים $1$ עד $k$). 3. **מיין את $k$ האיברים הקטנים** (מיקומים $1$ עד $k$) באמצעות אלגוריתם מיון אופטימלי (כגון מיון-מיזוג) בזמן $O(k \lg k)$. 4. **החזר** את $A[1..k]$. **ניתוח זמן ריצה:** - שלב 1: $O(n)$ - שלב 2: $O(n)$ - שלב 3: $O(k \lg k)$ - סה"כ: $O(n + k \lg k)$ ✓