Example
Here is an example of understanding the problem of rearranging an array such that arr[i] >= arr[j] if "i" is even and arr[i]<=arr[j] if "i" is odd and j < i.
Input array: int arr[] = { 4, 5, 1, 2, 9, 8 }
Output: After rearranging the elements of the array: { 4, 5, 2, 8, 1, 9 }
Explanation: We're given an array of odd and even integers to work with. Now we'll compare the arr[i] position to the arr[j] position and see if arr[i] is even or odd. If arr[i] is even, make sure arr[i] is more than arr[j], and if arr[i] is odd, make sure arr[i] is less than arr[j].
Algorithm
The algorithm for rearranging the elements of the array is as follows:
- Set the even positions to the floor of ( n/2).
- Set the odd places to n - even positions.
- Create a temporary array.
- Copy all the elements of the given array to the temporary array.
- The temporary array should be sorted.
- Set the value of j equals to odd positions - 1.
- Copy the value of the temporary array to the original array[j] at the even position(index-based) of the given array and decrement the value of j by 1.
- Set the value of j equals to odd positions.
- Copy the value of the temporary array to the original array[j] at the odd position(index-based) of the given array and increment the value of j by 1.
- Print the elements of the original array.
Working
We will see the working of the algorithm. We are not using index-based numbering in this case. Elements in the 0 position should be treated as if they were in the first position, which is unusual. We count from 1 as odd to n numbers.
Make a copy of the given initial array into the temporary array, and then count how many even and odd positions can be found in the array. After that, we'll sort the array in ascending order.
Update the array elements at the odd position (non-array-based indexing) as decreasing values of odd place – 1 to 0 from the temporary array.
The elements from half of the temporary array will be stored in the original array's odd position. Similarly, the rest of the values from the second half of the temporary array will be put at the even part of the original array. It will allow us to rearrange the array so that elements in even places are larger and elements in odd positions are smaller than all of the elements before them.
Explanation
Here is the diagrammatic explanation of the working of the algorithm to better understand the solution.
Step 1: Original array;
Even Positions: floor ( n/2 ) => floor ( 7 /2 ) = 3.
Odd Positions: n - even Positions =>( 7 - 3)= 4.
Step 2: Temporary Array Elements; We will copy all the original array elements to the temporary array and sort the elements.
Step 3: Set j equals to odd positions - 1. Copy the temporary array elements to the original array[j] at the even place (index-based) of the given array and decrement the value of j by 1.
The updated original array;
We can see that the elements only at the even positions have been changed, and the rest elements are unchanged.
Step 4: Now set j equals to odd positions. Copy the value of the temporary array to the original array[j] at the odd position(index-based) of the given array and increment the value of j by 1.
The new original array;
This is the required and updated array. Print this array as output.
Now we are ready to see the algorithm’s implementation. Let’s understand the implementation of this algorithm in different ways.
Source
Implementation
Here is the implementation of the algorithm in different programming languages.
Approach 1(C++)
The given code is the implementation of our algorithm in C++ language.
Code
#include<iostream>
#include<algorithm>
using namespace std;
void rearrangeArray(int array[], int n)
{
int evenPosition = n / 2;
int oddPosition = n - evenPosition;
int temporaryArray[n];
for (int i = 0; i < n; i++)
temporaryArray[i] = array[i];
sort(temporaryArray, temporaryArray + n);
int j = oddPosition - 1;
for (int i = 0; i < n; i += 2)
{
array[i] = temporaryArray[j];
j--;
}
j = oddPosition;
for (int i = 1; i < n; i += 2)
{
array[i] = temporaryArray[j];
j++;
}
}
void printArray(int array[], int n)
{
for (int i = 0; i < n; i++)
cout << array[i] << " ";
}
int main()
{
int array[] = { 1,4,6,2,4,8,9};
int n = sizeof(array) / sizeof(array[0]);
rearrangeArray(array, n);
printArray(array,n);
return 0;
}
You can also try this code with Online C++ Compiler
Output
Approach 2(Python 3)
The given code is the implementation of our algorithm in Python language.
Code
import array as a
import numpy as np
# function to rearrange the given array
def rearrangeArray(arr, n):
# total number of even positions
evenPos = int(n / 2)
# total number of odd positions
oddPos = n - evenPos
# intialising empty array
tempArray = np.empty(n, dtype = object)
# copy original array temporary array
for i in range(0, n):
tempArray[i] = arr[i]
# sort the temporary array
tempArray.sort()
j = oddPos - 1
# filling up the odd position in original array
for i in range(0, n, 2):
arr[i] = tempArray[j]
j = j - 1
j = oddPos
# filling up even positions in original array
for i in range(1, n, 2):
arr[i] = tempArray[j]
j = j + 1
# Display
for i in range(0, n):
print (arr[i], end = ' ')
# Driver code
arr = a.array('i', [ 1, 4, 6, 2, 4, 8, 9 ])
rearrangeArray(arr, 7)
You can also try this code with Online Python Compiler
Output
Approach 3(C#)
The given code implements our algorithm using the C# language.
Code
using System;
public class CodingNinjas {
// Function to rearrange array
public static void rearrangeArray(int []array, int n)
{
// total number of even positions
int evenPos = n / 2;
// total number of odd positions
int oddPos = n - evenPos;
int[] tempArray = new int [n];
// copy original array in temporary
for (int i = 0; i < n; i++)
tempArray[i] = array[i];
// sorting the temp array
Array.Sort(tempArray);
int j = oddPos - 1;
// Fill up odd position in array
for (int i = 0; i < n; i += 2) {
array[i] = tempArray[j];
j--;
}
j = oddPos;
// Fill up even positions
for (int i = 1; i < n; i += 2) {
array[i] = tempArray[j];
j++;
}
// display
for (int i = 0; i < n; i++)
Console.Write(array[i] + " ");
}
// Driver Code
public static void Main()
{
int[] array = new int []{ 1, 4, 6, 2, 4, 8, 9 };
int size = 7;
rearrangeArray(array, size);
}
}
Output
Also see, Morris Traversal for Inorder and Rabin Karp Algorithm
Complexity Analysis
We have discussed various approaches in different languages of our Algorithm. Now let’s analyse the space and time complexity of the algorithm.
Time complexity
The algorithm's time complexity is O(n log n), where "n" is the number of elements in the array.
Space complexity
The algorithm's time complexity is O(n), where "n" is the number of elements in the array.
Check out this problem - Next Smaller Element
Frequently Asked Questions
What does it mean when an array is referred to as a data structure?
Because they hold elements of the same type, arrays are categorised as homogeneous data structures. Numbers, strings, a boolean value, characters, objects, and other data can be stored. However, after deciding what kind of values your array will hold, all of its elements must be of that type.
Is it possible to modify the size of an array during execution?
No, we won't be able to adjust the array size. There are, however, similar data types that allow for size changes.
What are some of the uses of arrays?
Other data structures, such as linked lists, are implemented using them. Arrays are commonly used to represent database records. The computer uses it in lookup tables. It effectively implements memory addressing logic, in which indices serve as addresses for a one-dimensional array of memory.
Conclusion
This blog discussed the method with which we can rearrange an array such that arr[i] >= arr[j] if "i" is even and arr[i]<=arr[j] if "i" is odd and j < i.
We have discussed,
- Example of the method.
- Algorithm for the solution using the index-based method.
- Working of the Algorithm.
- Explanation of the Algorithm.
- Implementation of the Algorithm.
This blog is related to array rearrangement, so it is advised to check these articles on rearranging an array and rearranging an array such that arr[i] = i. You can visit Coding Ninjas Studio for more Coding Interview Questions.
Recommended Problems -
To learn more about array rearrangement problems, visit the Array rearranging Problems at Coding Ninjas Studio.
Head over to 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!!
We wish you Good Luck! Keep coding and keep reading Ninja!!
40+ registered 
