Home » Data Structure » Array Data Structure

Rearrange the array such that arr[i]>=arr[j] if i is even and arr[i]<=arr[j] if i is odd and j<i

C++ implementation to rearrange the array such that arr[i]>=arr[j] if i is even and arr[i]<=arr[j] if i is odd and j<i using multiple approaches.
Submitted by Vikneshwar GK, on March 14, 2022

Consider an integer array, of size n. The task at hand is to sort the array in such a way that the elements in the even position are greater than all the odd positioned elements before it and the elements in the odd position are lesser than all the even positioned elements before it.

Example:

Input:
array[]= {1, 2, 3, 4, 5}

Output:
array[] = {3, 4, 2, 5, 1} 

Input:
array[] = {1, 2, 3, 4, 5, 6}

Output:
array[] = {3, 4, 2, 5, 1, 6}

Solution 1: Sort and Partition

This approach involves an additional array that has the same array elements as the original array but is sorted. The sorted array is partitioned to hold the odd positioned elements and even position elements. These elements are assigned accordingly to the original array. It involves the following steps:

• Store the odd positioned elements, from the sorted array, in the odd positions of the original array by iterating from (n - floor(n/2)) to 0, where n is the length of the array.
• Store the even positioned elements, from the sorted array, in the even positions of the original array by iterating from (n - floor(n/2) + 1) to n-1
• Print the original array.

C++ Implementation:

#include <bits/stdc++.h>

using namespace std;

// function to rearrange the array
void rearrangeArray(int array[], int length)
{
    // declare temporary array
    int temp[length];
    // even and odd lengths
    int even = length / 2;
    int odd = length - even;

    // copy elements to temporary array
    for (int i = 0; i < length; i++) {
        temp[i] = array[i];
    }

    // sort the array
    sort(temp, temp + length);

    int index = odd - 1;

    // store elements in odd positions
    for (int i = 0; i < length; i += 2) {
        array[i] = temp[index];
        index--;
    }

    index = odd;

    // store elements in even positions
    for (int i = 1; i < length; i += 2) {
        array[i] = temp[index];
        index++;
    }
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// Main function
int main()
{
    int array[100], N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    rearrangeArray(array, N);
    printArray(array, N);
    
    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1: 2
Enter element 2: 4
Enter element 3: 1
Enter element 4: 5
Enter element 5: 3
3 4 2 5 1 

Time Complexity: O(nlog(n)), where n is the length of the array.

Solution 2: Forward and Backward Iteration

This method, like the previous approach, requires an additional array to the original array but sorted. Here, we iterate the sorted array and store them in the original array from the end to the beginning by decrement by 2. When the index reaches 0, we now move forward by incrementing by 2. It involves the following steps:

• Copy elements from the original array to the temporary array and sort them.
• Set index = n-1 if n is odd, index = n-2 if n is even.
• Iterate through the sorted array and store them in the index position of the original array and perform index - =2.
• When index = 0, set index = 1 and perform the same step but with index+=2.
• Print the original array.

C++ Implementation:

#include <bits/stdc++.h>

using namespace std;

// function to rearrange the array
void rearrangeArray(int array[], int length)
{
    // declare temporary array
    int temp[length];
    // even and odd lengths
    int even = length / 2;
    int odd = length - even;

    // copy elements to temporary array
    for (int i = 0; i < length; i++) {
        temp[i] = array[i];
    }

    // sort the array
    sort(temp, temp + length);

    int index, sign = -2;

    // set index based on odd or even length
    if (length % 2 == 0) {
        index = length - 2;
    }
    else {
        index = length - 1;
    }

    // iterate through the array
    for (int i = 0; i < length; i++) {

        array[index] = temp[i];

        // condition to start forward movement
        if (index == 0) {
            index++;
            sign = 2;
            continue;
        }
        index += sign;
    }
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// Main function
int main()
{
    int array[100], N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    rearrangeArray(array, N);
    printArray(array, N);
    
    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1: 1
Enter element 2: 2
Enter element 3: 3
Enter element 4: 4
Enter element 5: 5
Enter element 6: 6
3 4 2 5 1 6 

Time Complexity: O(nlog(n)), where n is the length of the array.