Home » Data Structure » Array Data Structure

Rearrange the array such that even index elements are smaller and the odd index elements are greater

C++ implementation to rearrange the array such that even index elements are smaller and the odd index elements are greater.
Submitted by Vikneshwar GK, on March 20, 2022

Consider an unsorted integer array, of size n. The task at hand is to rearrange the array in such a way that element position elements are less than the next element or odd elements are greater than the next element.

If index is even, then array[i]<=array[i+1]
If index is odd, then array[i]>=array[i+1]

Example:

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

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

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

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

Solution:

This is a simple yet efficient approach to rearrange the array in the required manner. It requires swapping the corresponding elements by checking their position in the given array. It involves the following steps:

Iterate through the array till n-1, where n is the length of the array.
If the index is even and array[i]>array[i+1], then swap these elements.
If the index is odd and array[i]<array[i+1], then swap these elements.
Print the array.

C++ Implementation:

#include <iostream>
using namespace std;

// Function to rearrange the array
// such that odd positioned elements
// are greater than even positioned elements
void rearrangeArray(int array[], int length)
{
    for (int i = 0; i < length - 1; i++) {

        // if index is even
        if (i % 2 == 0 && array[i] > array[i + 1])
            swap(array[i], array[i + 1]);

        // if index is odd
        if (i % 2 != 0 && array[i] < array[i + 1])
            swap(array[i], array[i + 1]);
    }
}

// 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];
    int 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: 7
Enter element 1: 7
Enter element 2: 3
Enter element 3: 4
Enter element 4: 1
Enter element 5: 9
Enter element 6: 5
Enter element 7: 6
3 7 1 9 4 6 5

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