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

Suppose you have an integer array. The problem statement asks to rearrange the array in such a way that the elements at even position in an array should be greater than all elements before it and the elements at odd positions should be less than the elements before it.

Example

Input

arr[]={1, 4, 6, 2, 4, 8, 9}

Output

4 6 4 8 2 9 1

Explanation

All elements at even positions are greater than all the elements before it and the elements at odd positions are less than the previous elements.

Algorithm

1. Set evenPosition to n / 2.
2. Set oddPosition to n – evenPosition.
3. Create an array(temporary).
4. Store all the elements of the given array into this temporary array.
5. Sort the temporary array.
6. Set j equal to oddPosition -1.
7. Copy the temporary to original array[j] at the even position (indexing based) of the given array and decrease the value of j by 1.
8. Set j to oddPosition.
9. Copy the temporary to the original array[j] at the odd position (indexing based) of the given array and increase the value of j by 1.
10. Print the original array since the updation is made in the original array.

Explanation

Given an array of integers, our task is to rearrange the array in such a way that the elements at even number of positions should be greater than all of the elements before it. And the elements at the odd number of positions should be less than all of the numbers present before it. We can see in the example as elements at even positions are greater than all the numbers before it. Here we are not taking it as index-based numbering. Element at 0 positions should be treated as 1 position that is odd. 1^st position of an array is 2 position that is even, here we are not considering array-based indexing in our result, we start from 1 as odd to n numbers.

Make a copy of the original array into the temporary array, count how many even and odd positions can be in a given array. Then, we are going to sort the array in increasing order. Now update the elements of the array at the odd position (non-array based indexing), from the temporary array as decreasing values of oddPosition – 1 to 0.

All of the elements from half of the temporary array will be stored at the odd position of the original array. Similarly, we will be storing rest of the values of the second half of the temporary array will be stored at even position of the original array, in this manner, we can rearrange the array so that the elements at even positions greater and elements at odd positions at odd elements will be smaller than all of the elements before it respectively.

Implementation

C++ program

#include<iostream>
#include<algorithm>

using namespace std;

void rearrangeArrayEvenOdd(int arr[], int n)
{
    int evenPosition = n / 2;

    int oddPosition = n - evenPosition;

    int temporaryArray[n];

    for (int i = 0; i < n; i++)
        temporaryArray[i] = arr[i];

    sort(temporaryArray, temporaryArray + n);

    int j = oddPosition - 1;

    for (int i = 0; i < n; i += 2)
    {
        arr[i] = temporaryArray[j];
        j--;
    }

    j = oddPosition;

    for (int i = 1; i < n; i += 2)
    {
        arr[i] = temporaryArray[j];
        j++;
    }
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 1,4,6,2,4,8,9};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrangeArrayEvenOdd(arr, n);
    printArray(arr,n);
    return 0;
}

4 6 4 8 2 9 1

Java program

import java.util.*;

class rearrangeArray
{
    public static void rearrangeArrayEvenOdd (int arr[], int n)
    {
        int evenPosition = n / 2;

        int oddPosition = n - evenPosition;

        int[] temporaryArray = new int [n];

        for (int i = 0; i < n; i++)
            temporaryArray[i] = arr[i];

        Arrays.sort(temporaryArray);
        int j = oddPosition - 1;

        for (int i = 0; i < n; i += 2)
        {
            arr[i] = temporaryArray[j];
            j--;
        }

        j = oddPosition;

        for (int i = 1; i < n; i += 2)
        {
            arr[i] = temporaryArray[j];
            j++;
        }
    }
    public static void printArray(int arr[], int n)
    {

        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
    public static void main(String argc[])
    {
        int[] arr = { 1,4,6,2,4,8,9};
        int size =arr.length;
        rearrangeArrayEvenOdd (arr, size);
        printArray(arr, size);

    }
}

4 6 4 8 2 9 1

Complexity Analysis

Time Complexity

O(n log n) where “n” is the number of elements in the array.

Space Complexity

O(n)  where “n”  is the number of elements in the array.