CODEWITHSUNDEEP
ccompiler-errorsmergesortalphabetical-sort
Martim Correia
Martim Correia

Reputation: 505

Sort an array of structures in alphabetical order using merge sort

So basically I created 2 structures: one called product and the other called order. An order has an array of products and each product has description which is a string.

I'm trying to sort an array of products in an order called set_prod in an alphabetical order, I need to sort it based on the products description.

To do so I found a merge sort algorithm that did that but when I try to adapt it to sort my structures it gives a segmentation fault (core dumped) error and other errors that I dont comprehend as well.

Here is the code:

typedef struct product {
   int ident;
   char desc[MAX_CHARS]; /* string that describes a product eg. "bread" */
   int price;  /* price of the product*/
   int weight; /* weight of the product eg. 2kg */
   int quant; /* quantity of the product in stock */
   int state_prod;
} product;

typedef struct order {
   int ident_o;
   product set_prod[MAX_PRODS_OD]; /* Set of products */
   int state;
} order;

void Merge_str_2(product *arr[], int low, int mid, int high) //Merging the Array Function
{
    int nL = mid - low + 1;
    int nR = high - mid;

    char **L = malloc(sizeof(char *) * nL);
    char **R = malloc(sizeof(char *) * nR);
    int i;
    for (i = 0; i < nL; i++) {
        L[i] = malloc(sizeof(arr[low + i]->desc));
        strcpy(L[i], arr[low + i]->desc);
    }
    for (i = 0; i < nR; i++) {
        R[i] = malloc(sizeof(arr[mid + i + 1]->desc));
        strcpy(R[i], arr[mid + i + 1]->desc);
    }
    int j = 0, k;
    i = 0;
    k = low;
    while (i < nL && j < nR) {
        if (strcmp(L[i], R[j]) < 0)
            strcpy(arr[k++]->desc, L[i++]);
        else
            strcpy(arr[k++]->desc, R[j++]);
    }
    while (i < nL)
        strcpy(arr[k++]->desc, L[i++]);
    while (j < nR)
        strcpy(arr[k++]->desc, R[j++]);
}

void MergeSort_str(product **arr[], int low, int high) //Main MergeSort function
{
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort_str(arr, low, mid);
        MergeSort_str(arr, mid + 1, high);
        Merge_str_2(arr, low, mid, high);
    }
}

I can only compile with gcc -Wall -Wextra -Werror -ansi -pedantic and I get these warnings:

In function ‘main’:

warning: passing argument 1 of ‘MergeSort_str’ from incompatible pointer type [-Wincompatible-pointer-types]

          MergeSort_str(sistem_orders[ide].set_prod,0,MAX_PRODS_OD-1);
                        ^~~~~~~~~~~~~

note: expected ‘product *** {aka struct product ***}’ but argument is of type ‘product * {aka struct product *}’

 void MergeSort_str(product** arr[],int low,int high);
      ^~~~~~~~~~~~~

In function ‘MergeSort_str’:
warning: passing argument 1 of ‘Merge_str_2’ from incompatible pointer type [-Wincompatible-pointer-types]
         Merge_str_2(arr,low,mid,high);
                     ^~~
note: expected ‘product ** {aka struct product **}’ but argument is of type ‘product *** {aka struct product ***}’

void Merge_str_2(product* arr[],int low,int mid,int high)
      ^~~~~~~~~~~

Seriously any help would be appreciated because I am clueless about these errors.

Upvotes: 1

Views: 1293

Answers (1)

Chris Dodd
Chris Dodd

Reputation: 126253

The problem is that your sort function is designed to sort an array of pointers, and you want to sort an array of structures. So you need to either rewrite the sort function to work with an array of structures, or create an array of pointers and sort that, then convert it back to a (sorted) array of structures.

The easiest is probably just to use the stdlib qsort function (which does a quicksort, not a mergesort), which has an API designed to sort an array of arbitrary objects:

int product_compare(const void *a_, const void *b_) {
    const product *a = a_;
    const product *b = b_;
    return strcmp(a->desc, b->desc); }

...in main (or another function):

qsort(sistem_orders[ide].set_prod, MAX_PRODS_OD, sizeof(product), product_compare);

Note that this will sort empty elements to the front of the array, which might not be what you want -- you probably want to ignore the empty elements and keep the non-empty elements in the front, in which case you really want to extend your struct order with a count of the number of products, and pass that count to qsort as the second argument.

Upvotes: 1

Related Questions