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.