# Rearrange array such that elements at even positions are greater than odd in C++

Hello there! In this tutorial, we will rearrange elements of an array such that elements at even positions are greater than odd positions.

e.g.

```int arr[]={15,12,13,18,5,9};
// for this output should be 18 5 15 9 13 12```

So let’s see how we can do this.

## Algorithm

The algorithm used to rearrange the array is very simple yet interesting.

• First, we sort the given array in ascending order.
• Now we define two pointers begin and end which points at the beginning and at the end respectively.
• Next, we take an answer array and start filling values from the sorted array such that if we are at an odd position in the answer array, arr[begin] is copied and begin pointer is incremented by 1.
• Similarly, if we at an even position in the answer array, arr[end] is copied and end pointer is decremented by 1.
• We do this till begin pointer is smaller than or equal than the end pointer.
• The final result will be stored in the answer array.

Here is the code of the above algorithm:

```#include <bits/stdc++.h>
using namespace std;

int main() {
int arr[] = {15,12,13,18,5,9};
int n = sizeof(arr)/sizeof(int);

cout<<"The given array is:"<<endl;
for(int j =0 ; j<n ; j++ ){
cout<<arr[j]<<' ';
}

sort(arr, arr + n);  // sorting array

int begin = 0, end = n-1;  // two pointers

for(int j =0 ; j< n ; j++ ){
if(j%2 == 0)   //even position
{
end--;
}
else {          // odd position
begin++;
}
}

cout<<endl<<"The rearranged array is:"<<endl;
for(int j =0 ; j<n ; j++ ){
}

return 0;
}
```

Output:

```The given array is:
15 12 13 18 5 9
The rearranged array is:
18 5 15 9 13 12```

In this algorithm, sorting takes O(n*logn) time and traversing takes O(n) time. Thus making overall time complexity O(n*logn + n) or simply O(n*logn). Whereas the space complexity is O(n) for the answer array.

Hope it is clear.