qsort Example

1. This example will demonstrate how to sort a given list in ascending or descending order

2. Many a times the structures are quite big and allocating such structures could be resource intensive exercise. Therefore I allocate a list of pointers to pointers (double pointer) to the original data structure.

3. QSORT sorts only arrays or data stored in contiguous memory locations. Therefore can't be directly used to sort linked lists.

Workaround : Walk the Linked List
                       Store the pointers to these nodes in an array/allocated memory location
                       Call Qsort to sort this array based on a comparison function that you define.

###include files : stdio.h -- stdlib.h -- string .h ####

--  This function will read the contents of a linked-list/array and copy into an "array" of pointers to the data. Qsort will sort this array.

#define ARRAY_SIZE 10

typedef struct adi_data_t_ {
    unsigned int number;
} adi_data_t;

typedef struct adi_delete_list_t_ {
    adi_data_t ** first;
    unsigned int count;
} adi_delete_list_t;

/* compare function to sort in ASCENDING order */
int adi_compare_data (const void * a, const void *b)
{
   const adi_data_t ** one = (const adi_data_t **) a;
   const adi_data_t ** two = (const adi_data_t **) b;

   printf("Number one : [%d] Number two : [%d]  ret [%d]\n", (*one)->number, (*two)->number, (*one)->number - (*two)->number);
   return (*one)->number - (*two)->number ;

}

/* compare function to sort in DESCENDING order */

int adi_compare_data (const void * a, const void *b)

{

   const adi_data_t ** one = (const adi_data_t **) a;

   const adi_data_t ** two = (const adi_data_t **) b;

   printf("Number one : [%d] Number two : [%d]  ret [%d]\n", (*one)->number, (*two)->number, (*one)->number - (*two)->number);

   return (*two)->number - (*one)->number ;

}

int adi_delete_walker(adi_delete_list_t * delete, adi_data_t * data)
{
    static adi_data_t ** list = NULL;
    void *temp = NULL;

    /* allocate memory for the list */
    temp = realloc(list, (delete->count + 1) * sizeof (adi_data_t *));
    if(temp == NULL) {
        printf("###!Ady: Hell Freezes over: Realloc failed \n");
    } else {
        list = (adi_data_t **) temp;
        delete->first = list;
        memcpy(&list[delete->count], &data, sizeof(adi_data_t *));
        printf(" First [%p] List [%p] Current element:[%p] \n", delete->first, list, &list[delete->count]);
        delete->count++;
    }
}

int main (int argc, char* argv[])

{

    adi_delete_list_t delete;

    adi_data_t data_array[10];

    unsigned int i = 0;

    memset(&delete, 0, sizeof(adi_delete_list_t));

    /* Fill the array and pass it to the delete function */

    for (i=0; i < 10 ; i++) {

        data_array[i].number = rand()/1000000;

        printf(" Data Array filled with %d \n", data_array[i].number);

        adi_delete_walker(&delete, &data_array[i]);

    }

    printf("qsort parameters: first [%p] count [%d]", delete.first, delete.count);

    /* qsort the array */

    qsort(delete.first, delete.count, sizeof(adi_data_t *), adi_compare_data);

     for (i=0; i < 10 ; i++) {

        printf(" POST SORT: Data Array filled with %d \n", (*(delete.first)[i]).number);

     }

    free(delete.first);

}