CODEWITHSUNDEEP
calgorithmmergesort
Koko
Koko

Reputation: 57

Mergesort in C and I keep getting errors. Is my approach correct?

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

// PURPOSE:
const int LINE_LEN = 256;

#define STOP_CMD "quit"

const int STOP_CMD_LEN = sizeof(STOP_CMD) - 1;

// PURPOSE: To hold a node in a linked list of integers.
struct Node {
    int value_;
    struct Node *nextPtr_;
};

// PURPOSE: To create and return a linked list of integer pairs.
struct Node *makeList() {
    struct Node *list = NULL;
    struct Node *end = NULL;
    struct Node *next;
    int value;
    char line[LINE_LEN];

    while (1) {
        printf("Integer (or %s) to quit: ", STOP_CMD);
        fgets(line, LINE_LEN, stdin);

        if (strncmp(line, STOP_CMD, STOP_CMD_LEN) == 0)
            break;

        value = strtol(line,NULL,10);
        next = (struct Node *)malloc(sizeof(struct Node));

        if (list == NULL) {
            list = next;
        } else {
            end->nextPtr_ = next;
        }

        end = next;
        next->value_ = value;
        next->nextPtr_ = NULL;
    }

    return (list);
}

// PURPOSE: To print the 'value_' values found in 'list'. No return value.
void print(const struct Node *list) {
    const struct Node *run;

    for (run = list; run != NULL; run = run->nextPtr_)
        printf("%d\n", run->value_);
}

// PURPOSE: To sort the items in 'list' in ascending order according to
// their value for 'value_'. Returns sorted list.
struct Node *sort(struct Node *list) {
    // Merge-sort is recursive, so there is/are base case(s):
    // For merge-sort, the base cases are when 'list' has either 0 or 1
    // node it it. If 'list' points to either 0 or 1 thing then return 'list':

    // YOUR CODE HERE
    if (list == NULL || list->nextPtr_ == NULL) {
        return list;
    }

    // This is the beginning of the recursive case.
    // We have to split 'list' into two lists of approximately the same length.
    // A straight-forward way to do that is with loop and 3 pointer variables:
    // (*) 'full' races through the list starting at 'list' 2 nodes at a time.
    // The loop should stop when either 'full' lands on 'NULL', or the
    // next of 'full' is 'NULL'.
    // (*) 'half' starts at 'list' but goes through at 1/2 the speed by only
    // getting the next (not the next-next like 'full'). When 'full'
    // reaches the end then 'half' will point to the *beginning* of the
    // second list. We need this node, but we *also* need the one just
    // before 'half'. So that is why there is also . . .
    // (*) 'prevHalf', whose job is to take the value 'half' just had.
    // Just before advancing 'half' to its next, give 'prevHalf' the old
    // value of 'half'.

    struct Node *full;
    struct Node *half;
    struct Node *prevHalf = NULL;

    // YOUR CODE HERE
    full = list;
    half = list;
    while (full != NULL) {
        full = full->nextPtr_;
        if (full != NULL){
            prevHalf = half;
            half = half->nextPtr_;
        }
    }

    // Here we separate both sublists:

    prevHalf->nextPtr_ = NULL;

    // Here we recursively sort both sublists:

    struct Node *firstHalf = sort(list);
    struct Node *secondHalf = sort(half);
    struct Node *end = NULL;

    // Here we merge the lists pointed to by 'firstHalf' and 'secondHalf'.
    // Make 'list' point to the beginning of the combined list, and use 'end'
    // to keep track of the end.
    // Use a loop to while both 'firstHalf' and 'secondHalf' are both not yet
    // at the end of their lists, then compare the values that both point to.
    // If 'firstHalf' points to the lower value then put it at the end of the
    // combined list. Else put 'secondHalf' at the end.
    // You do not have to remove the node from the old list, but you *do* have
    // to advance which ever pointer you used (either 'firstHalf' or
    // 'secondHalf') to point to the next node in the list.
    // When either 'firstHalf' or 'secondHalf' are 'NULL' then quit the loop:

    list = NULL;

    // YOUR CODE HERE
    // if (firstHalf value_->secondHalf->value_) {
    if (firstHalf->value_ & secondHalf->value_) {
        list = firstHalf;
        end = firstHalf;
        firstHalf = firstHalf->nextPtr_;
    } else {
        list = secondHalf;
        end = secondHalf;
        secondHalf = secondHalf->nextPtr_;
    }
    while ((firstHalf != NULL) && (secondHalf != NULL)) {
        if (firstHalf->value_ & secondHalf->value_) {
            list->nextPtr_ = firstHalf;
            end->nextPtr_ = firstHalf;
            firstHalf = firstHalf->nextPtr_;
            end = end->nextPtr_;
        } else {
            list->nextPtr_ = secondHalf;
            end->nextPtr_ = secondHalf;
            secondHalf = secondHalf->nextPtr_;
            end = end->nextPtr_;
        }
    }

    // Almost finished!
    // You made it to the end of one list, but there still is the other one.
    // Make the node pointed to by 'end' point to which ever list that you did
    // *not* go all the way through.

    // YOUR CODE HERE
    while (firstHalf != NULL && secondHalf == NULL) {
        list->nextPtr_ = firstHalf;
        end->nextPtr_ = firstHalf;
        firstHalf = firstHalf->nextPtr_;
        end = end->nextPtr_;
    }
    while (firstHalf == NULL && secondHalf != NULL) {
        list->nextPtr_ = secondHalf;
        end->nextPtr_ = secondHalf;
        secondHalf = secondHalf->nextPtr_;
        end = end->nextPtr_;
    }
    return (list);
}

// PURPOSE: To do nothing if 'list' is NULL. Otherwise to 'free()' both
// 'nextPtr_' and 'namePtr_' for 'list', and all of 'nextPtr_' successors.
// No return value.
void release(struct Node *list) {
    if (list == NULL)
        return;

    release(list->nextPtr_);
    free(list);
}

// PURPOSE: To create, print, and 'free()' a linked list of the 'argc-1'
// items on 'argv[]', from 'argv[1]' to 'argv[argc-1]'. Returns
// 'EXIT_SUCCESS' to OS.
int main(int argc, char *argv[]) {
    // I.

    // II. :
    struct Node *list;

    list = makeList();

    printf("Before sort:\n");
    print(list);

    list = sort(list);

    printf("After sort:\n");
    print(list);
    release(list);

    // III. Finished:
    return (EXIT_SUCCESS);
}

The program asks the user for an input and then shows the user input before sorting it and displaying it The expected output should be

$ ./mergeSort 
Integer (or quit) to quit: 9
Integer (or quit) to quit: 8
Integer (or quit) to quit: 7
Integer (or quit) to quit: 1
Integer (or quit) to quit: 2
Integer (or quit) to quit: 3
Integer (or quit) to quit: 6
Integer (or quit) to quit: 4
Integer (or quit) to quit: 5
Integer (or quit) to quit: quit
Before sort:
9
8
7
1
2
3
6
4
5
After sort:
1
2
3
4
5
6
7
8
9

Will fixing these errors get the expected output? and if not, what can I do differently to generate the same output? I do not know if my approach is correct or not. Any help will be appreciated.

Now after fixing some errors. I get this

Integer (or quit) to quit: 1
Integer (or quit) to quit: 2
Integer (or quit) to quit: 3
Integer (or quit) to quit: 4
Integer (or quit) to quit: 5
Integer (or quit) to quit: 6
Integer (or quit) to quit: 7
Integer (or quit) to quit: 8
Integer (or quit) to quit: 9
Integer (or quit) to quit: quit
Before sort:
1
2
3
4
5
6
7
8
9
After sort:
8
9

Why isn't it sorting it all the input starting?

Upvotes: 1

Views: 69

Answers (1)

chqrlie
chqrlie

Reputation: 144695

There are some problems in your code:

  • in makelist() you should check the return value of fgets() to avoid an infinite loop upon unexpected end of file.

  • you should also check for malloc() failure to avoid undefined behavior.

  • your implementation of release() recurses as many levels as there are nodes in the list. Any sufficiently long list will cause a stack overflow. A non-recursive version is preferable.

  • the loop to split the list is incorrect: full does not skip twice as fast as half. You should modify this way:

      full = list;
  half = list;
  while (full != NULL) {
      full = full->nextPtr_;
      if (full != NULL) {
          prevHalf = half;
          half = half->nextPtr_;
          full = full->nextPtr_;
      }
  }

  • when comparing node values, you must use <= instead of &:

      if (firstHalf->value_ <= secondHalf->value_)

  • in the main merging loop, you should not modify list->nextPtr_, only end->nextPtr_.

  • the last merging loops are useless. You are supposed to just set end->nextPtr_ to leftHalf or rightHalf depending on which list is empty.

Here is a correct version:

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

// PURPOSE:
const int LINE_LEN = 256;

#define STOP_CMD "quit"

const int STOP_CMD_LEN = sizeof(STOP_CMD) - 1;

// PURPOSE: To hold a node in a linked list of integers.
struct Node {
    int value_;
    struct Node *nextPtr_;
};

// PURPOSE: To create and return a linked list of integer pairs.
struct Node *makeList(void) {
    struct Node *list = NULL;
    struct Node *end = NULL;
    struct Node *next;
    int value;
    char line[LINE_LEN];

    while (1) {
        printf("Integer (or %s) to quit: ", STOP_CMD);
        if (!fgets(line, LINE_LEN, stdin))
            break;

        if (strncmp(line, STOP_CMD, STOP_CMD_LEN) == 0)
            break;

        value = strtol(line, NULL, 10);
        next = (struct Node *)malloc(sizeof(struct Node));
        if (next == NULL) {
            fprintf(stderr, "out of memory\n");
            exit(EXIT_FAILURE);
        }
        next->value_ = value;
        next->nextPtr_ = NULL;
        if (list == NULL) {
            list = next;
        } else {
            end->nextPtr_ = next;
        }
        end = next;
    }
    return list;
}

// PURPOSE: To print the 'value_' values found in 'list'. No return value.
void print(const struct Node *list) {
    const struct Node *run;

    for (run = list; run != NULL; run = run->nextPtr_)
        printf("%d\n", run->value_);
}

// PURPOSE: To sort the items in 'list' in ascending order according to
// their value for 'value_'. Returns sorted list.
struct Node *sort(struct Node *list) {
    // Merge-sort is recursive, so there is/are base case(s):
    // For merge-sort, the base cases are when 'list' has either 0 or 1
    // node it it. If 'list' points to either 0 or 1 thing then return 'list':

    // YOUR CODE HERE
    if (list == NULL || list->nextPtr_ == NULL) {
        return list;
    }

    // This is the beginning of the recursive case.
    // We have to split 'list' into two lists of approximately the same length.
    // A straight-forward way to do that is with loop and 3 pointer variables:
    // (*) 'full' races through the list starting at 'list' 2 nodes at a time.
    // The loop should stop when either 'full' lands on 'NULL', or the
    // next of 'full' is 'NULL'.
    // (*) 'half' starts at 'list' but goes through at 1/2 the speed by only
    // getting the next (not the next-next like 'full'). When 'full'
    // reaches the end then 'half' will point to the *beginning* of the
    // second list. We need this node, but we *also* need the one just
    // before 'half'. So that is why there is also . . .
    // (*) 'prevHalf', whose job is to take the value 'half' just had.
    // Just before advancing 'half' to its next, give 'prevHalf' the old
    // value of 'half'.

    struct Node *full;
    struct Node *half;
    struct Node *prevHalf = list;

    // YOUR CODE HERE
    full = list;
    half = list;
    while (full != NULL) {
        full = full->nextPtr_;
        if (full != NULL) {
            prevHalf = half;
            half = half->nextPtr_;
            full = full->nextPtr_;
        }
    }

    // Here we separate both sublists:

    prevHalf->nextPtr_ = NULL;

    // Here we recursively sort both sublists:

    struct Node *firstHalf = sort(list);
    struct Node *secondHalf = sort(half);
    struct Node *end = NULL;

    // Here we merge the lists pointed to by 'firstHalf' and 'secondHalf'.
    // Make 'list' point to the beginning of the combined list, and use 'end'
    // to keep track of the end.
    // Use a loop to while both 'firstHalf' and 'secondHalf' are both not yet
    // at the end of their lists, then compare the values that both point to.
    // If 'firstHalf' points to the lower value then put it at the end of the
    // combined list. Else put 'secondHalf' at the end.
    // You do not have to remove the node from the old list, but you *do* have
    // to advance which ever pointer you used (either 'firstHalf' or
    // 'secondHalf') to point to the next node in the list.
    // When either 'firstHalf' or 'secondHalf' are 'NULL' then quit the loop:

    list = NULL;

    // YOUR CODE HERE
    if (firstHalf->value_ <= secondHalf->value_) {
        list = firstHalf;
        end = firstHalf;
        firstHalf = firstHalf->nextPtr_;
    } else {
        list = secondHalf;
        end = secondHalf;
        secondHalf = secondHalf->nextPtr_;
    }
    while ((firstHalf != NULL) && (secondHalf != NULL)) {
        if (firstHalf->value_ <= secondHalf->value_) {
            end->nextPtr_ = firstHalf;
            end = end->nextPtr_;
            firstHalf = firstHalf->nextPtr_;
        } else {
            end->nextPtr_ = secondHalf;
            end = end->nextPtr_;
            secondHalf = secondHalf->nextPtr_;
        }
    }

    // Almost finished!
    // You made it to the end of one list, but there still is the other one.
    // Make the node pointed to by 'end' point to which ever list that you did
    // *not* go all the way through.

    // YOUR CODE HERE
    if (firstHalf != NULL) {
        end->nextPtr_ = firstHalf;
    } else {
        end->nextPtr_ = secondHalf;
    }

    return list;
}

// PURPOSE: To do nothing if 'list' is NULL. Otherwise to 'free()' both
// 'nextPtr_' and 'namePtr_' for 'list', and all of 'nextPtr_' successors.
// No return value.
void release(struct Node *list) {
    while (list != NULL) {
        struct Node *next = list->nextPtr_;
        free(list);
        list = next;
    }
}

// PURPOSE: To create, print, and 'free()' a linked list of the 'argc-1'
// items on 'argv[]', from 'argv[1]' to 'argv[argc-1]'. Returns
// 'EXIT_SUCCESS' to OS.
int main(int argc, char *argv[]) {
    // I.

    // II. :
    struct Node *list;

    list = makeList();

    printf("Before sort:\n");
    print(list);

    list = sort(list);

    printf("After sort:\n");
    print(list);
    release(list);

    // III. Finished:
    return EXIT_SUCCESS;
}

Upvotes: 1

Related Questions