1

I have an array of struct of 

typedef struct BinaryTreeNode {
    BSTElementType userID;
    BSTElementType count;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
}BinaryTreeNode;

typedef BinaryTreeNode BSTNode;

And I wish to merge sort the array in ascending order. However, when I execute the merge, nothing changes. This is the code I used to create the array of struct, and the function call of the MergeSort. The maxUsers is an int I got from converting the number of nodes from a binary tree, which should be the max amount of the array.

BSTNode *arr = (BSTNode *)malloc(maxUsers * sizeof(BSTNode));

MergeSort(arr, 0, maxUsers);

void Merge(BSTNode *arr, int low, int mid, int high) {
    int mergedSize = high - low + 1;
    BSTNode *temp = (BSTNode *)malloc(mergedSize * sizeof(BSTNode));
    int mergePos = 0;
    int leftPos = 0;
    int rightPos = 0;

    leftPos = low;
    rightPos = mid + 1;

    //printf("Starting Merge\n");

    while (leftPos <= high && rightPos <= mid) {
        if (arr[leftPos].count < arr[rightPos].count) {
            temp[mergePos].userID = arr[leftPos].userID;
            temp[mergePos].count = arr[leftPos].count;
            ++leftPos;
        }
        else {
            temp[mergePos].userID = arr[rightPos].userID;
            temp[mergePos].count = arr[rightPos].count;
            ++rightPos;
        }
        ++mergePos;
    }

    while (leftPos <= mid) {
        temp[mergePos].userID = arr[leftPos].userID;
        temp[mergePos].count = arr[leftPos].count;
        ++leftPos;
        ++mergePos;
    }

    while (rightPos <= high) {
        temp[mergePos].userID = arr[rightPos].userID;
        temp[mergePos].count = arr[rightPos].count;
        ++rightPos;
        ++mergePos;
    }

    for (mergePos = 0; mergePos < mergedSize; ++mergePos) {
        arr[low + mergePos].userID = temp[mergePos].userID;
        arr[low + mergePos].count = temp[mergePos].count;
    }
}

void MergeSort(BSTNode *arr, int low, int high) {
    int mid = 0;

    if (low < high) {
        mid = (low + high) / 2;

        MergeSort(arr, low, mid);
        MergeSort(arr, mid + 1, high);

        Merge(arr, low, mid, high);
    }
}

Any tips or hints will be much appreciated!

Edit: When I tried to write some printf statements, I noticed that the values are coming out as negatives. But the values that are stored in the structs are positives. Any reason for this error?

printf("Left Pos: %d, Right Pos: %d\n", leftPos, rightPos);
    while (leftPos <= mid && rightPos <= high) {
        printf("Left Pos count: %d, Right Pos count: %d\n", arr[leftPos].count, arr[rightPos].count);
        if (arr[leftPos].count < arr[rightPos].count) {
            temp[mergePos].userID = arr[leftPos].userID;
            temp[mergePos].count = arr[leftPos].count;
            ++leftPos;
        }
Improve this question
5
  • Any reason you typedef the typedef? Why not use the shorter name on the first typedef if you want that (the longer name is fine, though)? Don't obfuscate your code. Commented Sep 16, 2016 at 6:43
  • @Olaf This is for an assignment that required to typedef it. Commented Sep 16, 2016 at 13:19
  • I did not tell not to typedef it! Read my comment carefully again. Commented Sep 16, 2016 at 13:44
  • 1) MergeSort(arr, 0, maxUsers); --> MergeSort(arr, 0, maxUsers-1); Commented Sep 16, 2016 at 15:40
  • 2) while (leftPos <= high && rightPos <= mid) { --> while (leftPos <= mid && rightPos <= high) { Commented Sep 16, 2016 at 15:43

1 Answer 1

Reset to default
1

There are two crucial changes that need to be made:

  1. In Merge, you have while (leftPos <= high && rightPos <= mid) but you need while (leftPos <= mid && rightPos <= high) (reversing the left/right comparison values).

  2. In main() — or, at least, the code that calls MergeSort(), you have MergeSort(arr, 0, maxUsers); but you need MergeSort(arr, 0, maxUsers-1); because the values passed must be such that arr[lo] and arr[hi] are both valid entries in the array, and when you pass maxUsers you are telling it that arr[maxUsers] is valid when it isn't.

A third important change is to add free(temp) before exiting MergeSort().

I also elected to replace your multiline assignments with simple one-line structure assignments.

Here's a debug laden version of the code, but the debug printing is all commented out. It was all active when I resolved the problem. While I was debugging, even though I was using rand() to generate the data, I didn't use srand() quite deliberately so that I was working with the same data on each run. When I was confident that the code was clean, then I used the srand(time(0)); and varied the size of the array, but while debugging, stability was important.

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

typedef int BSTElementType;

typedef struct BinaryTreeNode
{
    BSTElementType userID;
    BSTElementType count;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
} BinaryTreeNode;

typedef BinaryTreeNode BSTNode;

static void PrintArray(const char *tag, int n, BSTNode *array)
{
    printf("%s:\n", tag);
    for (int i = 0; i < n; i++)
        printf("%2d: u = %4d, c = %2d\n", i, array[i].userID, array[i].count);
    putchar('\n');
    fflush(stdout);
}

static
void Merge(BSTNode *arr, int low, int mid, int high)
{
    int mergedSize = high - low + 1;
    BSTNode *temp = (BSTNode *)malloc(mergedSize * sizeof(BSTNode));
    int mergePos = 0;
    int leftPos = low;
    int rightPos = mid + 1;

    //printf("-->> %s: lo = %d, md = %d, hi = %d, sz = %d\n", __func__, low, mid, high, mergedSize);

    //printf("L = %d, M = %d; R = %d, H = %d\n", leftPos, mid, rightPos, high);
    while (leftPos <= mid && rightPos <= high)      // Key change
    {
        //printf("a[%d].c = %d <=> a[%d].c = %d\n", leftPos, arr[leftPos].count,
        //       rightPos, arr[rightPos].count);
        if (arr[leftPos].count < arr[rightPos].count)
        {
            //printf("L1: a[%d].c = %d\n", leftPos, arr[leftPos].count);
            temp[mergePos++] = arr[leftPos++];
        }
        else
        {
            //printf("R1: a[%d].c = %d\n", rightPos, arr[rightPos].count);
            temp[mergePos++] = arr[rightPos++];
        }
        //printf("L = %d, M = %d; R = %d, H = %d\n", leftPos, mid, rightPos, high);
    }

    while (leftPos <= mid)
    {
        //printf("L2: a[%d].c = %d\n", leftPos, arr[leftPos].count);
        temp[mergePos++] = arr[leftPos++];
    }

    while (rightPos <= high)
    {
        //printf("R2: a[%d].c = %d\n", rightPos, arr[rightPos].count);
        temp[mergePos++] = arr[rightPos++];
    }

    assert(mergePos == mergedSize);

    //PrintArray("merged", mergedSize, temp);

    for (mergePos = 0; mergePos < mergedSize; ++mergePos)
        arr[low + mergePos] = temp[mergePos];

    free(temp);         // Key change
    //printf("<<-- %s: lo = %d, md = %d, hi = %d, sz = %d\n", __func__, low, mid, high, mergedSize);
}

static
void MergeSort(BSTNode *arr, int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2;
        //printf("-->> %s: lo = %d, md = %d, hi = %d\n", __func__, low, mid, high);

        MergeSort(arr, low, mid);
        MergeSort(arr, mid + 1, high);

        Merge(arr, low, mid, high);
        //printf("<<-- %s: lo = %d, md = %d, hi = %d\n", __func__, low, mid, high);
    }
}

int main(void)
{
    /* Unstable when testing */
    //srand(time(0));
    //int maxUsers = rand() % 20 + 5;
    /* Stable while debugging */
    int maxUsers = 10;

    BSTNode *arr = (BSTNode *)malloc(maxUsers * sizeof(BSTNode));

    for (int i = 0; i < maxUsers; i++)
    {
        arr[i].userID = rand() % 100 * 100;
        arr[i].count = rand() % 10;
        arr[i].left = 0;
        arr[i].right = 0;
    }

    PrintArray("Before", maxUsers, arr);
    MergeSort(arr, 0, maxUsers - 1);        // Key change
    PrintArray("After", maxUsers, arr);

    free(arr);

    return 0;
}

One of the key debugging observations was that the main loop in Merge() was never entered; that was a strong hint for the first problem. Oddball data was a strong hint for the second problem. The main data is all nicely controlled in range.

Sample output (YMMV because you may not be using the exact same PRNG):

Before:
 0: u = 7900, c =  9
 1: u = 3900, c =  5
 2: u = 5500, c =  3
 3: u = 4300, c =  4
 4: u = 3600, c =  6
 5: u =  900, c =  2
 6: u = 5300, c =  9
 7: u = 6300, c =  1
 8: u = 7900, c =  8
 9: u = 4400, c =  3
10: u = 9400, c =  0

After:
 0: u = 9400, c =  0
 1: u = 6300, c =  1
 2: u =  900, c =  2
 3: u = 4400, c =  3
 4: u = 5500, c =  3
 5: u = 4300, c =  4
 6: u = 3900, c =  5
 7: u = 3600, c =  6
 8: u = 7900, c =  8
 9: u = 5300, c =  9
10: u = 7900, c =  9

Sample run (random amounts of data):

Before:
 0: u = 3300, c =  1
 1: u =  200, c =  8
 2: u = 7500, c =  6
 3: u = 2700, c =  8
 4: u = 8300, c =  3
 5: u = 6900, c =  3
 6: u =  400, c =  3
 7: u = 1100, c =  6
 8: u = 3600, c =  5
 9: u = 2100, c =  7
10: u = 9400, c =  9
11: u = 7300, c =  0
12: u = 1800, c =  4
13: u = 8200, c =  9
14: u = 8400, c =  4
15: u = 9600, c =  0
16: u = 4400, c =  7
17: u = 2900, c =  0
18: u = 4300, c =  4
19: u = 6500, c =  9
20: u = 6800, c =  6
21: u = 8000, c =  2
22: u = 6000, c =  5

After:
 0: u = 2900, c =  0
 1: u = 9600, c =  0
 2: u = 7300, c =  0
 3: u = 3300, c =  1
 4: u = 8000, c =  2
 5: u =  400, c =  3
 6: u = 6900, c =  3
 7: u = 8300, c =  3
 8: u = 4300, c =  4
 9: u = 8400, c =  4
10: u = 1800, c =  4
11: u = 6000, c =  5
12: u = 3600, c =  5
13: u = 6800, c =  6
14: u = 1100, c =  6
15: u = 7500, c =  6
16: u = 4400, c =  7
17: u = 2100, c =  7
18: u = 2700, c =  8
19: u =  200, c =  8
20: u = 6500, c =  9
21: u = 8200, c =  9
22: u = 9400, c =  9

Debug-enabled, fixed-size run:

Before:
 0: u =  700, c =  9
 1: u = 7300, c =  8
 2: u = 3000, c =  2
 3: u = 4400, c =  8
 4: u = 2300, c =  9
 5: u = 4000, c =  5
 6: u = 9200, c =  2
 7: u = 8700, c =  3
 8: u = 2700, c =  9
 9: u = 4000, c =  2

-->> MergeSort: lo = 0, md = 4, hi = 9
-->> MergeSort: lo = 0, md = 2, hi = 4
-->> MergeSort: lo = 0, md = 1, hi = 2
-->> MergeSort: lo = 0, md = 0, hi = 1
-->> Merge: lo = 0, md = 0, hi = 1, sz = 2
L = 0, M = 0; R = 1, H = 1
a[0].c = 9 <=> a[1].c = 8
R1: a[1].c = 8
L = 0, M = 0; R = 2, H = 1
L2: a[0].c = 9
<<-- Merge: lo = 0, md = 0, hi = 1, sz = 2
<<-- MergeSort: lo = 0, md = 0, hi = 1
-->> Merge: lo = 0, md = 1, hi = 2, sz = 3
L = 0, M = 1; R = 2, H = 2
a[0].c = 8 <=> a[2].c = 2
R1: a[2].c = 2
L = 0, M = 1; R = 3, H = 2
L2: a[0].c = 8
L2: a[1].c = 9
<<-- Merge: lo = 0, md = 1, hi = 2, sz = 3
<<-- MergeSort: lo = 0, md = 1, hi = 2
-->> MergeSort: lo = 3, md = 3, hi = 4
-->> Merge: lo = 3, md = 3, hi = 4, sz = 2
L = 3, M = 3; R = 4, H = 4
a[3].c = 8 <=> a[4].c = 9
L1: a[3].c = 8
L = 4, M = 3; R = 4, H = 4
R2: a[4].c = 9
<<-- Merge: lo = 3, md = 3, hi = 4, sz = 2
<<-- MergeSort: lo = 3, md = 3, hi = 4
-->> Merge: lo = 0, md = 2, hi = 4, sz = 5
L = 0, M = 2; R = 3, H = 4
a[0].c = 2 <=> a[3].c = 8
L1: a[0].c = 2
L = 1, M = 2; R = 3, H = 4
a[1].c = 8 <=> a[3].c = 8
R1: a[3].c = 8
L = 1, M = 2; R = 4, H = 4
a[1].c = 8 <=> a[4].c = 9
L1: a[1].c = 8
L = 2, M = 2; R = 4, H = 4
a[2].c = 9 <=> a[4].c = 9
R1: a[4].c = 9
L = 2, M = 2; R = 5, H = 4
L2: a[2].c = 9
<<-- Merge: lo = 0, md = 2, hi = 4, sz = 5
<<-- MergeSort: lo = 0, md = 2, hi = 4
-->> MergeSort: lo = 5, md = 7, hi = 9
-->> MergeSort: lo = 5, md = 6, hi = 7
-->> MergeSort: lo = 5, md = 5, hi = 6
-->> Merge: lo = 5, md = 5, hi = 6, sz = 2
L = 5, M = 5; R = 6, H = 6
a[5].c = 5 <=> a[6].c = 2
R1: a[6].c = 2
L = 5, M = 5; R = 7, H = 6
L2: a[5].c = 5
<<-- Merge: lo = 5, md = 5, hi = 6, sz = 2
<<-- MergeSort: lo = 5, md = 5, hi = 6
-->> Merge: lo = 5, md = 6, hi = 7, sz = 3
L = 5, M = 6; R = 7, H = 7
a[5].c = 2 <=> a[7].c = 3
L1: a[5].c = 2
L = 6, M = 6; R = 7, H = 7
a[6].c = 5 <=> a[7].c = 3
R1: a[7].c = 3
L = 6, M = 6; R = 8, H = 7
L2: a[6].c = 5
<<-- Merge: lo = 5, md = 6, hi = 7, sz = 3
<<-- MergeSort: lo = 5, md = 6, hi = 7
-->> MergeSort: lo = 8, md = 8, hi = 9
-->> Merge: lo = 8, md = 8, hi = 9, sz = 2
L = 8, M = 8; R = 9, H = 9
a[8].c = 9 <=> a[9].c = 2
R1: a[9].c = 2
L = 8, M = 8; R = 10, H = 9
L2: a[8].c = 9
<<-- Merge: lo = 8, md = 8, hi = 9, sz = 2
<<-- MergeSort: lo = 8, md = 8, hi = 9
-->> Merge: lo = 5, md = 7, hi = 9, sz = 5
L = 5, M = 7; R = 8, H = 9
a[5].c = 2 <=> a[8].c = 2
R1: a[8].c = 2
L = 5, M = 7; R = 9, H = 9
a[5].c = 2 <=> a[9].c = 9
L1: a[5].c = 2
L = 6, M = 7; R = 9, H = 9
a[6].c = 3 <=> a[9].c = 9
L1: a[6].c = 3
L = 7, M = 7; R = 9, H = 9
a[7].c = 5 <=> a[9].c = 9
L1: a[7].c = 5
L = 8, M = 7; R = 9, H = 9
R2: a[9].c = 9
<<-- Merge: lo = 5, md = 7, hi = 9, sz = 5
<<-- MergeSort: lo = 5, md = 7, hi = 9
-->> Merge: lo = 0, md = 4, hi = 9, sz = 10
L = 0, M = 4; R = 5, H = 9
a[0].c = 2 <=> a[5].c = 2
R1: a[5].c = 2
L = 0, M = 4; R = 6, H = 9
a[0].c = 2 <=> a[6].c = 2
R1: a[6].c = 2
L = 0, M = 4; R = 7, H = 9
a[0].c = 2 <=> a[7].c = 3
L1: a[0].c = 2
L = 1, M = 4; R = 7, H = 9
a[1].c = 8 <=> a[7].c = 3
R1: a[7].c = 3
L = 1, M = 4; R = 8, H = 9
a[1].c = 8 <=> a[8].c = 5
R1: a[8].c = 5
L = 1, M = 4; R = 9, H = 9
a[1].c = 8 <=> a[9].c = 9
L1: a[1].c = 8
L = 2, M = 4; R = 9, H = 9
a[2].c = 8 <=> a[9].c = 9
L1: a[2].c = 8
L = 3, M = 4; R = 9, H = 9
a[3].c = 9 <=> a[9].c = 9
R1: a[9].c = 9
L = 3, M = 4; R = 10, H = 9
L2: a[3].c = 9
L2: a[4].c = 9
<<-- Merge: lo = 0, md = 4, hi = 9, sz = 10
<<-- MergeSort: lo = 0, md = 4, hi = 9
After:
 0: u = 4000, c =  2
 1: u = 9200, c =  2
 2: u = 3000, c =  2
 3: u = 8700, c =  3
 4: u = 4000, c =  5
 5: u = 4400, c =  8
 6: u = 7300, c =  8
 7: u = 2700, c =  9
 8: u = 2300, c =  9
 9: u =  700, c =  9

The code compiles and runs cleanly under GCC 6.1.0 and Valgrind 3.12-SVN on Mac OS X 10.11.6.

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

1 Comment

Thanks for this. I also noticed that I switched the low and high in the while loop.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.