הרצאה 8 - מיון

עשינו המון עד כה! להכניס רשימה של כל הנושאים

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

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

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

בעיית המיון

הגדרה: נתון מערך של איברים arr מסוג כלשהו באורך n. נקרא למערך ממוין אם לכל שני איברים עוקבים במערך a[i] ו-a[i + 1] (כאשר i ו-i + 1 בין 0 ל-n - 1) מתקיים a[i] <= a[i + 1].

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

1, 3, 3, 7, 25, 25, 100

בעוד שמערך char ממוין יכול להיות:

'+', '0', '5', 'Q', 'q', 'q' '~'

בקורס נתעסק בעיקר במיון מערכי int לפשטות, אבל כפי שלמדנו, מערכי char הם גם רק מספרים שאנחנו ממפים באמצעות ASCII לתווים - המיון שלהם נעשה בדיוק באותה צורה.

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

3, 100, 1, 3, 25, 7, 25

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

מיון “אינטואיטיבי”

הנה דרך אינטואיטיבית שבה אני עבדתי. כתבתי על נייר את המערך ועוד עותק ריק שלו:

חיפשתי את האיבר המקסימלי ברשימה - זה 100, שמתי אותו במקום האחרון:

סימנתי גם את ה-100 באדום כדי שיהיה ברור שהוא כבר מוין. המשכתי לאיבר המקסימלי הבא שהוא לא 100 - יש לנו שני איברי 25 ולכן לא משנה איזה ניקח, למשל את הראשון:

וכך הלאה עד למערך הממוין. פשוט סה“כ, נכון? לנו כבני אדם לחלוטין. כעת, ננסה לפרק את האלגוריתם הפשוט שהגדרנו לפתרון הבעיה להוראות שהמחשב ידע לעקוב אחריהן:

ראשית אנחנו צריכים, בנוסף למערך הנתון, מערך נוסף לשבץ בתוכו את התוצאות. נשתמש ב-malloc או נקצה סטאטית מערך נוסף בשביל זה.
צריך כעת למצוא את האיבר המקסימלי במערך - נעבור על כל המערך ונחפש אותו. נצטרך לעבור ממש על כל האיברים מכיוון שתמיד יתכן שהאיבר המקסימלי יהיה בסוף (כפי שקרה באיטרציה השנייה שלנו).
נצטרך לסמן באיזשהי דרך את המספרים שכבר “הוצאנו” מהמערך המקורי למערך המתמיין. אנחנו לא יכולים פשוט “לצבוע” את המערך - אפשר למשל להקצות מערך נוסף של משתנים bool בשם sorted המאותחל ל-false - כאשר sorted[i] == true אם כבר הוצאנו את האיבר ה-i מהמערך המקורי. אם מובטח לנו למשל שהמערך חיובי בלבד, אפשר למשל לסמן איברים שהוצאנו ב-1- ובכך לייתר את הקצאת המערך הנוסף.
אם נניח ש-n הוא אורך המערך, לאחר n איטרציות המערך החדש יהיה ממוין. נצטרך להחזיר את המערך הממוין ולוודא שיודעים שצריך להשתמש בו ולא במערך הקודם.

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

Max Sort

הבעיה העיקרית במימוש האינטואיטיבי שניסינו הייתה שצריך להקצות מערכים נוספים להתסבך עם בדיקות איתם. אולי אפשר לקחת את הקונספט של בחירת האיבר המקסימלי כל פעם ולשדרג אותו מעט?

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

נעבור איבר-איבר ונזהה את האיבר המקסימלי - זהו 100 ולכן מקומו במערך הממוין הוא האיבר האחרון. נחליף בינו לבין האחרון:

כעת נרצה למצוא את האיבר המקסימלי השני, זה שקטן/שווה ל-100. נשים לב שמובטח לנו ש-100 נמצא במקום הנכון, ולכן אין צורך להסתכל על האיבר האחרון במערך, ויש להחליף הלפני אחרון במערך. נקבל ש-25 במקום ה-1 (מתחילים לספור מ-0) צריך להתחלף עם 7 במקום הלפני אחרון:

נשים לב שקיימים שני 25 במערך, ולכן אין מניעה שהיינו בוחרים גם את השני מביניהם להחלפה. נמשיך כך עד שהמערך יהיה ממוין!

כעת נרצה לממש בקוד מיון את האלגוריתם. נכתוב במילים את השלבים שינחו אותנו במימוש:

יש לקבל כפרמטרים למימוש מצביע למערך int* arr ואורכו int n.
יש למיין את ה-len איברים הראשונים של המערך בכל איטרציה, כאשר len מאותחל לאורך המערך n ויורד ב-1 בכל איטרציה.
נמצא את האיבר המקסימלי מתוך len האיברים הראשונים ונחליף אותו עם האיבר ה-len במערך.

עבור שלב 2 נכתוב פונקציה שמוצאת את האינדקס של האיבר המקסימלי מתוך ה-len איברים הראשונים, ועבור שלב 3 נשתמש בפונקציית ה-swap שלמדנו לממש:

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
int get_max_index(int* arr, int len) {
    int max_index = 0;
    for(int i = 1; i < len; i++) {
        if(arr[i] > arr[max_index]) {
            max_index = i;
        }
    }
    return max_index;
}
void max_sort(int* arr, int n) {
    for(int len = n; len > 0; len--) {
        int max_index = get_max_index(arr, len);
        swap(&arr[len - 1], &arr[max_index]);
    }
}

הערה: קיים אלגוריתם מקביל ל-Max Sort בשם Min Sort, שעובד בצורה דואלית ע“י מציאת האלמנט המינימלי בכל שלב.

Bubble Sort

מיון בועות הוא דוגמא נוספת לאלגוריתם פשוט למימוש למיון. הרעיון הוא כזה - נעבור על כל המערך, איבר אחר איבר, ונשווה בין כל שני איברים סמוכים. אם הם לא ממוינים - כלומר, a[i - 1] > a[i] - נחליף ביניהם. כך איברים גדולים “יבעבעו” כלפי מעלה. כאשר לא נשארו איברים לבעבע, נדע שסיימנו.

נדגים על המערך הקודם - זוהי הצורה ההתחלתית שלו:

באיטרציה הראשונה 3 ו-100 בסדר הנכון ולכן לא נחליף ביניהם, ואז:

וכך הלאה, כאשר 100 מבעבע עד הסוף באיטרציה הראשונה:

כלומר, בסוף האיטרציה הראשונה האיבר המקסימלי יהיה בסוף, בדומה ל-Max Sort - כעת יש לבעבע רק את ה-n - 1 איברים שנשארו.

נממש:

#include <stdbool.h>
void swap(int* a, int* b);
void bubble_sort(int* arr, int n) {
    bool sorted = true;
    int len = n;
    while(len > 0 && !sorted) {
        for(int i = 1; i < n; i++) {
            if(arr[i - 1] > arr[i]) {
                swap(&arr[i - 1], &arr[i]);
                sorted = false;
            }
        }
    }
}

תרגילים

נתונה חתימת הפונקציה וההגדרות:

#define ASCENDING 0
#define DESCENDING 1
void hybrid_max_sort(int* arr, int n, int direction);

כאשר הפרמטר direction קובע אם הפונקציה ממיינת עם Max Sort את האיברים בסדר עולה או בסדר יורד. ממשו את הפונקציה.

מיון Bidirectional Bubble Sort הוא וריאציה של Bubble Sort בו לאחר ביצוע איטרציה עולה לאורך המערך ובעבוע איברים גדולים כלפי מעלה, מתבצעת איטרציה יורדת לאורך המערך ובעבוע איברים קטנים כלפי מטה. ממשו את void bidir_bubble_sort(int* arr, int n).
נתון מערך int* arr באורך 2n כאשר n מספר שלם חיובי. כתבו פונקציה המקבלת מערך כזה ואורכו הממיינת בסדר עולה את המספרים באינדקסים הזוגיים ובסדר יורד את המספרים באינדקסים האי-זוגיים.
כתבו פונקציה המקבלת מערך ואורכו וממיינת את המספרים לפי ערכם המוחלט.
כתבו פונקציה המבצעת מיון לבחירתכם ומחזירה את התוצאה במערך חדש, תוך כדי שהיא לא משנה את המערך המקורי ולא מבצעת העתקות מיותרות בין המערך המקורי לחדש.
כתבו פונקציה המקבלת מטריצה, מספר שורותיה ומספר עמודותיה וממיינת כל עמודה בסדר עולה.

תכונות אלגוריתמי מיון

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

יציבות

הגדרה: מיון יציב הוא מיון בו הסדר בין אלמנטים שווים במערך הלא ממוין נשמר לאחר המיון.

נבחן למשל את המערך המיוחד הזה:

במקרה זה, כל איבר במערך מכיל שני “שדות” - מספר ואות. בתכנות C מעט מתקדם יותר ניתן לייצר משתנים עם מספר שדות הנקראים Structs (דומים ל-Classes משפות תכנות אחרות). נניח כעת שנרצה למיין את המערך לפי המספר של איבר. כאשר נבצע למשל Bubble Sort נקבל את השלבים הבאים:

אם נסמן ב-i(x) האינדקס של איבר x במערך, נשים לב שמתקיים i(2a) < i(2b) גם במערך המקורי וגם במערך הממוין. זו דוגמא לכך ש-Bubble Sort הוא באופן כללי מיון יציב.

שאלה: איזה שינוי קטן ניתן לבצע ב-Bubble Sort שלא ישבור את האלגוריתם (כלומר, האלגוריתם עדיין יבצע מיון) אבל יהפוך אותו ללא יציב?

In Place

הגדרה: אלגוריתם מיון נקרא In Place אם הוא מבצע את המיון על גבי המערך המקורי ללא הקצאת מערך נוסף.

Bubble Sort ו-Max Sort, שני האלגוריתמים שפגשנו עד כה, הם In Place - מיד נפגוש אלגוריתמים נוספים שמשתמשים בזכרון נוסף בשביל להאיץ את תהליך המיון.

סיבוכיות זמן ומקום (Time & Space Complexity)

השארנו את התכונות המעניינות ביותר של האלגוריתמים לסוף - כמה הם יעילים. באופן כללי יש שני משאבים שאלגוריתמים צורכים מאיתנו ונבדלים זה מזה בהם:

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

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

דוגמא: Bogosort הוא אלגוריתם מיון בו מגרילים רנדומלית לכל איבר במערך מקום חדש, ואז בודקים האם המערך ממוין. למעשה, “מערבבים” את המערך כמו חפיסת קלפים ומקווים שהוא יהיה ממוין. זהו כמובן אלגוריתם לדוגמא בלבד, ללא שימושים פרקטיים - עם זאת, ניתן אינטואיטיבית להבין כי סיבוכיות הזמן שלו תהיה משמעותית גדולה יותר מאשר של Max Sort או Bubble Sort.

מיון מיזוג (Merge Sort)

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

מיזוג מערכים ממוינים

נניח שנתונים שני מערכים קלט ממוינים arr1, arr2. נרצה לקבל מערך פלט שלישי ממוין arr3 שמכיל את כל האיברים בשני המערכים. אין חובה שהמערכים יהיו באותו האורך. לדוגמא:

כיצד נעשה זאת?

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

נסמן את האינדקסים בהתאמה ב-i1, i2, i3. נתאחל את כולם ל-0:

נשווה בין שני האיברים הראשונים. 9 < 4 ולכן נכתוב אותו ראשון ונקדם את האינדקסים i1 ו-i3:

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

נכניס את 10 מ-arr2, את 11 מ-arr1 ואז נוותר ללא איברים ב-arr1. נותר עוד איברים ב-arr2 - נכניס את 15 מ-arr2 ונקבל:

מימוש מיזוג מערכים בקוד

האלגוריתם שלנו עובד! נכתוב מימוש שלו - נניח שאנחנו מקבלים את שלושת המערכים כקלט ואת אורכם של השניים הראשונים:

void merge(int* arr1, int len1, int* arr2, int len2, int* arr3) {
    for(int i1 = 0, i2 = 0, i3 = 0; i1 < len1 && i2 < len2; i3++) {
        if(arr1[i1] < arr2[i2]) {
            arr3[i3] = arr1[i1++];
        } else {
            arr3[i3] = arr2[i2++];
        }
    }
    // Copy leftover elements from either array
    while(i1 < len1) {
        arr3[i3++] = arr1[i1++];
    }
    while(i2 < len2) {
        arr3[i3++] = arr1[i2++];
    }
}

מיון מיזוג

כעת נראה כיצד ניתן להשתמש במיזוג מערכים ממוינים לטובת מיון. זה נשמע קצת כמו הגדרה מעגלית - בשביל למזג אנחנו צריכים מראש למיין, אז כיצד נשתמש במיזוג בשביל מיון? נשים לב לעובדה חשובה - מערכים באורך 1 הם בהגדרה ממוינים. נוכל להשתמש בעובדה זו באופן הבא - נתחיל במיזוג של “מערכים” באורך 1 זה עם זה, עד שכל המערך יורכב מרצף של מערכים ממוינים באורך 2. נמזג את כל המערכים באורך 2 עד שכל המערך יורכב מרצף של מערכים ממוינים באורך 4. כך נמשיך במיזוג עד שנקבל מערך אחד ממוין.

לפשטות, נניח שאורך המערך הוא חזקה של 2, n = 2^k. המימוש של האלגוריתם מעט מורכב, ביחוד החלק של חישוב האינדקסים בצורה מדויקת. מכיוון ש-malloc יכולה להכשל, נגדיר שהמיון מחזיר false אם היא נכשלה, אחרת true, ולא נשכח לשחרר את הזכרון:

#include <stdlib.h>
#include <stdbool.h>
void merge(int* arr1, int len1, int* arr2, int len2, int* arr3);
int merge_sort(int* arr, int n) {
    int* tmp_arr = (int*)malloc(sizeof(int) * n);
    if(!tmp_arr) {
        return false;
    }
    for (int len = 1; len < n; len *= 2) {
        for (int i = 0; i < n; i += 2 * len) {
            merge(arr + i, len, arr + i + len, len, tmp_array);
            for (int j = 0; j < 2 * len; j++) {
                arr[i + j] = temp_array[j];
            }
        }
    }
    free(tmp_arr);
    return true;
}

נפרק את שלבי האלגוריתם בצורה מסודרת:

נתחיל בהקצאת עבור המערך לתוכו נבצע מיזוג.
הלולאה החיצונית מגדירה איטרציות על גדלי מערך הולכים וגדלים - 1, ואז 2, ואז 4, וכך הלאה.
הלולאה הפנימית מבצעת איטרציות על כל תתי המערכים שיש למזג. למשל, כשאורך המערכים אותם ממזגים הוא 2, i מקבל את הערכים 0, 4, 8 וכך הלאה.
המערכים הנשלחים ל-merge נכתבים באריתמטיקת מצביעים. למשל, כשאורך המערכים אותם ממזגים הוא 2, מתחילים בשליחה של arr ו-arr + 2, כאשר המיזוג מתבצע לתוך המערך הזמני.
בסיום המיזוג מעתיקים את האיברים הרלוונטים חזרה למערך המקורי.

נבחן דוגמא:

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

נמשיך במיזוג מערכים באורך 2 למערכים באורך 4:

נסיים במיזוג שני המערכים באורך 4 למערך אחד באורך 8:

וקיבלנו מערך ממוין!

הערות:

ההנחה כי אורך המערך הוא חזקה של 2 נעשת כאן לפשטות על מנת להמנע ממקרי קצה, אבל ניתן לספק אותה מעשית בצורה פשוטה - נרחיב כל מערך לחזקה הקרובה ביותר של 2 אליו, ו-“נרפד” את הקצוות המורחבים באיברים לא רלוונטיים למיון (למשל INT_MAX).
לפעמים נהוג ללמד את השלב של ההעתקה מהמערך הזמני חזרה למערך שלנו עם memcpy, פונקציה המעתיקה מכתובת אחת בזכרון לאחרת. חתימת הפונקציה היא void* memcpy(void* dst, void* src, size_t count) - שני מצביעים ליעד והמקור, ומספר הבתים שיש להעביר (דומה ל-malloc). כך ניתן להחליף את הלולאה הפנימית ביותר עם השורה הבאה:

memcpy(arr + i, tmp_arr, 2 * len * sizeof(int));

תרגילים ושאלות

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

void merge_descend(int* arr1, int len1, int* arr2, int len2, int* arr3);

קבעו האם Merge Sort הוא אלגוריתם מיון יציב או לא.
נתונה הפונקציה הבאה:

int* merge_array_list(int** array_list, int array_list_len, int* arrays_len);

כאשר arrays_list הוא מערך של מערכים ממוינים שמספר המערכים בו הוא arrays_list_len, והאורך של המערך array_list[i] הוא arrays_len[i]. כתבו פונקציה הממזגת את כל המערכים למערך אחד שיוקצה דינמית ויוחזר מהפונקציה.

Keyboard shortcuts

מבוא לתכנות בשפת C