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

Problem Statement

You have given an array of integers. The problem “Rearrange array such that even index elements are smaller and odd index elements are greater” asks to rearrange the array in such a manner that the even index elements should be smaller than the odd index elements in a modified array.

Example

arr[]={ 2,5,7,1,3,4 }

2 7 1 5 3 4

Explanation: 2 is in even index position(0 index) so it is smaller than the next odd indexed element, 1 is smaller than 5 which is on the odd indexed element.

Algorithm to rearrange array such that even indexed elements are smaller than odd indexed

1. Traverse the array from 0 to n-1(less than the length of the array).
2. Check if the index is even and the next element is smaller than the current element then swap both of the numbers.
3. Check if the index is odd and the next element is greater than the current element, then swap both of the numbers.
4. Print the array.

Explanation

Given an array of length n. We are asked to rearrange the array in such a way that the even index elements are smaller than the odd indexed elements. We will be doing this by swapping up the elements if the conditions are not satisfied. First, we have to check its type either it is even or odd then we have to modify the array.

Traverse the array from 0 to less than n-1 where n is the length of the array. Take one less than n-1 up to the traversal because we are going to compare it with the next element if present in the array. So we have to leave that place for comparison else it will through an error. If we loop until less than n, then it will hit the index which does not exist in the array. That’s why we took 0 to less than n – 1 traversal.

We will traverse the array and check for each value of ‘i’ is it is even or odd if it is even and also array[i] is greater than the next element. It means the next element position as i is definitely odd, and that odd positioned element is less than the even positioned element. So we are going to swap the elements as arr[i] is the current even element and arr[i+1] is the next odd positioned element.

Now simultaneously we check if the value of ‘i’ is odd and also if the element at this index is smaller than the previous element then also we are going to swap the values in the array. After swapping all the possible values, the array so formed will be the final and desired output.

Code

C++ code to rearrange array such that even indexed elements are smaller than odd indexed

#include <iostream>
using namespace std;

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

        if (i % 2 != 0 && arr[i] < arr[i + 1])
            swap(arr[i], arr[i + 1]);
    }
}

void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";

    cout << endl;
}

int main()
{
    int arr[] = {  2,5,7,1,3,4  };
    int n = sizeof(arr) / sizeof(arr[0]);

    evenOddComparison (arr, n);

    printArray(arr, n);

    return 0;
}

2 7 1 5 3 4

Java code to rearrange array such that even indexed elements are smaller than odd indexed

class rearrangeArray
{
    public static void evenOddComparison(int arr[], int n)
    {

        int temp;
        for (int i = 0; i < n - 1; i++)
        {
            if (i % 2 == 0 && arr[i] > arr[i + 1])
            {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
            if (i % 2 != 0 && arr[i] < arr[i + 1])
            {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
    }
    public static void printArray(int arr[], int size)
    {
        for (int i = 0; i < size; i++)
            System.out.print(arr[i] + " ");

        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = { 2,5,7,1,3,4 };
        int n = arr.length;

        evenOddComparison (arr, n);

        printArray(arr, n);
    }
}

2 7 1 5 3 4

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. We have just traversed the array and have swapped the elements thus the time complexity is linear.

Space Complexity

O(1) because we have used constant space but the program as a whole takes O(n) space.