# 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 answer[10]; // answer array int begin = 0, end = n-1; // two pointers for(int j =0 ; j< n ; j++ ){ if(j%2 == 0) //even position { answer[j] = arr[end]; end--; } else { // odd position answer[j] = arr[begin]; begin++; } } cout<<endl<<"The rearranged array is:"<<endl; for(int j =0 ; j<n ; j++ ){ cout<<answer[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.

## Leave a Reply