4.7 אלגוריתמים פתרון

תרגיל 1 - פתרון: מיון מערך של מספרים שלמים

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int arr[] = {42, 17, 8, 99, 3, 55, 21, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("לפני: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    qsort(arr, n, sizeof(int), cmp);

    printf("אחרי: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

---

תרגיל 2 - פתרון: מיון בסדר יורד

#include <stdio.h>
#include <stdlib.h>

int cmp_desc(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);  // הפוך - b מינוס a
}

int main() {
    int arr[] = {10, 40, 20, 50, 30};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("לפני: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    qsort(arr, n, sizeof(int), cmp_desc);

    printf("אחרי: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

ההבדל היחיד מתרגיל 1 הוא שבפונקציית ההשוואה מחזירים b - a במקום a - b. ככה qsort ממיינת בסדר יורד במקום עולה.

---

תרגיל 3 - פתרון: מיון מערך של מחרוזות

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp_strings(const void *a, const void *b) {
    const char *str_a = *(const char **)a;
    const char *str_b = *(const char **)b;
    return strcmp(str_a, str_b);
}

int main() {
    char *names[] = {"Eve", "Alice", "Charlie", "Bob", "David"};
    int n = sizeof(names) / sizeof(names[0]);

    printf("לפני: ");
    for (int i = 0; i < n; i++) {
        printf("%s ", names[i]);
    }
    printf("\n");

    qsort(names, n, sizeof(char *), cmp_strings);

    printf("אחרי: ");
    for (int i = 0; i < n; i++) {
        printf("%s ", names[i]);
    }
    printf("\n");

    return 0;
}

שימו לב לפונקציית ההשוואה: כי המערך הוא מערך של מצביעים (char *), הפרמטרים של פונקציית ההשוואה הם מצביעים למצביעים - כלומר char **. לכן עושים המרה ל-const char ** ואז dereference כדי לקבל את ה-char * עצמו.

---

תרגיל 4 - פתרון: חיפוש בינארי במערך ממוין

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("המערך: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    int target;
    printf("הכנס מספר לחיפוש: ");
    scanf("%d", &target);

    int *found = bsearch(&target, arr, n, sizeof(int), cmp);

    if (found != NULL) {
        int index = found - arr;  // חישוב האינדקס מהפרש מצביעים
        printf("נמצא: %d באינדקס %d\n", *found, index);
    } else {
        printf("המספר %d לא נמצא במערך\n", target);
    }

    return 0;
}

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

---

תרגיל 5 - פתרון: מיון וחיפוש ביחד

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int arr[6];

    printf("הכנס 6 מספרים: ");
    for (int i = 0; i < 6; i++) {
        scanf("%d", &arr[i]);
    }

    // מיון המערך
    qsort(arr, 6, sizeof(int), cmp);

    printf("מערך ממוין: ");
    for (int i = 0; i < 6; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // חיפוש
    int target;
    printf("הכנס מספר לחיפוש: ");
    scanf("%d", &target);

    int *found = bsearch(&target, arr, 6, sizeof(int), cmp);

    if (found != NULL) {
        printf("נמצא: %d\n", *found);
    } else {
        printf("המספר %d לא נמצא\n", target);
    }

    return 0;
}

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