qsort on more than one item in a struct

Question

I'm tasked with the user inputting n lines containing a month, day and year in the form of 'January 12 99'.

I have to sort the list of dates chronologically using qsort first by year, then by day, then by month.

My problem is I am not sure of how to qsort on multiple indexes. I have done it for the year whic works fine but after that I don't know how to qsort on the day as surely it will just sort it by day but the years will be muddled up again?

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

typedef int (*compfn)(const void*, const void*);

struct date
{
    char month[9]; //Maximum of 9 characters in a month
    int day; //The day of the month (e.g. 18)
    int year; //The year of the date    
};

int sortDates(struct date *elem1, struct date *elem2)
{

    if (elem1 -> year < elem2 -> year)
    {
        return -1;
    }
    else 

    if (elem1->year > elem2->year)
        {
        return 1;
    }
    else
        return 0;

}


main()
{
    int n;
    int i;

    scanf("%d", &n);

    struct date *list;

    list = (struct date *)malloc((n * sizeof(struct date)));

    for(i = 0; i < n; i++)
    {
        scanf("%s %d %d", list[i].month, &list[i].day, &list[i].year);
    }

    qsort(list, sizeof(list), sizeof(struct date), (compfn)sortDates);

    for(i = 0; i < n; i++)
    {
        printf("%s %d %d\n", list[i].month, list[i].day, list[i].year);
    }
}

EDIT: So I have the sort working, I am just struggling with converting from an integer back to the string representation of the month when printing the sorted list. Here is the code, I am getting "array subscript is not an integer" error.

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

typedef int (*compfn)(const void*, const void*);

struct date
{
    int month;
    int day; //The day of the month (e.g. 18)
    int year; //The year of the date    
};

char* months[]= {
   "January", "February",
   "March", "April",
   "May", "June",
   "July", "August",
   "September", "October",
   "November", "December"};


int getMonth(char tempMonth[])
{
    int i = 0;
    for(i = 0; i<12; i++)
    {
            if(tempMonth == months[i]) return i;
    }
    return 0;
}

char getStringMonth(struct date month)
{
    return months[month];
}

int sortDates(struct date *elem1, struct date *elem2)
{
    if (elem1 -> year < elem2 -> year)
    {
        return -1;
    }
    else 

    if (elem1->year > elem2->year)
        {
        return 1;
    }


    if ( elem1->month < elem2->month )
    {
            return -1;
    }
    else 

    if ( elem1->month > elem2->month )
        {
        return 1; 
    }


    if ( elem1->day < elem2->day )
    {list
            return -1;
    }
        else 

    if ( elem1->day > elem2->day )
        {
        return 1;
    } 
        else

    return 0;
}

main()
{
    int n;
    int i;
    char tempMonth[255]; //Used to store the month until checked

    scanf("%d", &n);list

    struct date *list;

    list = (struct date *)malloc((n * sizeof(struct date)));

    for(i = 0; i < n; i++)
    {
        scanf("%s %d %d", tempMonth, &list[i].day, &list[i].year);
        list[i].month = getMonth(tempMonth);
    }

    qsort(list, sizeof(list), sizeof(struct date), (compfn)sortDates);

    for(i = 0; i < n; i++)
    {
        printf("%s %d %d", getStringMonth(list[i].month), list[i].day, list[i].year);
    }

}

Salcido

please don't do that. if you have another question then ask another one. – Dyanne

Answer 1

Remember to free the memory you malloc'd.

In the following code I have assumed that the month is stored as a number, but I see in your struct that this is not the case. I would convert the inputted month from string to a number, to ease the sorting process.

int sortDates(struct date* elem1, struct date* elem2)
{

    if ( elem1->year < elem2->year)
        return -1;
    else if ( elem1->year > elem2->year )
        return 1;


    /* here you are sure the years are equal, so go on comparing the months */

    if ( elem1->month < elem2->month )
        return -1;
    else if ( elem1->month > elem2->month )
        return 1; 

    /* here you are sure the months are equal, so go on comparing the days */

    if ( elem1->day < elem2->day )
        return -1;
    else if ( elem1->day > elem2->day )
        return 1; 
    else
        return 0; /* definitely! */

}

Also pay attention to this declaration: char month[9];, it is true that September is 9 chars, but you need a terminator char '\0' in C to close a string. To avoid this sort of problems, I would declare an array with all the months, to allow the checking and to convert the month from a string to a number:

char* allMonths[]=
   "January", "February",
   "March", "April",
   "May", "June",
   "July", "August",
   "September", "October",
   "November", "December";

char tmpMonth[255];
scanf("%s %d %d", tmpMonth, &list[i].day, &list[i].year);
/* convert tmpMonth to a number by finding it in the allMonths and throw error if not found */

Dyanne

I am having a bit of a problem getting back from an integer to a string when outputting the month. I have edited my original question. Any help no matter how small would be great – Salcido

allMonths[month_number -1] will do. month_number being in the range [1-12] while the array index starts with 0. – Dyanne

Answer 2

Instead of returning 0 when the two years are equal, just copy-paste the logic and apply it to months. Then once again for days. That's all.

By the way, if you want a chronological sort, you have to sort the years first, then the months, then the days. Not days then months.

And you should store months as numbers, not strings: this will be easier for a chronological sort.

Finally, I would name the function compareDates, not sortDates.

Phellem

Answer 3

Instead of returning 0 on the last else, compare another field:

else {
    if (elem1->day < elem2->day) {
        return -1;
    }
    else if (elem1->day > elem2->day) {
        return 1;
    }
    else {
        //compare months
    }
}

The basic idea is:

1. Check years, if they are not the same return result (as you do)
2. If years are the same, check days, if they are not the same return result
3. If days are also the same, check month.

Auctioneer

Answer 4

What you have is fine for the year (the major key). You just need a slight adaptation to use the month (the minor key) when the year is equal and you can extend this to as many levels of keys as you want.

Pseudo-code only for homework, I'm afraid:

def compare (date1, date2):
    if date1.year > date2.year:
        return 1
    if date1.year < date2.year:
        return -1

    # Years are equal here.

    if date1.month > date2.month
        return 1
    if date1.month < date2.month
        return -1

    # Years and months are equal here.

    if date1.day > date2.day
        return 1
    if date1.day < date2.day
        return -1

    # Years, months and days are all equal here.

    return 0

By doing a single "layered" comparison function like this, you won't have to worry about month sorting screwing up the order of the years, since it sorts by day within month within year.

And, as you can see, I'm not a big fan of the:

if condition:
    return something
else:
    carry on

idiom. The else is totally unnecessary and can cause massive levels of indentation where none is needed. I prefer:

if condition:
    return something

carry on

The actual method for sorting is best done by turning those month names into numeric values so the comparisons works better. That's probably best left for a different question but you could probably put together something with a string array:

char *months[] = {"January", "February", ... "December"};

and a for loop to convert the name into a value in the range 0 through 11.

Kalpak

Answer 5

You should alter your comparison function, sortDates, and make the decision based on days when years are equal and based on month when days and months are equal.

Griseous