C++ Program For Even Odd Sorted Array

An array is considered even-odd sorted when all its even numbers are grouped together at the beginning, followed by all its odd numbers, with both the even and odd sub-arrays individually sorted in ascending order. This arrangement can be useful in various data processing and algorithmic tasks where specific ordering of elements based on parity is required.

In this article, you will learn how to rearrange an array of integers into an even-odd sorted structure using different C++ programming techniques.

Problem Statement

Given an unsorted array of integers, the task is to reorder its elements such that:

• All even numbers appear before all odd numbers.
• The group of even numbers is sorted in ascending order.
• The group of odd numbers is sorted in ascending order.

For instance, if the input array is [4, 1, 3, 2, 5, 6], the desired output would be [2, 4, 6, 1, 3, 5]. This problem requires a combination of partitioning and sorting techniques to achieve the specified arrangement.

Example

Let's consider an example to illustrate the expected outcome.

Input Array: [7, 2, 8, 1, 4, 9, 3, 6]

Expected Even-Odd Sorted Array: [2, 4, 6, 8, 1, 3, 7, 9]

Background & Knowledge Prerequisites

To effectively understand and implement the solutions, a basic understanding of the following C++ concepts is helpful:

• Arrays and Vectors: How to declare, initialize, and manipulate dynamic arrays (std::vector).
• Loops: for loops for iterating through collections.
• Conditional Statements: if-else statements for parity checks.
• Standard Library Algorithms: Functions like std::sort for sorting and std::stable_partition for partitioning.
• Functions: Defining and calling custom functions.
• Iterators: For specifying ranges in STL algorithms.

Relevant setup information for C++ includes using the for input/output, for dynamic arrays, and for sorting and partitioning utilities.

Use Cases or Case Studies

Organizing data into even-odd sorted arrays can be beneficial in several scenarios:

• Optimized Search: In databases or search algorithms where queries often target even or odd properties, pre-sorting can speed up retrieval.
• Data Visualization: Presenting data in a structured manner where patterns related to parity are highlighted, such as financial reports separating even-numbered transaction IDs from odd ones.
• Resource Management: In systems where resources are assigned even or odd IDs, this sorting can help in efficient allocation or deallocation processes.
• Game Development: Organizing game objects or entities based on their unique IDs (even for player characters, odd for NPCs) to simplify processing or rendering pipelines.
• Educational Tools: Demonstrating sorting and partitioning concepts in computer science education, providing a clear visual example of combined operations.

Solution Approaches

We will explore three distinct approaches to achieve an even-odd sorted array in C++. Each method offers a different balance of readability, efficiency, and use of standard library features.

Approach 1: Two-Pass with Auxiliary Vectors

This approach involves creating two temporary vectors, one for even numbers and one for odd numbers. We populate these vectors in the first pass, then sort them individually, and finally merge them back into the original array or a new result array.

One-line summary: Iterate through the array to separate evens and odds into temporary vectors, sort each, and then combine them.

// Even-Odd Sorted Array - Auxiliary Vectors
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::sort

void evenOddSortAuxiliary(std::vector<int>& arr) {
    // Step 1: Create auxiliary vectors for even and odd numbers
    std::vector<int> evens;
    std::vector<int> odds;

    // Step 2: Populate auxiliary vectors
    for (int num : arr) {
        if (num % 2 == 0) { // Check if number is even
            evens.push_back(num);
        } else { // Number is odd
            odds.push_back(num);
        }
    }

    // Step 3: Sort the auxiliary vectors
    std::sort(evens.begin(), evens.end());
    std::sort(odds.begin(), odds.end());

    // Step 4: Combine sorted evens and odds back into the original array
    arr.clear(); // Clear the original array to refill
    for (int num : evens) {
        arr.push_back(num);
    }
    for (int num : odds) {
        arr.push_back(num);
    }
}

int main() {
    std::vector<int> arr = {7, 2, 8, 1, 4, 9, 3, 6};

    std::cout << "Original Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    evenOddSortAuxiliary(arr);

    std::cout << "Even-Odd Sorted Array (Auxiliary): ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::vector<int> arr2 = {10, 5, 20, 15, 30, 25};
    std::cout << "Original Array 2: ";
    for (int num : arr2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    evenOddSortAuxiliary(arr2);

    std::cout << "Even-Odd Sorted Array 2 (Auxiliary): ";
    for (int num : arr2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Original Array: 7 2 8 1 4 9 3 6 
Even-Odd Sorted Array (Auxiliary): 2 4 6 8 1 3 7 9 
Original Array 2: 10 5 20 15 30 25 
Even-Odd Sorted Array 2 (Auxiliary): 10 20 30 5 15 25

Stepwise Explanation:

1. Initialization: Two empty std::vector objects, evens and odds, are created.
2. Population: The input arr is iterated. Each number is checked for parity (num % 2 == 0). Even numbers are added to evens, and odd numbers to odds.
3. Sorting: std::sort is called on both evens and odds vectors independently to sort their elements in ascending order.
4. Combination: The original arr is cleared. Then, all elements from evens are appended to arr, followed by all elements from odds. This reassembles the array in the desired even-odd sorted order.

Approach 2: In-place Partitioning with Two Pointers and std::sort

This approach modifies the array in-place to first partition it into even and odd sections using a two-pointer technique, then sorts each section. This avoids the extra space overhead of auxiliary vectors during the partitioning phase.

One-line summary: Use two pointers to partition the array in-place into even and odd sections, then apply std::sort to each section separately.

// Even-Odd Sorted Array - In-place Partitioning
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::sort
#include <iterator>  // Required for std::distance

void evenOddSortInPlace(std::vector<int>& arr) {
    if (arr.empty()) {
        return;
    }

    // Step 1: Partition the array in-place using two pointers
    // Move all even numbers to the left side and odd numbers to the right.
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) {
        // Find an odd number on the left side
        while (left < right && arr[left] % 2 == 0) {
            left++;
        }
        // Find an even number on the right side
        while (left < right && arr[right] % 2 != 0) {
            right--;
        }

        // If an odd number is found on the left and an even on the right, swap them
        if (left < right) {
            std::swap(arr[left], arr[right]);
            left++;
            right--;
        }
    }

    // After this loop, 'left' points to the first odd number or end of array
    // All elements before 'left' (exclusive) are even, all after (inclusive) are odd.

    // Step 2: Determine the split point
    // 'left' pointer is now at the beginning of the odd section or past the end
    // if all numbers are even/odd.
    int first_odd_index = 0;
    for (size_t i = 0; i < arr.size(); ++i) {
        if (arr[i] % 2 != 0) {
            first_odd_index = i;
            break;
        }
        first_odd_index = arr.size(); // If all numbers are even
    }


    // Step 3: Sort the even section
    std::sort(arr.begin(), arr.begin() + first_odd_index);

    // Step 4: Sort the odd section
    std::sort(arr.begin() + first_odd_index, arr.end());
}

int main() {
    std::vector<int> arr = {7, 2, 8, 1, 4, 9, 3, 6};

    std::cout << "Original Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    evenOddSortInPlace(arr);

    std::cout << "Even-Odd Sorted Array (In-place): ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::vector<int> arr2 = {10, 5, 20, 15, 30, 25};
    std::cout << "Original Array 2: ";
    for (int num : arr2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    evenOddSortInPlace(arr2);

    std::cout << "Even-Odd Sorted Array 2 (In-place): ";
    for (int num : arr2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::vector<int> arr3 = {1, 3, 5, 7, 9}; // All odd
    std::cout << "Original Array 3 (All Odd): ";
    for (int num : arr3) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    evenOddSortInPlace(arr3);
    std::cout << "Even-Odd Sorted Array 3 (In-place): ";
    for (int num : arr3) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::vector<int> arr4 = {2, 4, 6, 8, 10}; // All even
    std::cout << "Original Array 4 (All Even): ";
    for (int num : arr4) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    evenOddSortInPlace(arr4);
    std::cout << "Even-Odd Sorted Array 4 (In-place): ";
    for (int num : arr4) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Original Array: 7 2 8 1 4 9 3 6 
Even-Odd Sorted Array (In-place): 2 4 6 8 1 3 7 9 
Original Array 2: 10 5 20 15 30 25 
Even-Odd Sorted Array 2 (In-place): 10 20 30 5 15 25 
Original Array 3 (All Odd): 1 3 5 7 9 
Even-Odd Sorted Array 3 (In-place): 1 3 5 7 9 
Original Array 4 (All Even): 2 4 6 8 10 
Even-Odd Sorted Array 4 (In-place): 2 4 6 8 10

Stepwise Explanation:

1. Partitioning: Two pointers, left and right, are initialized to the beginning and end of the array, respectively.

• The left pointer moves right, skipping even numbers, until it finds an odd number.
• The right pointer moves left, skipping odd numbers, until it finds an even number.
• If left is still less than right, it means an odd number is on the left side and an even number is on the right side. These elements are swapped, effectively moving the even number to the left and the odd to the right. Both pointers then move towards the center.
• This process continues until left and right cross or meet. At this point, all even numbers are roughly on the left, and all odd numbers on the right.

1. Determine Split Point: After partitioning, we need to find the exact index where the even section ends and the odd section begins. This is done by iterating from the beginning until the first odd number is encountered. If all numbers are even, this index will be arr.size().
2. Sort Even Section: std::sort is used to sort the sub-array from arr.begin() up to the first_odd_index.
3. Sort Odd Section: std::sort is then used to sort the sub-array from arr.begin() + first_odd_index to arr.end().

Approach 3: Using std::stable_partition and std::sort

The C++ Standard Library provides std::stable_partition, which is perfect for this problem's initial partitioning phase. It rearranges elements such that those satisfying a given predicate come before those that don't, while preserving the relative order of elements within each group.

One-line summary: Use std::stable_partition to group evens before odds (maintaining relative order), then apply std::sort to the even and odd sections.

// Even-Odd Sorted Array - std::stable_partition
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::sort and std::stable_partition
#include <functional> // Required for std::function (optional, for predicate)

// Predicate function to check if a number is even
bool isEven(int n) {
    return n % 2 == 0;
}

void evenOddSortStablePartition(std::vector<int>& arr) {
    // Step 1: Use std::stable_partition to move all even numbers to the front
    // It returns an iterator to the first element of the second group (odds).
    auto first_odd_it = std::stable_partition(arr.begin(), arr.end(), isEven);

    // Step 2: Sort the even section
    std::sort(arr.begin(), first_odd_it);

    // Step 3: Sort the odd section
    std::sort(first_odd_it, arr.end());
}

int main() {
    std::vector<int> arr = {7, 2, 8, 1, 4, 9, 3, 6};

    std::cout << "Original Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    evenOddSortStablePartition(arr);

    std::cout << "Even-Odd Sorted Array (Stable Partition): ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::vector<int> arr2 = {10, 5, 20, 15, 30, 25};
    std::cout << "Original Array 2: ";
    for (int num : arr2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    evenOddSortStablePartition(arr2);

    std::cout << "Even-Odd Sorted Array 2 (Stable Partition): ";
    for (int num : arr2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Original Array: 7 2 8 1 4 9 3 6 
Even-Odd Sorted Array (Stable Partition): 2 4 6 8 1 3 7 9 
Original Array 2: 10 5 20 15 30 25 
Even-Odd Sorted Array 2 (Stable Partition): 10 20 30 5 15 25

Stepwise Explanation:

1. Predicate Function: A simple boolean function isEven is defined to serve as the predicate for std::stable_partition. It returns true if a number is even, false otherwise.
2. Stable Partitioning: std::stable_partition(arr.begin(), arr.end(), isEven) is called. This function rearranges the elements in arr such that all elements for which isEven returns true (even numbers) appear before all elements for which isEven returns false (odd numbers). Importantly, it preserves the relative order of elements within the even group and within the odd group. It returns an iterator first_odd_it pointing to the first odd number in the now partitioned array.
3. Sort Even Section: std::sort(arr.begin(), first_odd_it) sorts the range from the beginning of the array up to (but not including) first_odd_it, which covers all the even numbers.
4. Sort Odd Section: std::sort(first_odd_it, arr.end()) sorts the range from first_odd_it to the end of the array, covering all the odd numbers.

Conclusion

We have explored three effective methods for rearranging an array into an even-odd sorted structure in C++. The choice of approach often depends on specific requirements like memory usage, stability (preserving relative order during partitioning), and code conciseness.

• The auxiliary vectors method is straightforward and easy to understand, making it suitable for beginners, though it uses O(N) extra space.
• The in-place two-pointer partitioning method offers a space-efficient solution (O(1) extra space for partitioning), but its partitioning logic can be slightly more complex to implement correctly.
• The std::stable_partition and std::sort approach leverages powerful C++ Standard Library algorithms, providing a concise, efficient, and robust solution that handles partitioning and sorting with excellent readability for those familiar with STL.

Summary

• An even-odd sorted array groups all even numbers first, then all odd numbers, with both groups sorted individually.
• Approach 1 (Auxiliary Vectors): Simple to implement, involves separating evens and odds into temporary vectors, sorting them, and then merging. Uses O(N) additional space.
• Approach 2 (In-place Two Pointers): Optimizes space by partitioning the array in-place using two pointers, then sorting the resulting even and odd sections. Achieves O(1) auxiliary space for partitioning.
• Approach 3 (std::stable_partition): Employs std::stable_partition for efficient and concise partitioning (which also preserves relative order within partitions), followed by std::sort on the resulting sub-arrays. This is generally the preferred C++ idiomatic solution for such problems.