מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג/תרגילים/מיון 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. לכל ,‏ {{{1}}}.
  2. לכל ,‏ m_1 \lt A[i] \lt m_2.
  3. לכל ,‏ {{{1}}}.



דוגמה:

אם {{{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) חייבת להיות

.

  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] קטנים או שווים לו. הנח שאין שינוי בסיבוכיות שלוש פונקציות העזר. כיצד תשתנה (אם בכלל) תשובתך לסעיף הקודם?