הרצאה 11 - מיון רקורסיבי

בהמשך להרצאה על רקורסיה, מסתבר כי ישנם אלגורימי מיון שמימוש רקורסיבי שלהם (במקום איטרטיבי) הוא מוצלח ואלגנטי. בהרצאה זו נפגוש מספר אלגוריתמים כאלו וננתח אותם לעומק.

מיון מיזוג רקורסיבי

מתברר כי את אלגוריתם המיון היעיל שלמדנו, Merge Sort, ניתן לממש בצורה רקורסיבית באופן מוצלח. האלגוריתם מעצם הוויתו מתאים למימוש רקורסיבי - הרי אנחנו שוברים את המערך הממוין לחלקים קטנים יותר, ומשתמשים בתת-מערכים ממוינים על מנת למזג בצורה יעילה.

תנאי העצירה באלגוריתם יהיה גודל תת-המערך הממוזג - ניתן לעצור עבור מערכים בגודל 1. צעד הרקורסיה יהיה הקטנת גודל המערך ואז מיזוג שלו, יחד עם העתקה ממערך העזר למערך המקורי:

#include <stdlib.h>
void merge(int* arr1, int len1, int* arr2, int len2, int* dst);
void merge_sort_aux(int* arr, int n, int* tmp_arr);
void merge_sort(int* arr, int n) {
    int* tmp_arr = malloc(n * sizeof(int));
    merge_sort_aux(arr, n, tmp_arr);
    free(tmp_arr);
}
void merge_sort_aux(int* arr, int n, int* tmp_arr) {
    if(n <= 1) {
        return;
    }
    int low = n / 2;
    int high = n - low;
    merge_sort_aux(arr, low, tmp_arr);
    merge_sort_aux(arr + low, right, tmp_arr);
    merge(arr, low, arr + low, high, tmp_arr);
    for(int i = 0; i < n; i++) {
        arr[i] = tmp_arr[i];
    }
}

מבחינת סיבוכיות זמן, מתבצעות $\Theta(\log n)$ קריאות לפונקציה הרקורסיבית שאורכה $\Theta(n)$, ולכן בדומה למימוש האיטרטיבי נקבל $\Theta(n \log n)$. מבחינת סיבוכיות המקום, אנו מקצים $\Theta(n)$ זכרון עבור מערך העזר, ומכיוון שמתבצעות $\log n$ קריאות רקורסיביות אנחנו מקצים גם $\Theta(\log n)$ מקום עבור מחסנית הקריאות. סה״כ מתקיים שסיבוכיות המקום היא:

כלומר, הסיבוכיות זהה לחלוטין לסיבוכיות במימוש האיטרטיבי.

Quick Sort