Home » Data Structure » Array Data Structure

Rearrange the array such that the even positioned are greater than odd

C++ implementation to rearrange the array such that the even positioned are greater than odd.
Submitted by Vikneshwar GK, on March 07, 2022

Consider an integer array, of size n. The task at hand is to arrange the array in such a way that the even positioned elements are greater than the previous odd positioned elements and odd positioned elements are lesser than the previous even positioned elements, i.e. array[i]>=array[i-1], if i is even and array[i]<=array[i-1], if i is odd.

Example:

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

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

Explanation:
For even positions, 
6>=1, 5>=2, and 4>=3
For odd positions,
2<=6, 3<=5

Solution: Using Sorting

This method involves sorting the array using an O(nlog(n)) algorithm. The idea here is to place the n/2 elements, which are at the right side of the array, in even positions by moving the left side n/2 elements to odd positions.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

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

void rearrangeArray(int array[], int length)
{
    // Sort the array
    sort(array, array + length);

    int solution[length];
    int odd = 0, even = length - 1;
    for (int i = 0; i < length; i++) {
        // place elements from right side on even position
        if ((i + 1) % 2 == 0)
            solution[i] = array[even--];

        // place elements from left side on off position
        else
            solution[i] = array[odd++];
    }
    printArray(solution, length);
}

// Main function
int main()
{
    int array[100], N, k;
    
    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);
    
    return 0;
}

Output:

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

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