Assignment Chef icon Assignment Chef
All English tutorials

Programming lesson

Mastering Merge Sort in C: A Projector Angle Problem Tutorial

Learn merge sort in C by solving a real-world geometry problem: finding the largest safe projection angle in a circular theater. Step-by-step tutorial with code examples.

merge sort in C C programming tutorial sorting algorithms divide and conquer atan2 function floating point comparison dynamic memory allocation projector angle problem COP 3502C assignment 4 merge sort example C struct sorting qsort in C radian to degree circular array gap group pair sorting programming assignments help

Introduction

Merge sort is a fundamental divide-and-conquer algorithm that every C programmer must master. In this tutorial, we'll explore merge sort by tackling a practical problem inspired by a movie theater projector. You'll learn how to sort groups of people by their angular position, compute maximum safe projection angles, and output sorted pairs—all while writing efficient C code.

Understanding the Problem

Imagine a circular room with a projector at the center (0,0). Groups of people stand at various points, each with coordinates (x,y) and a group size. The projector emits a sector of light at a certain angle width. We need to find the largest possible angle such that no group is inside the projection. Additionally, we must list all pairs of groups that define the edges of that maximum angle projection.

This problem is perfect for practicing merge sort because we need to sort groups by their angle relative to the x-axis. Once sorted, we can scan through the sorted list to find the largest gap between consecutive angles (considering the circular nature).

Setting Up the Structures

First, define two structs: one for a group and one for a result pair.

typedef struct {
    int groupNumber;
    int size;
    double angle; // in radians
} Group;

typedef struct {
    int firstGroup;
    int secondGroup;
    double angle; // in degrees
} Result;

The Group struct holds the group's index, number of people, and its angle. The Result struct stores a pair of group indices and the angle between them. We'll dynamically allocate arrays for groups and results.

Calculating Angles with atan2

To convert (x,y) coordinates to an angle, use the atan2(y, x) function from math.h. It returns the angle in radians between -π and π. We'll normalize angles to [0, 2π) for easier sorting.

double getAngle(int x, int y) {
    double rad = atan2(y, x);
    if (rad < 0) rad += 2 * M_PI;
    return rad;
}

This ensures all angles are between 0 and 2π. The atan2 function is essential for handling all quadrants correctly.

Implementing Merge Sort

We'll write a merge sort function that sorts an array of Group structures by their angle. Merge sort is stable and has O(N log N) complexity, which is efficient for up to 500,000 groups.

void merge(Group arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    Group *L = malloc(n1 * sizeof(Group));
    Group *R = malloc(n2 * sizeof(Group));
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i].angle < R[j].angle) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    free(L);
    free(R);
}

void mergeSort(Group arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

This classic implementation uses dynamic memory for temporary arrays. In a production setting, you might optimize by pre-allocating a single temporary array, but this version is clear for learning.

Finding the Maximum Angle

After sorting, we have an array of groups in angular order. The maximum safe projection angle is the largest gap between consecutive groups (including the wrap-around from last to first). For each gap, compute the angle difference in degrees. If the gap is larger than the current maximum, update the max. Also, collect all pairs that achieve this max angle.

double maxAngle = 0.0;
int resultCount = 0;
Result *results = malloc(N * sizeof(Result)); // allocate enough space

for (int i = 0; i < N; i++) {
    int j = (i + 1) % N;
    double diff = groups[j].angle - groups[i].angle;
    if (j == 0) diff += 2 * M_PI; // wrap-around
    double degDiff = diff * 180.0 / M_PI;
    if (degDiff > maxAngle + 1e-9) {
        maxAngle = degDiff;
        resultCount = 0;
    }
    if (fabs(degDiff - maxAngle) < 1e-9) {
        int g1 = groups[i].groupNumber;
        int g2 = groups[j].groupNumber;
        if (g1 > g2) { int temp = g1; g1 = g2; g2 = temp; }
        results[resultCount].firstGroup = g1;
        results[resultCount].secondGroup = g2;
        results[resultCount].angle = maxAngle;
        resultCount++;
    }
}

We use a small epsilon (1e-9) for floating-point comparison. The pairs are stored with the smaller group number first.

Sorting the Result Pairs

Now we need to sort the result pairs according to the specification: first by first group, then by second group. We can use merge sort again or qsort from the standard library. Here's a comparison function for qsort:

int compareResults(const void *a, const void *b) {
    Result *r1 = (Result *)a;
    Result *r2 = (Result *)b;
    if (r1->firstGroup != r2->firstGroup)
        return r1->firstGroup - r2->firstGroup;
    return r1->secondGroup - r2->secondGroup;
}

Then call qsort(results, resultCount, sizeof(Result), compareResults);.

Outputting the Results

Finally, print the maximum angle rounded to 4 decimal places, then each pair on its own line.

printf("%.4f\n", maxAngle);
for (int i = 0; i < resultCount; i++) {
    printf("%d %d\n", results[i].firstGroup, results[i].secondGroup);
}

Handling Edge Cases

If the maximum angle is very close to 360 degrees, the gap might be the complement of a small angle. Our loop already handles this by checking the wrap-around gap. Also, note that the initial projection angle A is given but we are to find the maximum possible angle regardless of A. The problem states we can change the default setting, so we ignore A in the calculation.

Complete Code Structure

Here's the skeleton of the main function:

int main() {
    int N, A;
    scanf("%d %d", &N, &A);
    Group *groups = malloc(N * sizeof(Group));
    for (int i = 0; i < N; i++) {
        int x, y, s;
        scanf("%d %d %d", &x, &y, &s);
        groups[i].groupNumber = i;
        groups[i].size = s;
        groups[i].angle = getAngle(x, y);
    }
    mergeSort(groups, 0, N-1);
    // ... find max angle and collect pairs ...
    qsort(results, resultCount, sizeof(Result), compareResults);
    // print output
    free(groups);
    free(results);
    return 0;
}

Time Complexity Analysis

Merge sort runs in O(N log N). The subsequent linear scan is O(N). Sorting the result pairs is O(P log P) where P is the number of pairs (at most N). Overall, the algorithm is efficient for N up to 500,000.

Real-World Analogy: Sorting Playlist by Popularity

Just like you might sort a music playlist by number of streams using merge sort, here we sort groups by angle. Imagine you're a DJ at a circular festival: you want to rotate the stage so that the maximum number of people can see without being blinded by the spotlight. Merge sort helps you order the crowd positions quickly.

Common Pitfalls

  • Floating-point precision: Always use an epsilon when comparing angles.
  • Wrap-around: Don't forget to compare the last and first group.
  • Memory leaks: Free all dynamically allocated memory.
  • Sorting pairs: Ensure pairs are sorted by first then second group number.

Conclusion

By working through this projector angle problem, you've practiced merge sort, dynamic memory allocation, and floating-point comparisons in C. These skills are essential for coding interviews and systems programming. Now you can confidently tackle any sorting challenge!