תרגול 4 - Comparison-Based Sorting Algorithms

1. רקע

2. תרגיל 1: ניתוח רקורסיה

func(n)
    if (n = 1 or n = 2)
        return 2n
    if (n mod 2 = 0)
        num = func(n/2)
        return num²
    else
        return 2*func(n-1)

1) נוסחת רקורסיה

לפי המקרים:
  T(n) ≤ T(n/2) + c₃,        אם n זוגי ו-n > 2
  T(n) ≤ T(n-1) + c₄,        אם n אי-זוגי ו-n > 1
  T(1) = c₁,  T(2) = c₂

יהי c = 2·max{c₁, c₂, c₃, c₄}.

הטריק: כש-n אי-זוגי, אחרי קריאה אחת n-1 זוגי, ואז מתחלק ב-2.
שתי קריאות יורדות מ-n ל-⌊(n-1)/2⌋ ≈ n/2.
לכן באופן אחיד:
  T(n) ≤ T(⌊n/2⌋) + c,    T(1), T(2) ≤ c.

2) פתרון בהצבה

T(n) ≤ T(⌊n/2⌋) + c
     ≤ T(⌊n/4⌋) + 2c
     ≤ T(⌊n/8⌋) + 3c
     ...
     ≤ T(⌊n/2ᵏ⌋) + k·c

נעצרים כש-⌊n/2ᵏ⌋ ≤ 2 ⟺ n ≤ 2^(k+1) ⟺ log₂ n − 1 ≤ k.

אחרי ⌈log n⌉ צעדים מגיעים ל-T(2) או T(1):
  T(n) ≤ c + ⌊log₂ n⌋ · c = O(log n).

3) אישור באינדוקציה

נוכיח: T(n) ≤ c · log₂ n לכל n ≥ 2.

בסיס n=2: T(2) ≤ c = c · log₂ 2. ✓

הנחה: לכל k < n, T(k) ≤ c · log₂ k.

צעד (n זוגי): T(n) ≤ T(n/2) + c
              ≤ c·log(n/2) + c    [הנחת אינדוקציה]
              = c·(log n − log 2) + c
              = c·log n − c + c = c·log n. ✓

צעד (n אי-זוגי): T(n) ≤ T((n-1)/2) + c
                 ≤ c·log((n-1)/2) + c   [הנחה]
                 = c·log(n-1) − c + c
                 ≤ c·log(n-1) ≤ c·log n. ✓

⟹ T(n) = O(log n). ∎

3. HeapSort - Recap

HeapSort(A)
  BuildMaxHeap(A)
  n = length(A)
  For s = n downto 2
    x = A[1]
    PercDown(1, A[s], s-1, A)
    A[s] = x

סיבוכיות וכוחות

4. תרגיל 2: HeapSort בסדר יורד

גישה 1 — שימוש ב-Min-Heap

HeapSort(A)
  BuildMinHeap(A)            ← במקום BuildMaxHeap
  n = length(A)
  For h = n downto 2
    x = A[1]
    PercDown(1, A[h], h-1, A)
    A[h] = x

כל DeleteMin מוציא את הקטן ביותר ושם בסוף ⟹ מערך ממוין מהגדול לקטן.

גישה 2 — Max-Heap + היפוך מערך

HeapSort(A)
  BuildMaxHeap(A)
  n = length(A)
  For h = n downto 2
    x = A[1]
    PercDown(1, A[h], h-1, A)
    A[h] = x
  ReverseArray(A)            ← היפוך לקבלת סדר יורד

יתרונות וחסרונות

אסימפטוטית — שתיהן \(\Theta(n \log n)\). בפועל: גישה 1 עדיפה.

5. MergeSort - Recap

Mergesort(A, l, r)
  if l < r then
    q ← ⌊(l+r)/2⌋
    Mergesort(A, l, q)
    Mergesort(A, q+1, r)
    Merge(A, l, q, r)

Merge(A, p, q, r): מיזוג שני התת-מערכים הממוינים \(A[p..q]\) ו-\(A[q+1..r]\) ל-\(A[p..r]\) ב-\(\Theta(n)\) זמן ו-\(O(n)\) מקום עזר.

6. דף עזר