Lesson 12

Sorting: qsort (stdlib.h)

• void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *))

  • void *base: Starting address

  • size_t nitems: number of items to sort

  • size_t size: size in bytes for each element

  • int (*compar)(const void *, const void *): Pointer to a function which compares 2 elements (a and b)

  • Returning negative value means a is less than b, 0 means a equals b, and positive means that a is larger than b.

• Example for sorting int implementation

    int asc_isort(const void *a, const void *b) {
        int *ap = (int *)a;
        int *bp = (int *)b;
  
        return *ap - *bp;
    }
    // shorthand imlpementation is
    int asc_isort(const void *a, const void *b) {
        return *(*int)a - *(*int)b;
    }
  

  becaue *(*int)a will convert a into an integer pointer then it will dereference a same with b.

Sorting float numbers

const size_t size = 5;
float arr[size] = {2.0, 1.0, 1.5, 0.3, 1.9};
qsort(arr, size, sizeof(int), asc_float_sort);

• The return type of the sorting method is int, therefore when dealing we have to be aware that if we do the calculation ap - *ab on floating points, this will loose the precision potentially causing a logic error.

• If i were to do the same implementation as i did with int, It would have resulted in the incorrect sorting (1.0 0.3 2.0 1.5 1.9) because converting float to int will result in precision loss. eg. 2.0 - 1.5 = 0.5then we return 0.5 which is automatically typecasted to int would return 0 - 2.0 is not the same as 1.5. Therefore the implementation must be different

    int asc_float_sort(const void * a, const void * b) {
        float *ap = (float *)a;
        float *bp = (float *)b;
  
        if (*ap < *bp) return -1;
        if (*bp < *ap) return 1;
        return 0;
    }
  

Sorting array of pointers

• It’s the same as sorting an array, however, we need to use double pointer

    // for the following
    int arr[5] = {2, 5, 0, 9, 1};
    int *parr[5] = {arr, arr+1, arr+2, arr+3, arr+4};
    qsort(parr, 5, sizeof(int *), asc_parr_sort);
  
    // we would have the following implementation
    int asc_parr_sort(const void *a, const void *b) {
        int **ap = (int **)a;
        int **bp = (int **)b;
  
        return **ap - **bp;
    }
  

• (int **)a is because the function receives a pointer of an element, and since the element is a pointer, we need to dereference both. so *a equals to &parr[i] we dereference once and we get parr[i] which is an integer pointer, we dereference again and we get arr[i].

Sorting structs

• It’s the same as sorting an array, however, we need to use struct members for comparison purposes.

    // given the following definition
    typedef struct person person;
    struct person {
        char name[10];
        int age;
    };
  
    // with the following definition
    const size_t size = 4;
    person people[size] = {
        {"gabbie", 36},
        {"arty", 42},
        {"bob", 42},
        {"hayden", 1}
    };
  
    // here's the expected implemenetations
  
    int asc_person_by_name_sort(const void *a, const void *b) {
        person *ap = (person *)a;
        person *bp = (person *)b;
  
        return strcmp(ap->name, bp->name);
    }
  
    int asc_person_by_age_sort(const void *a, const void *b) {
        person *ap = (person *)a;
        person *bp = (person *)b;
  
        return ap->age - bp->age;
    }
  
    int asc_person_by_age_and_name_sort(const void *a, const void *b) {
        person *ap = (person *)a;
        person *bp = (person *)b;
        int age_sort = ap->age - bp->age;
  
        if (age_sort != 0) {
            return age_sort;
        }
  
        return strcmp(ap->name, bp->name);
    }