Using Merge Sort With Struct Array

[Bogeyman]

Structure template:

typedef struct structure
{
    char name[48];
    int age;
}Structure;

Array of structs:

Structure array[10];

In C, is it possible to sort an array of structs, like the one above, by a particular member using merge sort? I managed to get merge sort to work with a regular array of integers, but my understanding of merge sort isn't very good and I'm not sure how to modify it to work with structs, or if it's even possible to.

If such a thing is possible, would someone be willing to show me how it's done?

Any help is much appreciated.

[TarikNeaj]

I managed to get merge sort to work with a regular array of integers

Please show that code.

[fg109]

It'll work exactly the same way, except instead of using the < operator, you'll have to create your own boolean function that'll impose the ordering between two objects of your struct. Or just overload the < operator for your struct.

EDIT:

In C

[Bogeyman]

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

void merge_sort(int[], int, int);
void merge(int[], int, int, int);

int main()
{
    int i;
    int array[8];

    printf("Enter values into array:\n");

    for(i = 0; i < 8; i++)
    {
        printf("Digit %d: ", i + 1);
        scanf("%d", &array[i]);
    }

    merge_sort(array, 0, 7);

    printf("\nSorted array:\n");

    for(i = 0; i < 8; i++)
    {
        printf("%d ", array[i]);
    }

    printf("\n");

    return 0;
}// end main()

void merge_sort(int a[], int low, int high)
{
    int mid = 0;

    if(low == high)
    {
        return;
    }
    else
    {
        mid = (low + high) / 2;

        merge_sort(a, low, mid);

        merge_sort(a, mid + 1, high);

        merge(a, low, mid, high);
    }
}// end merge_sort()

void merge(int a[], int low, int mid, int high)
{
    int i;
    int left_index = low;
    int right_index = mid + 1;
    int combined_index = low;
    int tempA[10];

    while(left_index <= mid && right_index <= high)
    {
        if(a[left_index] <= a[right_index])
        {
            tempA[combined_index++] = a[left_index++];
        }
        else
        {
            tempA[combined_index++] = a[right_index++];
        }
    }

    if(left_index == mid + 1)
    {
        while(right_index <= high)
        {
            tempA[combined_index++] = a[right_index++];
        }
    }
    else
    {
        while(left_index <= high)
        {
            tempA[combined_index++] = a[left_index++];
        }
    }

    for(i = low; i <= high; i++)
    {
        a[i] = tempA[i];
    }
}// end merge() 

The merge_sort() and merge() functions were taken from lecture notes, so like I said, my understanding is pretty sub-par/crap.

[fg109]

I think line 83 should be while(left_index <= mid).

You just need to change line 64 for it to work with your struct. As for how to change it, that depends on how you want to define one object of the struct as less than the other object.

[Bogeyman]

Okay, I've tried changing line 64 to if(a.age[left_index] <= a.age[right_index]) but it gives me a compiler error saying that I'm looking to access a member in something not a structure or a union. I'm missing something very obvious aren't I?

[Bogeyman]

If it's not too much trouble, would someone demonstrate with code how to use a struct with merge sort? I'm basically stuck right now.

[fg109]

You should have changed line 64 to if(a[left_index].age <= a[right_index].age). Also remember to change your function prototypes and headers to use your struct.

[Bogeyman]

@fg109
I tried what you suggested and I'm no longer getting compiler errors but it's not sorting the list. I'll post my program to see if that helps.

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

// Structure template
typedef struct
{
    char firstname[20];
    char surname[20];
    int age;
}Person;

// Function Prototypes
void merge_sort(Person[], int, int);
void merge(Person[], int, int, int);

int main()
{
    // Struct array to hold people's data
    Person list[3];

    // File pointer for file operations
    FILE *fp;

    int i = 0;
    int low = 0, high = 0;

    // Open the file
    fp = fopen("list_of_people.txt", "r");

    // If error
    if(fp == NULL)
    {
        puts("Error opening file.\n");
    }
    else
    {
        // Read in contents of file and store in struct array
        for(i = 0; i < 3; i++)
        {
            fscanf(fp, "%s %s %d", list[i].firstname, list[i].surname, &list[i].age);
        }

        // Function Call
        merge_sort(list, low, high);

        // Print contents after sorting
        for(i = 0; i < 3; i++)
        {
            fprintf(stdout, "%s %s\n %d\n", list[i].firstname, list[i].surname, list[i].age);
        }
    }

    return 0;
}// end main()

void merge_sort(Person a[], int low, int high)
{
    int mid = 0;

    if(low == high)
    {
        return;
    }
    else
    {
        mid = (low + high) / 2;

        merge_sort(a, low, mid);

        merge_sort(a, mid + 1, high);

        merge(a, low, mid, high);
    }
}// end merge_sort()

void merge(Person a[], int low, int mid, int high)
{
    int i;
    int left_index = low;
    int right_index = mid + 1;
    int combined_index = low;
    Person tempA[10];

    while(left_index <= mid && right_index <= high)
    {
        if(a[left_index].age <= a[right_index].age)
        {
            tempA[combined_index++] = a[left_index++];
        }
        else
        {
            tempA[combined_index++] = a[right_index++];
        }
    }

    if(left_index == mid + 1)
    {
        while(right_index <= high)
        {
            tempA[combined_index++] = a[right_index++];
        }
    }
    else
    {
        while(left_index <= mid)
        {
            tempA[combined_index++] = a[left_index++];
        }
    }

    for(i = low; i <= high; i++)
    {
        a[i] = tempA[i];
    }
}// end merge() 

The file I'm reading in from contains exactly this information:
Mr X
30

Ms Y
25

Dr Z
50

The numbers are the ages of the people.

Ideally, Id like it to be sorted so that if sorting by age the output is:
Ms Y
25

Mr X
30

Dr Z
50

[fg109]

    int low = 0, high = 0;
    //stuff
        merge_sort(list, low, high);

[Bogeyman]

Thanks very much, that worked.

EDIT:
Just to be clear, changing the value of high to 3 made it work.

It's strange though, I have another program which is more complicated but essentially very similar. Instead of reading in from one file, I'm reading in from three files and combining three separate lists. The lists are merged fine. Two of the members of the struct being read into are age and ID. I can sort the list by these two members, but only when I specify the other one to the one I want to sort by. So if I choose to sort by age, it will sort by ID and vice versa when I choose ID. I've checked the code and I can't find the reason why this might be happening. What reasons might there be for this 'undefined behaviour'?

[Bogeyman]

Right, I've spent some time on this and I can't figure it out so I'm going to post my program.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NUM_STUDENTS 10
#define NUM_TUD_STUDENTS 30

// Structure template
typedef struct student_record
{
    char name[48];
    int ID;
    int age;
    float height;
    float weight;
}Record;

// Function Prototypes
void combine_lists(Record[], Record[], Record[], Record[]);
void merge_sort(Record[], int, int);
void merge(Record[], int, int, int);

int main()
{
    int low = 0, high = NUM_TUD_STUDENTS;
    int i;

    // Struct arrays. TUD, DIT, ITT and ITB are acronyms for college names.
    Record TUD[NUM_TUD_STUDENTS], DIT[NUM_STUDENTS],
    ITT[NUM_STUDENTS], ITB[NUM_STUDENTS];

    // File pointers
    FILE *fp1, *fp2, *fp3;

    // Open the files for reading
    fp1 = fopen("DIT_Student_List.txt", "r");
    fp2 = fopen("ITT_Student_List.txt", "r");
    fp3 = fopen("ITB_Student_List.txt", "r");

    // Check for error
    if(fp1 == NULL || fp2 == NULL || fp3 == NULL)
    {
        printf("Error opening files.\n");
    }
    else
    {
        // Read in the first list of students
        for(i = 0; i < NUM_STUDENTS; i++)
        {
            fscanf(fp1, "%s %d %d %f %f", DIT[i].name, &DIT[i].ID, &DIT[i].age,
                   &DIT[i].height, &DIT[i].weight);
        }

        // Read in the second list of students
        for(i = 0; i < NUM_STUDENTS; i++)
        {
            fscanf(fp2, "%s %d %d %f %f", ITT[i].name, &ITT[i].ID, &ITT[i].age,
                   &ITT[i].height, &ITT[i].weight);
        }

        // Read in the third list of students
        for(i = 0; i < NUM_STUDENTS; i++)
        {
            fscanf(fp3, "%s %d %d %f %f", ITB[i].name, &ITB[i].ID, &ITB[i].age,
                   &ITB[i].height, &ITB[i].weight);
        }

        // Call the function to combine the three lists
        combine_lists(TUD, DIT, ITT, ITB);

        // Sorting function
        merge_sort(TUD, low, high);

        // Display list of students after sorting
        for(i = 0; i < NUM_TUD_STUDENTS; i++)
        {
            fprintf(stdout, "%s\n %d\n %d\n %f\n %f\n", TUD[i].name, TUD[i].ID,
                TUD[i].age, TUD[i].height, TUD[i].weight);
        }
    }

    // Close the pointers
    fclose(fp1);
    fclose(fp2);
    fclose(fp3);

    return 0;
}// end main()

void combine_lists(Record tud[], Record dit[], Record itt[], Record itb[])
{
    int i = 0;

    // Combines all three lists into one list
    for(i = 0; i < 30; i++)
    {
        if(i < 10)
        {
            strcpy(tud[i].name, dit[i].name);
            tud[i].ID = dit[i].ID;
            tud[i].age = dit[i].age;
            tud[i].height = dit[i].height;
            tud[i].weight = dit[i].weight;
        }

        if(i > 9 && i < 20)
        {
            strcpy(tud[i].name, itt[i - 10].name);
            tud[i].ID = itt[i - 10].ID;
            tud[i].age = itt[i - 10].age;
            tud[i].height = itt[i - 10].height;
            tud[i].weight = itt[i - 10].weight;
        }

        if(i > 19)
        {
            strcpy(tud[i].name, itb[i - 20].name);
            tud[i].ID = itb[i - 20].ID;
            tud[i].age = itb[i - 20].age;
            tud[i].height = itb[i - 20].height;
            tud[i].weight = itb[i - 20].weight;
        }
    }
}// end combine_lists()

void merge_sort(Record a[], int low, int high)
{
    int mid = 0;

    if(low == high)
    {
        return;
    }
    else
    {
        mid = (low + high) / 2;

        merge_sort(a, low, mid);

        merge_sort(a, mid + 1, high);

        merge(a, low, mid, high);
    }
}// end merge_sort()

void merge(Record a[], int low, int mid, int high)
{
    int i;
    int left_index = low;
    int right_index = mid + 1;
    int combined_index = low;

    /*
        There is a problem here. When I set tempA to 30, the size of the combined struct arrays,
        the program crashes. However, setting it to a higher value stops that from happening.
        I don't see that as a reasonable solution however, as I don't know the cause of the crashes.
    */
    Record tempA[31];

    while(left_index <= mid && right_index <= high)
    {
        // When trying to sort by age, it sorts by ID and vice versa.
        if(a[left_index].age <= a[right_index].age)
        {
            tempA[combined_index++] = a[left_index++];
        }
        else
        {
            tempA[combined_index++] = a[right_index++];
        }
    }

    if(left_index == mid + 1)
    {
        while(right_index <= high)
        {
            tempA[combined_index++] = a[right_index++];
        }
    }
    else
    {
        while(left_index <= mid)
        {
            tempA[combined_index++] = a[left_index++];
        }
    }

    for(i = low; i <= high; i++)
    {
        a[i] = tempA[i];
    }
}// end merge() 

As I said in my post above, the problem is that, while the list is sorted, it is sorted by the wrong criteria and I cannot figure out why.

If you are going to help me with this, I would kindly ask you to please not give full working solutions and instead just point me in the right direction, as this is for an assignment and the last thing I want is to be accused of plagiarism!

Thank you.

[fg109]

You're probably reading the data in wrong. Check to see if they're really in this order:

name
ID
age
height
weight

Bogeyman wrote:

    /*
        There is a problem here. When I set tempA to 30, the size of the combined struct arrays,
        the program crashes. However, setting it to a higher value stops that from happening.
        I don't see that as a reasonable solution however, as I don't know the cause of the crashes.
    */
    Record tempA[31];

You are probably calling the function merge_sort incorrectly. The parameter high should be the index of the last element in your combined array, in this case 29.

[Bogeyman]

Yep, that's what the problem was, thanks. They were in the wrong order in the files I was reading in from.

I tried to sort by name instead of age, but that has no effect. Any idea why?

[fg109]

C strings do not use comparison operators.

http://www.cplusplus.com/reference/cstring/strcmp/

[Bogeyman]

@fg109
Thanks, I used strcmp() and got it to work. You've given me a lot of help so far and i'm very grateful for that, but if you don't mind, there's just one last thing I need help with.

The final thing I need to do with this program is to adjust the sorting algorithm by adding another sorting algorithm to it or by adding a searching part to it. I don't know which one would be easier to implement, but that's the one I'd like some help with. Which would you recommend?

[fg109]

I do not understand your question. What do you mean exactly by "adjust the sorting algorithm"? Searching and sorting are different things. Give examples of how your array should look before and after the function, and what the function should return, if anything.

[Bogeyman]

What do you mean exactly by "adjust the sorting algorithm"?

What I mean is to integrate another sorting algorithm, such as insertion sort, into the merge sort algorithm, possibly to make it more efficient, though efficiency isn't the main point.

The array holds the student's information, such as name, age, and ID. The information is displayed by name in ascending order once sorted. The function doesn't return anything.

I have already succeeded in sorting the list as I wanted, thanks to your help. That's not the issue. In the assignment, we are required to adjust the algorithm we have used, by either integrating another sorting algorithm into it or by adding a searching part to it. The issue is that I don't know how to do that.

[fg109]

If you meant using two algorithms at once to do the sorting, you can look into block sort:

http://en.wikipedia.org/wiki/Block_sort

It's supposed to use elements of merge sort and insertion sort, but even the pseudo code is so long that I haven't read through it.

If you meant using two different sorting algorithms in your sort function, one after the other, why would you do that? After running through the first algorithm, the array is already sorted, so there's no need to use a different algorithm to sort it.

If you meant having two sorting functions, one using merge sort and the other using insertion sort, then just do it. You said that you didn't want anyone to provide you "full working solutions" so you're not asking me to provide code. If you're looking for a description of other sorting algorithms:

http://en.wikipedia.org/wiki/Sorting_algorithm

If by integrating sort and search together you meant to do the search while sorting, then that would be pretty complicated, since you would need to keep track of the index of the element while you keep swapping values around during sorting.

It would be much easier to create a separate search function specifically to search your arrays. Binary search is very efficient but dependent on an array being already sorted, and you can call it at the end of your sorting function.

http://en.wikipedia.org/wiki/Binary_search_algorithm

[Bogeyman]

Thank you very much for the information. I think I'll go with adding search functionality after sorting the array, as that seems simplest to implement. I won't mark this as solved just yet, as I need to actually write the code and make sure it works first. I'll come back and let you know when I have it finished or if I need more help. Anyway, thanks for everything so far, it's much appreciated!