מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג/תרגילים/מיון Min-Max/שאלה

פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.

להלן אלגוריתם מיון בשם Min-Max-Sort:

Min-Max-Sort(A, p, q)
1		if p ≥ q
2			return 

3		m1 = Min(A, p, q)
4		m2 = Max(A, p, q)

5		if m1 == m2
6			return

7		(r, s) = Rearrange(A, p, q, m1, m2)

8		Min-Max-Sort(A, r, s)

להלן הסבר לפונקציה. הפונקציה מקבלת שלושה פרמטרים: A הוא המערך שאותו יש למיין; p וq הם שני אינדקסים המתארים את גבולות הגזרה שאותה יש למיין.שורות 3-4 מוצאות בהתאמה את הערכים הקטן והגדול בגזרה (הנח שכל אחת משתי הפונקציות Min וMax נתונות). הקריאה לRearrange (שגם היא נתונה) ב7 מסדרת את הגזרה, ומחזירה r וs כך שמתקיים:

1. לכל $\displaystyle p\leq i<r$,‏ {{{1}}}.
2. לכל $\displaystyle r\leq i\leq s$,‏ m_1 \lt A[i] \lt m_2.
3. לכל $\displaystyle s<i\leq q$,‏ {{{1}}}.

דוגמה: אם {{{1}}}, {{{1}}} ו{{{1}}}, אז: {{{1}}} ו{{{1}}}. #הקריאה לRearrange(A) יכולה לסדר את A כך ש{{{1}}}; בכל מקרה, הפונקציה תחזיר (3, 5).

1. אנא הסבר במילים אך באופן ברור מדוע כל אחת מMin(p, q), Max(p, q), וRearrange(p, q, m_1, m_2) חייבת להיות

$\displaystyle \Omega (p-q)$.

1. אנא נתח בצורה מדוייקת את זמן הריצה של Min-Max-Sort(A, 1, n) במונחי

n, אורך המערך A. אנא התייחס למקרה הטוב ביותר ולמקרה הגרוע ביותר.

1. כעת משנים מעט את האלגוריתם:

Third-Min-Max-Sort(A, p, q)
1		if p ≥ q
2			return 

3		m1 = Third-Min(A, p, q)
4		m2 = Max(A, p, q)

5		if m1 == m2
6			return

7		(r, s) = Rearrange(A, p, q, m1, m2)

8		Third-Min-Max-Sort(A, r, s)
9		Third-Min-Max-Sort(A, p, r - 1)

Third-Min(A, p, q) מחזירה ערך m_1 כך ששליש

מהאיברים A[p, ..., q] קטנים או שווים לו. הנח שאין שינוי בסיבוכיות שלוש פונקציות העזר. כיצד תשתנה (אם בכלל) תשובתך לסעיף הקודם?