Sort an array of structures in alphabetical order using merge sort

Question

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.

arr is an array of pointers to structures, to access a member of a pointer to a structure you need to use the arrow syntax: arr[k++]->desc. — Some programmer dude
– Some programmer dude, Commented Mar 30, 2020 at 16:23
yes i did change it but it gives me does warnings at gives segmentation fault whenever i use that sorting algorithm — Martim Correia
– Martim Correia, Commented Mar 30, 2020 at 17:03

Chris Dodd · Accepted Answer · 2020-03-30 19:58:05Z

1

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.

edited Mar 30, 2020 at 19:58

answered Mar 30, 2020 at 19:22

Chris Dodd

127k14 gold badges150 silver badges243 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

chqrlie Over a year ago

The prototype for product_compare should be int product_compare(const void *a_, const void *b_) and a and b should also be const pointers.

Collectives™ on Stack Overflow

Sort an array of structures in alphabetical order using merge sort

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related