C Program For Even Odd Sorted Array

Sorting arrays is a fundamental operation in computer science with numerous applications. This article explores how to rearrange an array such that all even numbers precede all odd numbers, with consideration for maintaining their relative order.

In this article, you will learn various C programming techniques to efficiently sort an array into an even-odd separated sequence.

Problem Statement

Given an array of integers, the task is to reorder its elements such that all even numbers appear before all odd numbers. An additional consideration, depending on the requirement, is to preserve the relative order of even numbers among themselves, and odd numbers among themselves, from the original array. This problem often arises in data processing where specific categories of data need to be grouped for optimized access or sequential processing.

Example

Consider the input array: [12, 34, 45, 9, 8, 90, 3]

A desired output (where even numbers come first, then odd numbers, and their relative order within their respective groups is preserved) would be: [12, 34, 8, 90, 45, 9, 3]

Background & Knowledge Prerequisites

To effectively understand and implement the solutions discussed, readers should have a basic understanding of:

• C Language Basics: Variables, data types, conditional statements (if-else), loops (for, while).
• Arrays: Declaration, initialization, and accessing elements.
• Functions: Defining and calling functions, passing arrays to functions.
• Pointers: (For some advanced approaches like qsort) Understanding how pointers work with arrays.

Use Cases or Case Studies

Separating even and odd numbers in an array has practical applications beyond simple academic exercises:

• Data Partitioning: In large datasets, elements with specific properties (e.g., even IDs, odd IDs) might need to be processed separately or prioritized.
• Resource Allocation: In systems programming, certain resources (e.g., memory blocks, process IDs) might be categorized as "even" or "odd" for load balancing or sequential access.
• Game Development: Organizing game objects based on a property, such as separating player-controlled units (even ID) from AI-controlled units (odd ID) for rendering or logic updates.
• Database Optimization: When retrieving records, grouping results based on a numerical attribute's parity can sometimes optimize subsequent operations or display logic.
• Network Packet Processing: In network routers or firewalls, packets might be prioritized or routed differently based on an even/odd identifier in their header.

Solution Approaches

Here are a few common approaches to solve the even-odd array sorting problem, each with its own trade-offs regarding time complexity, space complexity, and whether it preserves the relative order of elements.

Approach 1: Using an Auxiliary Array (Stable)

This approach creates a temporary array and iterates through the original array twice. In the first pass, all even numbers are copied to the temporary array. In the second pass, all odd numbers are copied. Finally, the temporary array's content is copied back to the original array. This method preserves the relative order of both even and odd numbers.

• One-line summary: Copy even numbers, then odd numbers, into a new array, then copy back.

// Even-Odd Sort using Auxiliary Array
#include <stdio.h>
#include <stdlib.h> // For malloc and free

void evenOddSortAuxiliary(int arr[], int n) {
    // Step 1: Allocate memory for a temporary array
    int *temp_arr = (int *)malloc(n * sizeof(int));
    if (temp_arr == NULL) {
        printf("Memory allocation failed!\\n");
        return;
    }

    int k = 0; // Index for the temporary array

    // Step 2: Copy all even numbers to the temporary array
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 0) {
            temp_arr[k++] = arr[i];
        }
    }

    // Step 3: Copy all odd numbers to the temporary array
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 != 0) {
            temp_arr[k++] = arr[i];
        }
    }

    // Step 4: Copy elements back from temporary array to original array
    for (int i = 0; i < n; i++) {
        arr[i] = temp_arr[i];
    }

    // Step 5: Free the allocated memory
    free(temp_arr);
}

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

int main() {
    int arr[] = {12, 34, 45, 9, 8, 90, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    evenOddSortAuxiliary(arr, n);

    printf("Sorted array (Auxiliary Array): ");
    printArray(arr, n);

    int arr2[] = {7, 2, 10, 5, 1, 8, 4};
    n = sizeof(arr2) / sizeof(arr2[0]);

    printf("Original array: ");
    printArray(arr2, n);

    evenOddSortAuxiliary(arr2, n);

    printf("Sorted array (Auxiliary Array): ");
    printArray(arr2, n);

    return 0;
}

Run

• Sample Output:

  Original array: 12 34 45 9 8 90 3 
  Sorted array (Auxiliary Array): 12 34 8 90 45 9 3 
  Original array: 7 2 10 5 1 8 4 
  Sorted array (Auxiliary Array): 2 10 8 4 7 5 1

• Stepwise Explanation:

1. A new dynamic array temp_arr of the same size as the original array is allocated.
2. An index k is initialized to 0 to track the current position in temp_arr.
3. The first loop iterates through the arr. If an element arr[i] is even (i.e., arr[i] % 2 == 0), it is copied to temp_arr[k], and k is incremented.
4. The second loop also iterates through the arr. If an element arr[i] is odd (i.e., arr[i] % 2 != 0), it is copied to temp_arr[k], and k is incremented.
5. After both loops, temp_arr contains all even numbers followed by all odd numbers, preserving their original relative order.
6. Finally, the elements from temp_arr are copied back to the original arr.
7. The dynamically allocated memory for temp_arr is freed to prevent memory leaks.

Approach 2: Two-Pointer In-Place Partitioning (Unstable)

This approach uses two pointers, left starting from the beginning and right starting from the end of the array. The left pointer moves until it finds an odd number, and the right pointer moves until it finds an even number. Once both are found, the elements at left and right are swapped. This continues until left crosses right. This method is space-efficient but does *not* preserve the relative order of elements within the even or odd groups.

• One-line summary: Use two pointers from opposite ends, swapping odd numbers on the left with even numbers on the right.

// Even-Odd Sort using Two Pointers
#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void evenOddSortTwoPointers(int arr[], int n) {
    // Step 1: Initialize two pointers
    int left = 0;
    int right = n - 1;

    // Step 2: Iterate while left pointer is less than right pointer
    while (left < right) {
        // Step 3: Move left pointer while it points to an even number
        while (arr[left] % 2 == 0 && left < right) {
            left++;
        }

        // Step 4: Move right pointer while it points to an odd number
        while (arr[right] % 2 != 0 && left < right) {
            right--;
        }

        // Step 5: If left is still less than right, swap elements
        if (left < right) {
            swap(&arr[left], &arr[right]);
            left++;
            right--;
        }
    }
}

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

int main() {
    int arr[] = {12, 34, 45, 9, 8, 90, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    evenOddSortTwoPointers(arr, n);

    printf("Sorted array (Two Pointers): ");
    printArray(arr, n);

    int arr2[] = {7, 2, 10, 5, 1, 8, 4};
    n = sizeof(arr2) / sizeof(arr2[0]);

    printf("Original array: ");
    printArray(arr2, n);

    evenOddSortTwoPointers(arr2, n);

    printf("Sorted array (Two Pointers): ");
    printArray(arr2, n);

    return 0;
}

Run

• Sample Output:

  Original array: 12 34 45 9 8 90 3 
  Sorted array (Two Pointers): 12 34 8 90 9 45 3 
  Original array: 7 2 10 5 1 8 4 
  Sorted array (Two Pointers): 4 2 10 8 1 5 7

*Note the changed relative order in the output compared to the auxiliary array method.*

• Stepwise Explanation:

1. Two pointers, left and right, are initialized to the start and end of the array, respectively.
2. The while (left < right) loop continues until the pointers cross.
3. The inner while (arr[left] % 2 == 0 && left < right) loop increments left as long as it points to an even number.
4. The inner while (arr[right] % 2 != 0 && left < right) loop decrements right as long as it points to an odd number.
5. If left is still less than right (meaning arr[left] is an odd number and arr[right] is an even number), these two elements are swapped.
6. After a swap, both left and right pointers are moved one step inward.
7. This process partitions the array, placing all even numbers before odd numbers.

Approach 3: Using qsort with a Custom Comparator (Unstable)

C's standard library stdlib.h provides a generic sorting function qsort. We can leverage qsort by providing a custom comparison function that defines our sorting logic: even numbers come before odd numbers.

• One-line summary: Utilize qsort with a custom comparison function that prioritizes even numbers over odd numbers.

// Even-Odd Sort using qsort
#include <stdio.h>
#include <stdlib.h> // For qsort

// Comparison function for qsort
int compareEvenOdd(const void *a, const void *b) {
    int num1 = *(const int *)a;
    int num2 = *(const int *)b;

    // Prioritize even numbers over odd numbers
    if (num1 % 2 == 0 && num2 % 2 != 0) {
        return -1; // num1 (even) comes before num2 (odd)
    }
    if (num1 % 2 != 0 && num2 % 2 == 0) {
        return 1;  // num1 (odd) comes after num2 (even)
    }

    // If both are even or both are odd, their relative order is not strictly defined
    // by this comparison for stability. qsort might not preserve it.
    // For simple even/odd separation, 0 (equal) is sufficient here.
    return 0;
}

void evenOddSortQsort(int arr[], int n) {
    // Step 1: Call qsort with the custom comparison function
    qsort(arr, n, sizeof(int), compareEvenOdd);
}

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

int main() {
    int arr[] = {12, 34, 45, 9, 8, 90, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    evenOddSortQsort(arr, n);

    printf("Sorted array (qsort): ");
    printArray(arr, n);

    int arr2[] = {7, 2, 10, 5, 1, 8, 4};
    n = sizeof(arr2) / sizeof(arr2[0]);

    printf("Original array: ");
    printArray(arr2, n);

    evenOddSortQsort(arr2, n);

    printf("Sorted array (qsort): ");
    printArray(arr2, n);

    return 0;
}

Run

• Sample Output:

  Original array: 12 34 45 9 8 90 3 
  Sorted array (qsort): 8 90 34 12 3 9 45 
  Original array: 7 2 10 5 1 8 4 
  Sorted array (qsort): 4 8 10 2 1 5 7

*Note the relative order of numbers within the even and odd groups is not preserved and can vary depending on the qsort implementation.*

• Stepwise Explanation:

1. A compareEvenOdd function is defined, which takes two const void * arguments (as required by qsort).
2. Inside the comparison function, the void pointers are cast to const int * and dereferenced to get the actual integer values (num1, num2).
3. The logic prioritizes even numbers: if num1 is even and num2 is odd, num1 comes before num2 (return -1). If num1 is odd and num2 is even, num1 comes after num2 (return 1).
4. If both numbers have the same parity (both even or both odd), 0 is returned, indicating they are "equal" in terms of this even-odd sorting criteria. qsort's behavior for "equal" elements is not guaranteed to be stable.
5. The qsort function is then called with the array, its size, the size of each element, and the custom compareEvenOdd function.

Conclusion

The problem of sorting an array to separate even and odd numbers can be approached in several ways, each with distinct characteristics. The auxiliary array method is simple to implement and guarantees stability, preserving the relative order of elements within their even and odd groups, but at the cost of O(N) extra space. The two-pointer in-place method is highly space-efficient (O(1) auxiliary space) but does not maintain the original relative order. Finally, using qsort with a custom comparison function offers a concise way to achieve the separation, though it also does not guarantee stability for elements of the same parity. The best approach depends on specific requirements regarding memory usage, performance, and whether the relative order of elements needs to be preserved.

Summary

• Problem: Reorder an array to place all even numbers before all odd numbers.
• Auxiliary Array Method:
• Pros: Stable (preserves relative order), easy to understand.
• Cons: O(N) auxiliary space complexity.
• Two-Pointer In-Place Method:
• Pros: Space-efficient (O(1) auxiliary space).
• Cons: Unstable (does not preserve relative order).
• qsort with Custom Comparator:
• Pros: Concise code using standard library, potentially efficient for large arrays.
• Cons: Unstable (does not preserve relative order).
• Key Consideration: Choose an approach based on whether preserving the relative order of elements is a requirement for your specific application.