Rearrange array such that even positioned are greater than odd

Problem Statement

Suppose you have an integer array. The problem “Rearrange array such that even positioned are greater than odd” asks to rearrange the array such the elements at even position in an array should be greater than the element just before it.

Arr[i-1] < = Arr[i], if position ‘i’ is odd.

Arr[i-1] > = Arr[i], if position ‘i’ is even.

Example

Arr[] = {1, 4, 5, 2, 7}

1 7 2 5 4

Explanation: Every element at even places is greater than the elements at the previous position (i.e. odd positions).

Algorithm

1. Traverse the array from 0 to n (length of the array).
    1. Check if the position is even or odd if it is even,
        2. If arr[i] is greater than the arr[i-1], then swap the array elements.
    2. Else, if arr[i] is smaller than the arr[i-1], then swap the array elements.
2. Print the array.

Explanation

We have given an integer array. We have asked to rearrange the array in such a way that the elements at even position should be greater than the elements just before it. Remember here we will not be considering the 0-based indexing. So the first element of the array will be treated as in the odd position. And the second as in even position and so on. The idea is to traverse the array and checking the odd and even position of the array. As mentioned earlier, not considering 0-based indexing position. So we will be picking the first element from 0th position and assuming it at an odd position because it is at the first position and 1 is an odd number. More formally, we are following 1-based indexing in this question.

What we are going to do is, we have to traverse the array from position 1 and checking if that position is even. If it is true then we will go checking if the even positioned element is greater than the previously positioned elements. If it is true, then swap the values. We can also check if the element positions are not odd, that can also work. And later check for even position element is greater than the previously positioned.

We should just remember few things, if the element at even position is not greater than the value of the element which is stored at the position just before the current element even positioned, then we should replace or swap those values. So that, they can come in order like the even positioned elements are greater than the previously positioned or simply at the oddly positioned element. At last, print the array, in which swapping was done.

Code

C++ code to rearrange array such that even positioned are greater than odd

#include<iostream>

using namespace std;

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void rearrangeEvenPositioned(int arr[], int n)
{
    for (int i = 1; i < n; i++)
    {
        if (i % 2 == 0)
        {
            if (arr[i] > arr[i - 1])
                swap(&arr[i - 1], &arr[i]);
        }
        else
        {
            if (arr[i] < arr[i - 1])
                swap(&arr[i - 1], &arr[i]);
        }
    }
}

int main()
{
    int arr[] = {1, 4, 5, 2, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    rearrangeEvenPositioned(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

1 5 2 7 4

Java code to rearrange array such that even positioned are greater than odd

class rearrangeArray1
{
    public static void rearrangeEvenPositioned(int arr[], int n)
    {
        for (int i = 1; i < n; i++)
        {
            if (i % 2 == 0)
            {
                if (arr[i] > arr[i - 1])
                {
                    int temp=arr[i-1];
                    arr[i-1]=arr[i];
                    arr[i]=temp;
                }
            }
            else
            {
                if (arr[i] < arr[i - 1])
                {
                    int temp=arr[i-1];
                    arr[i-1]=arr[i];
                    arr[i]=temp;
                }
            }
        }
    }
    public static void main(String args[])
    {
        int arr[] = {1, 4, 5, 2, 7};
        int n = arr.length;
        rearrangeEvenPositioned(arr, n);
        for (int i = 0; i < n; i++)
            System.out.print(arr[i]+" ");

    }
}

1 5 2 7 4

Complexity Analysis

Time Complexity

O(N)  where “N” is the number of elements in the array. We have only traversed the array which can be done in linear time complexity.

Space Complexity

The algorithm has O(1) space complexity. This algorithm is an in-place approach thus it takes constant space. But the whole program has O(N) space complexity because of the input.