استخدام qsort

دالة الفرز في المكتبة القياسية

توقيع qsort

كتابة دالة مقارنة

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

int cmp_int(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y); /* safe, no overflow */
}

int main(void) {
    int a[] = {5, 2, 9, 1, 3};
    qsort(a, 5, sizeof(int), cmp_int);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

تجنّب الطرح في دوال المقارنة

#include <stdio.h>

int main(void) {
    int x = 2000000000, y = -2000000000;
    printf("unsafe x-y = %d\n", x - y);          /* overflow */
    printf("safe        = %d\n", (x > y) - (x < y));
    return 0;
}

الترتيب التنازلي

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

int cmp_desc(const void *a, const void *b) {
    int x = *(const int *)a, y = *(const int *)b;
    return (y > x) - (y < x);
}

int main(void) {
    int a[] = {5, 2, 9, 1, 3};
    qsort(a, 5, sizeof(int), cmp_desc);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

فرز السلاسل النصية

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

int cmp_str(const void *a, const void *b) {
    const char *x = *(const char * const *)a;
    const char *y = *(const char * const *)b;
    return strcmp(x, y);
}

int main(void) {
    const char *names[] = {"charlie", "alice", "bob"};
    qsort(names, 3, sizeof(char *), cmp_str);
    for (int i = 0; i < 3; i++) printf("%s ", names[i]);
    printf("\n");
    return 0;
}

فرز البنى

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

typedef struct { char name[16]; int age; } Person;

int by_age(const void *a, const void *b) {
    const Person *p = a, *q = b;
    return (p->age > q->age) - (p->age < q->age);
}

int main(void) {
    Person ppl[] = {{"Ann", 30}, {"Ben", 25}, {"Cid", 40}};
    qsort(ppl, 3, sizeof(Person), by_age);
    for (int i = 0; i < 3; i++) printf("%s %d\n", ppl[i].name, ppl[i].age);
    return 0;
}

الفرز متعدد المفاتيح

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

typedef struct { char name[16]; int age; } Person;

int cmp(const void *a, const void *b) {
    const Person *p = a, *q = b;
    if (p->age != q->age)
        return (p->age > q->age) - (p->age < q->age);
    return strcmp(p->name, q->name);
}

int main(void) {
    Person ppl[] = {{"Zoe", 30}, {"Amy", 30}, {"Bo", 25}};
    qsort(ppl, 3, sizeof(Person), cmp);
    for (int i = 0; i < 3; i++) printf("%d %s\n", ppl[i].age, ppl[i].name);
    return 0;
}

qsort غير مستقرة

الدالة المرافقة bsearch

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

int cmp_int(const void *a, const void *b) {
    int x = *(const int *)a, y = *(const int *)b;
    return (x > y) - (x < y);
}

int main(void) {
    int a[] = {1, 3, 5, 7, 9};
    int key = 7;
    int *found = bsearch(&key, a, 5, sizeof(int), cmp_int);
    printf("%s\n", found ? "found" : "missing");
    return 0;
}

لماذا نستخدم qsort

اختبار سريع

مراجعة