Introduction
An array comes under one of the essential topics for programming interviews. Many companies like Amazon, Microsoft, and Google ask questions of the array in the interviews. So an individual needs to have a clear understanding of this topic.
In this blog, we will discuss the problem of rearranging an array such that the even index elements are smaller and the odd index elements are greater. We will discuss two approaches for this problem, first one is the brute force approach, and the other one is the optimal approach.
Must Read, Array Implementation of Queue and Rabin Karp Algorithm
Problem Statement
Ninjas has an array of size N. After giving the array. He said he wanted to rearrange the array such that the even index elements are smaller and the odd index elements are greater. But, the problem is that he cannot rearrange the array by himself. Can you help him rearrange the array?
For every i in the rearranged array:
 If i is odd then arr[i]>=arr[i+1]

If i is even then arr[i]<=arr[i+1]
You need to output the rearranged array; note that there can be multiple possible answers.
Before we deep dive into the solution to this problem, we should look at some examples that will help us understand the problem better.
Sample Examples
Input
N=4, arr[] = {4, 7, 7, 2}
Output
arr[] = {4, 7, 2, 7}
Explanation:
Elements at the even index are smaller than the elements at the odd index.
Note: {2, 7, 4, 7} is also a valid answer.
Input
N=6, arr[] = {7, 1, 4, 6, 9, 3}
Output
{1, 6, 3, 7, 4, 9}
Input
N=3, arr[] = {1,3,2}
Output
{1,3,2}
Explanation: In this case the array is already arranged as required in the question.
Also see, Morris Traversal for Inorder.
Brute Force Approach
The brute force approach to solving this problem of rearranging an array such that the even index elements are smaller and the odd index elements are greater is simple. We first sort the array, and after that, we will start iterating from the second element, and we will take a pointer j which will start from (n/2 + 1) if n is odd. Else if n is even, it will start from (n/2). We will swap the ith element and the jth element, and after swapping, the elements will increment i by 2, and we will increment j by 1. We will perform these operations till i<n.
Algorithm
 To solve this problem, we will create a function called rearrangeArray(), and it will take one argument: the initial array.
 After that, we will sort the array.
 We will start from i=1, and we will take a pointer j which would point to (n/2+1)th element if n is odd; else, it would point to (n/2)th element. In every iteration, we will swap the ith and jth element, and then we will increment i by 2 and j by 1.
 The loop will terminate when i would be greater than or equal to n.
 After the iteration is over then, we will print the array.
Code in C++
// C++ to rearrange array such that the even index elements are smaller and the odd index elements are greater
#include <bits/stdc++.h>
using namespace std;
// function to rearrange the array
void rearrangeArray(vector<int> &a)
{
int n = a.size();
// sort the given array
sort(a.begin(), a.end());
int j = n / 2;
// if n is odd then even index elements in the array would be n/2  1
if (n % 2)
{
j++;
}
for (int i = 1; i < n; i += 2)
{
swap(a[j++], a[i]);
}
}
// Driver Code
int main()
{
int n = 6;
vector<int> a(n);
a = {7, 1, 4, 6, 9, 3};
cout << "The array before rearranging elements is:"<< " ";
for (auto x : a)
{
cout << x << " ";
}
cout << endl;
rearrangeArray(a);
cout <<"The array after rearranging elements is:" << " ";
for (auto x : a)
{
cout << x << " ";
}
cout << endl;
}
Input
The array before rearranging elements is: 7 1 4 6 9 3
Output
The array after rearranging elements is: 1 6 4 7 3 9
Algorithm Complexity
Time Complexity: O(N*log(N))
Since we are sorting the array, sorting is performed in O(N*log(N)) time complexity. Therefore the time complexity would be O(N*log(N)).
Space Complexity: O(1)
Since we are not using extra space to store the new rearranged array, the space complexity is O(1).