4.7 - אלגוריתמים - הרצאה

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

התחביר:

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

הפרמטרים:

• base - מצביע לתחילת המערך

• nmemb - מספר האיברים במערך

• size - גודל של כל איבר (למשל sizeof(int))

• compar - פונקציית השוואה שתחזיר:

  • מספר שלילי אם a < b

  • אפס אם a == b

  • מספר חיובי אם a > b

דוגמה: מיון מערך של מספרים שלמים

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

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

int main() {
    int arr[] = {5, 1, 4, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

הפלט:

1 2 3 4 5

הפונקציה qsort שיכתבה את המערך המקורי במקום (in-place).

הפונקציה bsearch מבצעת חיפוש בינארי בתוך מערך ממוין. היא מחפשת איבר מתאים על פי מפתח (key) ומחזירה מצביע אליו אם נמצא, או NULL אם לא.

התחביר:

void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *));

• key - מצביע לערך שאתה מחפש

• base - תחילת המערך (חייב להיות ממוין!)

• nmemb - מספר האיברים

• size - גודל של כל איבר

• compar - אותה פונקציית השוואה כמו ב-qsort

דוגמה:

int arr[] = {1, 2, 3, 4, 5};
int target = 3;

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

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

אם המערך לא ממויין - bsearch עלול להחזיר תוצאה שגויה או לא למצוא את הערך.

לסיכום:

• qsort ממיינת מערכים - עליך לספק פונקציית השוואה מתאימה

• bsearch מחפשת ערך במערך ממויין - עם אותה פונקציית השוואה

• שתיהן פועלות על void* ולכן עובדות גם עם טיפוסים מורכבים

• פונקציית ההשוואה תמיד מקבלת שני מצביעים ל-void - יש להמיר אותם לטיפוס המתאים עם * ו-(type *)

• חובה לדעת אם המערך כבר ממויין לפני השימוש ב-bsearch