"Order From Chaos" Practice Problem - Keeps segfaulting

Hi all, I've been working on a practice problem (not homework) involving the merge sort algorithm. I keep getting a segfault when I run my code.

Here are the instructions:
*Please note I'm really just trying to get mergeSort() to sort the numbers without fault right now.

Order from Chaos
Filename: order.c


Your math teacher, Mr. Conway, has a bad habit of writing the problem numbers for your class’ homework assignments in a random order. Additionally, sometimes he won’t realize that he has written down a problem number already and will end up writing the same number multiple times! This makes the task of doing your homework much harder. If you decide to solve them in order, you need to spend several minutes sorting them before you begin. On the other hand, if you work through the problems in the order that Mr. Conway wrote them, you may end up solving the same problem twice.


To deal with this predicament, you decide to write a program that prints out the list of problems the way that a logical math teacher would write them. Since you would like the reorganized list to be as neat as possible, you set the following constraints:
•
•
•
•
In the new list, the numbers should be printed in order from lowest to highest.


There should be no duplicates.

Any two or more consecutive problem numbers should be condensed into a single segment, represented by a starting number, followed by a hyphen and an ending number.
For example, “7, 8, 9” would condense down to “7-9”.

The numbers should be condensed into as few segments as possible.

Different problems or ranges should be separated with a comma and a space. For example, given these rules, the problem numbers “2, 7, 1, 4, 1, 6, 8” should be condensed down to “1-2, 4, 6-8”.

The Problem:
Help make your life easier by reorganizing Mr. Conway’s homework assignment.

The Input:
The first line will contain a single, positive integer, d, representing the number of days of homework. For each day, there will be two lines. The first line will contain a single integer, p (1 ≤ p ≤ 10 5 ), representing the number of problems written by Mr. Conway on the board. The next line will contain p integers, n i (1 ≤ n i ≤ 10 5 ), representing the assigned problems.

The Output:
For each day, output a single line, starting with “Day #s: ” where s is the day number in the input (starting with 1). On the same line, output the condensed version of the problems, following the above constraints. Separate different problems or ranges within each day with a comma and a space.
Output a blank line after each day.

Sample Input:
4
7
2 7 1 4 1 6 8
2
6 8
10
2 7 8 14 2 10 15 1 3 2
5
1 2 3 4 5


Sample Output:
Day #1: 1-2, 4, 6-8
Day #2: 6, 8
Day #3: 1-3, 7-8, 10, 14-15
Day #4: 1-5

My code is attached below. I am wondering do all of the recursive calls happen before it moves on to the while loop? I'm confused about what happens when I think.

Thanks!

You have some major misunderstandings. You don't need a megabyte character array to read a single integer from 1 to 100000. I'm also assuming that you don't need to read a filename from the command line as that is unusual for these kinds of problems. Here's how your main should look.

Code:

---

#include <stdio.h>
#include <stdlib.h>
 
int cmp_int(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}
 
int main() {
    int days;
    scanf("%d", &days);
 
    while (days-- > 0) {
 
        int num_problems;
        scanf("%d", &num_problems);
 
        int *problems = malloc(num_problems * sizeof *problems);
        for (int i = 0; i < num_problems; i++)
            scanf("%d", &problems[i]);
 
        // You can sort the array with qsort (prototyped in stdlib.h)
        qsort(problems, num_problems, sizeof *problems, cmp_int);
 
        // ...
 
        free(problems);
    }
 
    return 0;
}

---

Note that saying "sizeof *problems" is the same as saying "sizeof(int)" in this case, since the type of *problems (problems dereferenced) is int.

Thank you for your response. I do have some major misunderstandings, I am still learning.

I used 100000 because it was a static array and the instructions said the number of problems could range from 1 to 10^5. Maybe that wasn't the best way, but that was my logic.

I know it doesn't have to read from a file, but I think it would be really good practice to figure out how to do that.

I also didn't know qsort() existed so thank you for that. I do need to know how to code merge sort for an upcoming class in the spring though so it would be nice to know what is going wrong.

I do appreciate your response because if I ever decide to compete where there is a time limit, this new information will be great to have in the back of my mind. Thank you!

Quote:

---

Originally Posted by checrisp

I do have some major misunderstandings, I am still learning.

---

Well duh.

Quote:

---

Originally Posted by checrisp

I used 100000 because it was a static array and the instructions said the number of problems could range from 1 to 10^5. Maybe that wasn't the best way, but that was my logic.

---

I don't understand your logic.
Why is it 1000000 instead of 100000?
Why are you only reading one number into it?
Why is it a char array instead of an int array?
If you were going to use that "static" array to hold the numbers then what is problems_array for? (And why is it char instead of int?)
I don't understand any of it, so I really can't help.

Why is it 1000000 instead of 100000?
I accidentally put an extra 0.

Why are you only reading one number into it?
The instructions say "The first line will contain a single integer, p(1 <= p <= 10^5), representing the number of problems written by Mr. Conway on the board." I was allowing for the possibility that Mr. Conway would assign 100,000 problems to be sorted.

Why is it a char array instead of an int array?
When I started, I did use an int array and it didn't work. I'm not totally sure why. The character array played nicer with fgets(). Maybe because of the spaces between the numbers? I basically grabbed it as a string with fgets() and converted it into an integer numerical representation with atoi().


If you were going to use that "static" array to hold the numbers then what is problems_array for? (And why is it char instead of int?)
num_problems is a way to see how many problems are assigned so I can pass that information on to mergeSort(). The problems_array is an array of characters to be sorted. I could have dynamically allocated space for num_problems, but I didn't feel like it. And since it stated 1 to 10^5, I figured it would be okay not to.