Approach 1 (Using Swapping)
We have been asked to reorder the array so that the components at even positions are greater than the preceding elements. Remember, we're not going to look at 0based indexing here. As a result, the array's initial element will be considered to be in the odd position. And then there's the second, which is in an even position, and so on.
We'll begin by traversing the array from position â€ś1â€ť and determining whether the position is even. If this is the case, we'll see if the evennumbered element is greater than the previouslynumbered elements, and the values should be swapped. Otherwise, we will check if the position is odd and smaller than the previous element, and then we will swap the element.
Algorithm
 Traverse from index 0 to n in the array (length of the array).
 Determine whether the position is even or odd.
i. If the position is even and if arr [i] is bigger than arr [i1],
â€“ swap the array members.
ii. Else, if arr [i] is smaller than arr [i1],
â€“ swap the array members.
 Display the array.
Implementation in C++
//By swapping, rearrange the array so that even positions are greater than odd positions.
#include <iostream>
using namespace std;
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void rearrange(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
if(i%2 == 0 && arr[i] > arr[i+1])
{
swap(&arr[i], &arr[i+1]);
}
else if(i%2 != 0 && arr[i] < arr[i+1])
{
swap(&arr[i], &arr[i+1]);
}
}
}
int main()
{
//take input from user
int n;
cout << "Enter the number of elements in the array: ";
cin >> n;
int arr[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++)
cin >> arr[i];
//call the function
rearrange(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Implementation in Java
//By swapping the even and odd positions, rearrange the array so that even is greater than odd.
import java.util.*;
class arrayEvenOdd
{
void swap(int a[],int i,int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
void rearrange(int arr[], int n)
{
for(int i = 0; i < n1; i++)
{
if((i%2 == 0) && (arr[i] > arr[i+1]))
{
swap(arr,i,i+1);
}
else if((i%2 != 0) && (arr[i] < arr[i+1]))
{
swap(arr,i,i+1);
}
}
}
public static void main(String args[])
{
//take input from user
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of elements in the array:");
int n = sc.nextInt();
int arr[] = new int[n];
System.out.println("Enter the elements of the array:");
for(int i=0; i<n; i++)
{
arr[i] = sc.nextInt();
}
//call the function
arrayEvenOdd obj = new arrayEvenOdd();
obj.rearrange(arr,n);
//print the array
System.out.println("The array after rearranging is:");
for(int i=0; i<n; i++)
{
System.out.print(arr[i]+" ");
}
}
}
Output
Complexity Analysis
Time Complexity: O (n), where â€śnâ€ť is the number of elements in the provided array. We have only traversed the array, which takes a linear amount of time.
Space Complexity: O (1). This algorithm is an inplace approach, which means it takes up the same amount of space every time. However, because of the input, the entire programme has O (N) space complexity.
Also see, Morris Traversal for Inorder and Rabin Karp Algorithm
Approach 2 (Using Sorting)
As we are interested in arranging the array such that the evenpositioned elements are greater, we can assign these greater elements to even indexes of the array. We can assign the rest of the elements to odd positions. This approach does the same thing after sorting the array.
In this approach, we will sort the array and assign the first (n/2) elements to odd positions. Letâ€™s look at the algorithm of this approach.
Algorithm
 Sort the array.
 Iterate through the array
 If the index is even, store the left pointer element in the temp array.
â€“ increment left pointer
 If the index is odd, store the right pointer element in the temp array.
â€“ decrement right pointer
 Print the temp array.
Implementation in C++
//Rearrange array such that evenposition elements are greater than odd by sorting
#include <iostream>
#include <algorithm>
using namespace std;
// Function to rearrange array such that evenposition elements are greater than odd
void rearrange(int arr[], int n)
{
//sort the array
sort(arr, arr+n);
//temp array
int temp[n];
int left=0, right=n1; //left and right pointers
//iterate through the array
for(int i=0; i<n; i++)
{
if(i%2==0)
{
temp[i]=arr[left];
left++;
}
else
{
temp[i]=arr[right];
right;
}
}
//print the array
for(int i=0; i<n; i++)
{
cout<<temp[i]<<" ";
}
}
int main()
{
//take the input
int n;
cout<<"Enter the number of elements in array:\n";
cin>>n;
int arr[n];
cout<<"Enter the elements of the array:\n";
for(int i=0; i<n; i++)
{
cin>>arr[i];
}
rearrange(arr, n);
return 0;
}
Implementation in Java
//Rearrange array such that evenposition elements are greater than odd by sorting
import java.util.*;
class arrayEvengreater
{
// Function to rearrange array such that evenposition elements are greater than odd
static void rearrange(int arr[], int n)
{
//sort the array
Arrays.sort(arr);
//temp array to store the sorted array
int temp[] = new int[n];
//pointers to keep track of positions
int left=0, right=n1;
//loop to copy the sorted array to temp array
for(int i=0;i<n;i++)
{
if(i%2==0)
{
temp[i]=arr[left];
left++;
}
else
{
temp[i]=arr[right];
right;
}
}
//print the temp array
System.out.println("Array after rearranging: ");
for(int i=0;i<n;i++)
System.out.print(temp[i]+" ");
}
// Driver method
public static void main(String args[])
{
//take input from user
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of elements in array:");
int n = sc.nextInt();
int arr[] = new int[n];
System.out.println("Enter the elements of the array:");
for(int i=0;i<n;i++)
arr[i] = sc.nextInt();
rearrange(arr, n);
}
}
Output
Complexity Analysis
Time Complexity: O (N log N), where n is the number of elements in the provided array. Sorting takes O (N*log N) time, and traversing takes O (N) time in this algorithm. As a result, the entire time complexity is O (N*log N + N) or just O (N*log N).
Space Complexity: O (N), since the sorting takes the space of O(N), by default.
Frequently Asked Questions
What is the difference between an array and a linked list?
The major differences between an array and a linked list are as follows.
 Arrays have a fixed size, whereas linked lists have a dynamic size.

In an array of elements, the insertion and deletion of a new element are difficult. However, in linked lists, both insertion and deletion are simple.
Give a realworld example of where data structures are used.
From the following examples, we can understand the importance of using data structures in real life.
 To keep track of a group of commonly used keywords.
 In a drivein burger restaurant, to keep customer order information. (Customers continue to arrive, and they must obtain the appropriate meal at the payment/collection window.)

To keep track of biological species' genealogy information.
What's the difference between a queue and a stack?
The main difference between Stack and Queue Data Structures is that Stack uses a LIFO data structure type, whereas Queue uses a FIFO data structure type. Last In First Out (LIFO) is a term that relates to the order in which things are done. When we add data to a Stack, the last entry is processed first. FIFO, on the other hand, is a term that stands for "First In, First Out."
What is the purpose of sorting in a data structure?
Sorting is the process of arranging data in a specific format. The sorting algorithm explains how data should be arranged in a specific order. The most prevalent types of ordering are numerical and lexicographical.
Conclusion
In this article, we have discussed the data structure problem of reordering an array such that the even positions are greater than the odd ones and their implementation in Java and C++ programming languages.
We hope that this blog has helped you learn more about reordering an array and if you would like to learn more, check out our articles on Strings, Arrays, Heap and Priority Queue, Linked List, Stack, Queue. Please upvote this blog to help other friends learn data structures.
You can also visit our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations and much more!
Recommended Problems 
Happy Reading!