2025 CSCI2100E Lab Session #1

Time Limit: 500ms
Memory Limit: 256mb

Description:
Given an integer array A, which may contain positive numbers, negative numbers, and zeros, you are required to perform the following operations:
1. Move all negative numbers to the front of the array and all non-negative numbers (positive numbers and zeros) to the back.
2. After the rearrangement, sort the negative part of the array in ascending order and the non-negative part in descending order.
The relative order of elements within the negative part and within the non-negative part should remain unchanged.

Input Format:
• The first line contains an integer n, representing the length of the array.
• The second line contains n integers, representing the elements of array A.
Output Format:
• Print the array after the operations, with each element separated by a space.

Sample Input1: 
6
3 -1 -4 2 0 -2
Sample Output1: 
-4 -2 -1 3 2 0

Sample Input2:
6
0 1 -1 -2 3 4   
Sample Output2: 
-2 -1 4 3 1 0


Code Template:
#include <stdio.h>

void Print(int A[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", A[i]);
    }
    printf("\n");
}

void rearrangeAndSort(int A[], int n) {
    int negCount = 0; // Count of negative numbers
    int nonNegCount = 0; // Count of non-negative numbers

    // Hint1: Separate negative and non-negative numbers
    // Implement your code here


    // Create temporary arrays for negative and non-negative numbers
    int negArray[negCount];
    int nonNegArray[nonNegCount];

    int negIndex = 0;
    int nonNegIndex = 0;


    // Hint2: Populate the temporary arrays
    // Implement your code here

    
    // Hint3: Sort the negative part in ascending order
    // Implement your code here


    // Hint4: Sort the non-negative part in descending order
    // Implement your code here


    // Hint5: Merge the sorted parts back into the original array
    // Implement your code here


}

int main() {
    int A[1000001];
    int n;

    // Input array length and elements
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }

    // Call the function
    rearrangeAndSort(A, n);

    // Output the result
    Print(A, n);

    return 0;
}