MergeSort on struct array

This is a discussion on MergeSort on struct array within the C Programming forums, part of the General Programming Boards category; Hi I am creating a program that uses mergesort to sort birthdays by their day of the year. In my ...

  1. #1
    Registered User
    Join Date
    Nov 2012
    Posts
    51

    MergeSort on struct array

    Hi I am creating a program that uses mergesort to sort birthdays by their day of the year. In my current build, I am storing an array of structs into a new date_array and sorting the date_array, then my plan was to create a function that searches the list of students and matches them to their name and birthday. But now I am thinking that it would be best to actually merge the array of struct instead of just a regular array. The reason that I think its best to sort the struct array is because our file can contain up to 1000 names and searching the array of names and birthdays and trying to match them will be a very slow process. What do you guys think? And any advice on merge sorting an array of structs? I have never done this and when I googled it, many answers talked about building said matching function, but I still don't think this is the right strategy.

    Text File
    Code:
    2
    9
    AL SMITH NOVEMBER 30 1989
    STEVE HARPER AUGUST 17 1988
    CASEY PETERSON OCTOBER 21 1988
    JOHN SMITH APRIL 20 1980
    BILL CLINTON NOVEMBER 2 1990
    B A JUNE 10 1902
    C D AUGUST 19 1994
    G H JANUARY 10 1980
    Z Y MAY 27 1990
    2
    JOHN SMITH
    BILL CLINTON
    4
    DAN MARINO SEPTEMBER 15 1961
    JOHN ELWAY JUNE 28 1960
    JOE MONTANA JUNE 11 1956
    DAN FOUTS JUNE 10 1951
    1
    JOE MONTANA
    Code:
    # include <stdio.h>
    # include <stdlib.h>
    # include <string.h>
     
    # define MAX_CHARS_IN_NAME 30
    # define NUMBER_OF_MONTHS 12
     
     typedef struct
    {
        char first_name[MAX_CHARS_IN_NAME];
        char last_name[MAX_CHARS_IN_NAME];
        char month[10];
        int day;
        int year;
        int day_of_year;
    } person;
    
    void MergeSort(int values[], int start, int end);
    void Merge(int values[], int start, int middle, int end);
    void Print_Array(int values[], int length);
    void Assign_Dates_To_Queried_Students(person *classmate, person *queried, int size);
    void Convert_Student_Birthday_To_Day_of_Year(person *classmate, int size);
     
    int main()
    {
        // Create a file pointer and open the file
        FILE *ifp = fopen("birthday.txt", "r");
     
        // Test to see if the file opens
        if (!ifp)
        {
            printf("The file is unable to open!\n");
            return -1;
        }
     
        // Create variables for the number of classes, number of students in the class, birthday month/day/year, number of queried students, queried students
        int i, num_classes, num_students, num_queried;
     
         // Read in the number of classes. PROPERLY READ IN (TESTED)
        fscanf(ifp, "%d", &num_classes);
        //printf("The number of classes is %d\n", num_classes);
     
         // Read in the number of students in the class. PROPERLY READ IN (TESTED)
        fscanf(ifp, "%d", &num_students);
        //printf("The number of students is %d\n", num_students);
    
        // Allocating space for the students in the classroom
        person *student = malloc(sizeof(person)*num_students);
        // Allocating space for the queried student structures.
        person *queried_student = malloc(sizeof(person)*num_queried);
     
         for (i=0; i< num_students; i++)
        {
            // Scan in the student's first name, last name
            fscanf(ifp, "%s", student[i].first_name);
            fscanf(ifp, "%s", student[i].last_name);
    
            // Scan in the student's birth month, day, year
            fscanf(ifp, "%s", student[i].month);
            //printf("\n");
            //printf("the student's month is %s\n", student[i].month);
            fscanf(ifp, "%d", &student[i].day);
            fscanf(ifp, "%d", &student[i].year);
        }
        
        Convert_Student_Birthday_To_Day_of_Year(student, num_students);
    
        printf("\n");
        
        int date_array[num_students];
        printf("The unsorted array:\n");
        for (i=0; i< num_students; i++)
        {
            date_array[i] = student[i].day_of_year;
            printf("%d ", date_array[i]);
        } 
        printf("\n");
    
        MergeSort(date_array, 0, num_students-1);
        printf("The sorted array:\n");
        Print_Array(date_array, num_students);
    
        // Scan in the number of queried students
        fscanf(ifp, "%d", &num_queried);
    
        // For loop that reads in the queried student(s) first and last name
        for (i=0; i< num_queried; i++)
        {
            fscanf(ifp, "%s", queried_student[i].first_name);
            fscanf(ifp, "%s", queried_student[i].last_name);
            //printf("The queried student is %s %s\n", queried_student[i].first_name, queried_student[i].last_name);
        }
    
        // This function assigns dates to the queried students by searching the list of the classmates
        Assign_Dates_To_Queried_Students(student, queried_student, num_students);
        Convert_Student_Birthday_To_Day_of_Year(queried_student, num_queried);
        
        int queried_date_array[num_queried];
        for (i=0; i< num_queried; i++)
        {
            queried_date_array[i] = queried_student[i].day_of_year;
            printf("%d ", queried_date_array[i]);
        }
        printf("\n");
                
        // Compare queried_date array to the sorted date arrays
        //person *closest_date()
    
         // print output
     
        fclose(ifp);
        return 0;
    }
    
    void Merge(int values[], int start, int middle, int end) 
    {
    
        //printf("merge %d, %d, %d\n", start, middle, end);
        
        int *temp, i, length, count1, count2, mc;
      
        // Allocate the proper amount of space for our auxiliary array.
        length = end - start + 1;
        temp = (int*)calloc(length, sizeof(int));
    
        // These will be our indexes into our two sorted lists.
        count1 = start;
        count2 = middle;
      
        // Keeps track of our index into our auxiliary array.
        mc = 0;
    
        // Here we copy values into our auxiliary array, so long as there are 
        // numbers from both lists to copy.
        while ((count1 < middle) || (count2 <= end)) {
    
            // Next value to copy comes from list one - make sure list
            // one isn't exhausted yet. Also make sure we don't access index
            // count2 if we aren't supposed to.
            if (count2 > end || (count1 < middle && values[count1] < values[count2])) {
                temp[mc] = values[count1];
                count1++;
                mc++;
            }
        
            // We copy the next value from list two.
            else {
                temp[mc] = values[count2];
                count2++;
                mc++;
            }
        }
    
        // Copy back all of our values into the original array.
        for (i=start; i<=end; i++)
            values[i] = temp[i - start];
    
        // Don't need this space any more!
        free(temp);
    }
    
    void MergeSort(int values[], int start, int end)
    {
        int mid;
      
        // Check if our sorting range is more than one element.
        if (start < end) 
        {
    
            mid = (start+end)/2;
        
            // Sort the first half of the values.
            MergeSort(values, start, mid);
        
            // Sort the last half of the values.
            MergeSort(values, mid+1, end);
        
            // Put it all together.
            Merge(values, start, mid+1, end);
        }
    }
    
    void Print_Array(int values[], int length) 
    {
    
        int i;
        for (i=0; i<length; i++)
            printf("%d ", values[i]);
    }
    
    void Assign_Dates_To_Queried_Students(person *classmate, person *queried, int size)
    {
        // COMPARING THE QUERIED STUDENT'S NAMES WITH STUDENTS NAMES
        // THIS IS NECCESSARY BECAUSE THE STUDENTS DATA NEEDS TO BE COPIED TO THE QUERIED STUDENT
        int i = 0;
        int j = 0;
    
        while (i< size)
        {
            // If the names of the queried student matches the name of the student in the list
            if (strcmp(classmate[i].first_name, queried[j].first_name) == 0
                && strcmp(classmate[i].last_name, queried[j].last_name) == 0)
            {
                strcpy(classmate[i].first_name, queried[j].first_name);
                strcpy(classmate[i].last_name, queried[j].last_name);
                strcpy(queried[j].month, classmate[i].month);
                queried[j].day = classmate[i].day;
                queried[j].year = classmate[i].year;
                queried[j].day_of_year = classmate[i].day_of_year;
                //printf("\n");
                //printf("%s %s", classmate[i].first_name, classmate[i].last_name);
                //printf(" %s", classmate[i].month);
                //printf(" %d", classmate[i].day);
                //printf(" %d\n", classmate[i].year);
                i++;
                j++;
            }
    
            else
            {
                i++;
            }
    
        }
    
        printf("\n");
    }
    
    void Convert_Student_Birthday_To_Day_of_Year(person *classmate, int size)
    {
        // Creating an integer first_day_of_month variable that will convert the month 
            // to the day of the year (e.g. March 1st = 60 because March 1st is the 60th day of the year...)
            
            // CREATE IF STATEMENTS FOR NON-FEB 29TH AND FEB 29TH'S
            
            // first_day_of_month is equal to the day of the year for the first of each month
            int first_day_of_month;
            int i;
    
            printf("\n");
    
            for (i=0; i< size; i++)
            {
                if (strcmp(classmate[i].month, "JANUARY") == 0)
                first_day_of_month = 1;
            
                else if (strcmp(classmate[i].month, "FEBRUARY") == 0)
                    first_day_of_month = 32;
            
                else if (strcmp(classmate[i].month, "MARCH") == 0)
                    first_day_of_month = 60;
            
                else if (strcmp(classmate[i].month, "APRIL") == 0)
                    first_day_of_month = 91;
            
                else if (strcmp(classmate[i].month, "MAY") == 0)
                    first_day_of_month = 121;
            
                else if (strcmp(classmate[i].month, "JUNE") == 0)
                    first_day_of_month = 152;
            
                else if (strcmp(classmate[i].month, "JULY") == 0)
                    first_day_of_month = 182;
            
                else if (strcmp(classmate[i].month, "AUGUST") == 0)
                    first_day_of_month = 213;
            
                else if (strcmp(classmate[i].month, "SEPTEMBER") == 0)
                    first_day_of_month = 244;
                
                else if (strcmp(classmate[i].month, "OCTOBER") == 0)
                    first_day_of_month = 274;
            
                else if (strcmp(classmate[i].month, "NOVEMBER") == 0)
                    first_day_of_month = 305;
            
                else
                    first_day_of_month = 335;
    
                // This line of code changes the student's birthdays into the day of the year.
                classmate[i].day_of_year = first_day_of_month + (classmate[i].day - 1);
            
                //printf("%s %s's birthday is the %d day of the year!\n", classmate[i].first_name, classmate[i].last_name, 
                //                                                 classmate[i].day_of_year);
            }
    
    }

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Sorting the records, by some field that will give you the most separation between the students, is good. Usually, that would be a unique student ID number or string of digits, but birthday and name are OK. A binary search of the sorted records will definitely put some zip! into your search.

    I don't like the whole "day of the month" logic, and would dump it. Use a simple number or string for the b-day: 1990-03-21: year 4 digits, month 2 digits day 2 digits. Show it with the hyphens, internally, it doesn't need them. Speeds up everything compared to strcmp()'s, while cutting down on a lot of code, too. Now you'll really be zipping right along!

  3. #3
    Registered User
    Join Date
    Nov 2012
    Posts
    51
    Quote Originally Posted by Adak View Post
    Sorting the records, by some field that will give you the most separation between the students, is good. Usually, that would be a unique student ID number or string of digits, but birthday and name are OK. A binary search of the sorted records will definitely put some zip! into your search.

    I don't like the whole "day of the month" logic, and would dump it. Use a simple number or string for the b-day: 1990-03-21: year 4 digits, month 2 digits day 2 digits. Show it with the hyphens, internally, it doesn't need them. Speeds up everything compared to strcmp()'s, while cutting down on a lot of code, too. Now you'll really be zipping right along!
    I like your idea but I figured it was the way to sort it by day of the year as that's what the professor and other students suggested. Would you suggest reconfiguring the merge sort to take in an array of structs or just the array of integers and then creating a matching function.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    By all means, go with what the prof recommends - unless he has expressed that you should always look for your own good way to do things, and not just use his. Prof's vary in this, from my VERY limited experience.

    Use the array of structs.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting array of struct inside struct
    By blueboyz in forum C Programming
    Replies: 13
    Last Post: 04-24-2012, 02:15 AM
  2. 2 problems: Struct array and pointer + struct
    By v1n1c1u5 in forum C Programming
    Replies: 0
    Last Post: 12-13-2009, 04:38 PM
  3. Initialising struct array withing struct
    By Disco Elephant in forum C Programming
    Replies: 4
    Last Post: 08-16-2009, 10:17 AM
  4. MergeSort with array of pointers
    By lionheart in forum C Programming
    Replies: 18
    Last Post: 08-01-2008, 10:23 AM
  5. returning a pointer of a struct of a struct array...
    By myrddinb in forum C Programming
    Replies: 1
    Last Post: 04-13-2004, 06:49 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21