qsort: Using array

1. The realloc operation can be expensive if the the operation is carried out for a large number of times AND/OR if the memory is already fragmented.

2. A malloc operation could be considered but it would require a flag to indicate the first instance of executing the function

if ( FLAG == TRUE)
   Memory already allocated. Don't allocate any memory
else  { /* Flag = FALSE */
   Allocate Memory
   Set Flag = TRUE
}


--------------------------------------x------------------x-------------------x-----------------------------
#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;

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 ;
    return (*two)->number - (*one)->number ;

}

int adi_delete_walker(adi_delete_list_t * delete, adi_data_t * data)
{
    static adi_data_t* array[ARRAY_SIZE];
    void *temp = NULL;

    delete->first = array;
    memcpy(&array[delete->count], &data, sizeof(adi_data_t *));
    delete->count++;


}

int main (int argc, char* argv[])
{
    adi_delete_list_t delete;
    adi_data_t data_array[ARRAY_SIZE];
    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 < ARRAY_SIZE ; 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 < ARRAY_SIZE ; i++) {
        printf(" POST SORT: Data Array filled with %d \n", (*(delete.first)[i]).number);
     }
 }

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);

}