Sorting an array of structures using merge sort

Question

So I have a structure called product and I have an array of products.

I am trying to sort the array by product price using merge sort, the problem is that my code is not swapping anything and I don't understand why. If someone could help me I would appreciate it a lot.

Structure:

typedef struct product {
    int ident;      /* idp of a product */
    char desc[64];  /* 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; /* state of a product, if 1 it is in the system else is 0 and is not in the sistem */
} product;

Merge sort algorithm

void mergesort_price(product a[], int left, int right) {
    int m = (right + left) / 2;
    if (right <= left)
      return;
    mergesort_price(a, left, m);
    mergesort_price(a, m + 1, right);
    merge_price(a, left, m, right);
}

void merge_price(product a[], int left, int m, int right) { 
    int i, j, k;
    for (i = m + 1; i > left; i--) 
        aux[i - 1] = a[i - 1];
    for (j = m; j < right; j++)
        aux[right + m - j] = a[j + 1];
    for (k = left; k <= right; k++)
        if (aux[j].price < aux[i].price || i > m)
            a[k] = aux[j--];
        else
        if ((aux[j].price == aux[i].price) || i > m) {
            if ((aux[j].ident < aux[i].ident) || i > m) {
                a[k] = aux[j--];
            }
        } else
            a[k] = aux[i++];
}

Example:

My input:

desc: pao, price:2, weight: 2, quant:200
desc: ovos, price:1, weight: 1, quant:100
desc: iscas, price:3, weight: 3, quant:300
desc: fiambre, price:2, weight: 2, quant:200
desc: queijo, price:2, weight: 2, quant:200

Correct output:

desc: ovos, price:1, weight: 1, quant:100
desc: pao, price:2, weight: 2, quant:200
desc: fiambre, price:2, weight: 2, quant:200
desc: queijo, price:2, weight: 2, quant:200
desc: iscas, price:3, weight: 3, quant:300

Program:

#include <stdlib.h> 
#include <stdio.h>
#include <string.h>

#define MAX_PROD 10000 /* max products in the system */

typedef struct product {
   int ident;      /* idp of a product */
   char desc[64];  /* 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; /* state of a product, if 1 it is in the system else is 0 and is not in the system */
} product;

product p1 = { 0, "pao", 2, 2, 200, 1 };
product p2 = { 1, "ovos", 1, 1, 100, 1 };
product p3 = { 2, "iscas", 3, 3, 300, 1 };
product p4 = { 3, "bacon", 2, 5, 400, 1 };
product p5 = { 4, "abacate", 2, 6, 500, 1 };

product sistem[5] = {};  /* array that contains the products */
product sistem2[5] = {}; /* Will be used has a copy of sistem */

sistem[5] = { p1, p2, p3, p4, p5}
product aux[5]; /* Auxliar array used in mergesort */

void mergesort_price(product a[], int left, int right) {
    int m = (right + left) / 2;
    if (right <= left)
        return;
    mergesort_price(a, left, m);
    mergesort_price(a, m + 1, right);
    merge_price(a, left, m, right);
}

void merge_price(product a[], int left, int m, int right) { 
    int i, j, k;
    for (i = m + 1; i > left; i--) 
        aux[i - 1] = a[i - 1];
    for (j = m; j < right; j++)
        aux[right + m - j] = a[j + 1];
    for (k = left; k <= right; k++)
        if (aux[j].price < aux[i].price || i > m)
            a[k] = aux[j--];
        else if ((aux[j].price == aux[i].price) || i > m) {
            if ((aux[j].ident < aux[i].ident) || i > m) {
                a[k] = aux[j--];
            }
        } else
            a[k] = aux[i++];
}

void print_array(product arr[]) {
    int i;
    for (i = 0; i < 5; i++) {
         printf("* %s %d %d %d\n", arr[i].desc, arr[i].price, arr[i].quant, arr[i].ident);
    }
}

void copy_el(product source[], product dest[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        dest[i] = source[i];
    }
}

int main() {   
    copy_el(sistem, sistem2, 5);
    printf("The products in the system are:\n");
    print_array(sistem);

    printf("\nSorted products by price in the system:\n");
    mergesort_price(sistem2, 5, 0);
    print_array(sistem2);

    return 0;
}

I know the input that I typed is not coded in the program I just gave the input in that way as an example to make it more comprehensible.

Answer 1

Remember as I mentioned in the top comments, your for loops are not initializing i, j, or k

Your sort looks a bit complicated.

There are two ways to do the merge:

(1) copy to temp array and merge back to original (this is what you're doing)

(2) merge from original left/right arrays to temp array and the copy the result back to the original (seems simpler to me)

Anyway, here's a refactored version:

#include <stdio.h>

typedef struct product {
    int ident;                          /* idp of a product */
    char desc[64];                      /* 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;                     /* state of a product, if its 1 its in
                                            the system else is 0 and is not in
                                            the system */
} product;

#define AMAX    28
product a[AMAX];
product aux[AMAX];

void merge_price(product a[], int low, int mid, int high);

void
mergesort_price(product a[], int low, int high)
{
    int mid = (high + low) / 2;

    if (high <= low)
        return;
    mergesort_price(a, low, mid);
    mergesort_price(a, mid + 1, high);
    merge_price(a, low, mid, high);
}

void
merge_price(product a[], int low, int mid, int high)
{
    int right;
    int left;
    int k;
    int i;

    k = 0;
    left = low;
    right = mid + 1;

    for (;  (left <= mid) && (right <= high);  ++k) {
        if (a[left].price <= a[right].price)
            aux[k] = a[left++];
        else
            aux[k] = a[right++];
    }

    for (;  left <= mid;  ++left, ++k)
        aux[k] = a[left];

    for (;  right <= high;  ++right, ++k)
        aux[k] = a[right];

    k = low;
    i = 0;
    for (;  k <= high;  ++k, ++i)
        a[k] = aux[i];
}

void
show(void)
{
    for (int idx = 0;  idx < AMAX;  ++idx)
        printf(" %d",a[idx].price);
    printf("\n");
}

int
main(void)
{

    for (int idx = 0;  idx < AMAX;  ++idx)
        a[idx].price = AMAX - idx;
    show();

    mergesort_price(a,0,AMAX - 1);
    show();
}

---

UPDATE:

ok it worked thanks but when i tried to do it but for strings it didnt work. I only changed the if statement really, like can u explain me why it didnt pls.

Okay, I've created a version that generates random product descriptions and sorts by price. It then resorts based on desc [a string sort].

I did this with a pointer to a comparison function that is passed as an extra argument to the existing functions. This is similar to the last argument of libc's qsort function.

This could be extended to a "multikey" sort (e.g. sort by price and then by desc [or whatever struct members you wish]). See: cmpbyboth and cmpbyall.

Note that, at first glance, cmpbyall should be faster than cmpbyboth but with (e.g.) -O2 the compiler may choose to inline the [simple] functions so that both functions may generate exactly the same executable code.

Anyway, here's the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define STRMAX      64
#define GENSTR      7

typedef struct product {
    int ident;                          /* idp of a product */
    char desc[STRMAX];                  /* 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;                     /* state of a product, if its 1 its in
                                            the system else is 0 and is not in
                                            the system */
} product;

typedef int (*cmpfnc_p)(const product *,const product *);

#define AMAX    28
product a[AMAX];
product aux[AMAX];

void merge_price(product a[], int low, int mid, int high,cmpfnc_p cmpfnc);

void
mergesort_price(product a[], int low, int high, cmpfnc_p cmpfnc)
{
    int mid = (high + low) / 2;

    if (high <= low)
        return;
    mergesort_price(a, low, mid, cmpfnc);
    mergesort_price(a, mid + 1, high, cmpfnc);
    merge_price(a, low, mid, high, cmpfnc);
}

void
merge_price(product a[], int low, int mid, int high,cmpfnc_p cmpfnc)
{
    int cmpflg;
    int right;
    int left;
    int k;
    int i;

    k = 0;
    left = low;
    right = mid + 1;

    for (;  (left <= mid) && (right <= high);  ++k) {
        cmpflg = cmpfnc(&a[left],&a[right]);
        if (cmpflg <= 0)
            aux[k] = a[left++];
        else
            aux[k] = a[right++];
    }

    for (;  left <= mid;  ++left, ++k)
        aux[k] = a[left];

    for (;  right <= high;  ++right, ++k)
        aux[k] = a[right];

    k = low;
    i = 0;
    for (;  k <= high;  ++k, ++i)
        a[k] = aux[i];
}

void
show(const char *tag)
{

    printf("\n");
    printf("%s",tag);

    for (int idx = 0;  idx < AMAX;  ++idx)
        printf(" %s=%d",a[idx].desc,a[idx].price);

    printf("\n");
}

// genstr -- get random string
void
genstr(char *desc)
{
    int len;
    int idx;
    int chr;
    int carry;

    // get random string length
    len = (rand() % GENSTR) + 1;

    // fill in random string
    for (idx = 0;  idx < len;  ++idx) {
        chr = rand() % 26;
        chr += 'a';
        *desc++ = chr;
    }

    *desc = 0;
}

// cmpbyprice -- compare by price
int
cmpbyprice(const product *left,const product *right)
{
    int cmpflg;

    cmpflg = left->price - right->price;

    return cmpflg;
}

// cmpbydesc -- compare by description
int
cmpbydesc(const product *left,const product *right)
{
    int cmpflg;

    cmpflg = strcmp(left->desc,right->desc);

    return cmpflg;
}

// cmpbyboth -- compare by price description
int
cmpbyboth(const product *left,const product *right)
{
    int cmpflg;

    do {
        cmpflg = cmpbyprice(left,right);
        if (cmpflg)
            break;

        cmpflg = cmpbydesc(left,right);
        if (cmpflg)
            break;

        // add more if you like ...
    } while (0);

    return cmpflg;
}

// cmpbyall -- compare by price description [faster version]
int
cmpbyall(const product *left,const product *right)
{
    int cmpflg;

    do {
        cmpflg = left->price - right->price;
        if (cmpflg)
            break;

        cmpflg = strcmp(left->desc,right->desc);
        if (cmpflg)
            break;

        // add more if you like ...
    } while (0);

    return cmpflg;
}

int
main(int argc,char **argv)
{
    unsigned int seed;
    product *ptr;

    --argc;
    ++argv;

    if (argc > 0)
        seed = atoi(*argv);
    else
        seed = time(NULL);
    printf("SEED: %u\n",seed);
    srand(seed);

    for (int idx = 0;  idx < AMAX;  ++idx) {
        ptr = &a[idx];
        ptr->price = AMAX - idx;
        genstr(ptr->desc);
    }
    show("INITED");

    mergesort_price(a,0,AMAX - 1,cmpbyprice);
    show("BYPRICE");

    mergesort_price(a,0,AMAX - 1,cmpbydesc);
    show("BYDESC");

    mergesort_price(a,0,AMAX - 1,cmpbyboth);
    show("BYBOTH");

    mergesort_price(a,0,AMAX - 1,cmpbyall);
    show("BYALL");
}