Rearrange array such that even positioned are greater than odd
Given an array arr[] of N elements, sort the array according to the following relations:
- arr[i] >= arr[i – 1], if i is even, ∀ 1 <= i < N
- arr[i] <= arr[i – 1], if i is odd, ∀ 1 <= i < N
Print the resultant array.
Examples:
Input: N = 4, arr[] = {1, 2, 2, 1}
Output: 2 1 2 1
Explanation:
- For i = 1, arr[1] <= arr[0]. So, 1 <= 2.
- For i = 2, arr[2] >= arr[1]. So, 2 >= 1.
- For i = 3, arr[3] <= arr[2]. So, 1 <= 2.
Input: arr[] = {1, 3, 2}
Output: 3 1 2
Explanation:
- For i = 1, arr[1] <= arr[0]. So, 1 <= 3.
- For i = 2, arr[2] >= arr[1]. So, 2 >= 1.
Approach: To solve the problem, follow the below idea:
Observe that array consists of [n/2] even positioned elements. If we assign the largest [n/2] elements to the even positions and the rest of the elements to the odd positions, our problem is solved. Because element at the odd position will always be less than the element at the even position as it is the maximum element and vice versa. Sort the array and assign the first [n/2] elements at even positions.
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
// function to rearrange the elements in array such that
// even positioned are greater than odd positioned elements
void assign(int arr[], int N)
{
// Sort the array
sort(arr, arr + N);
int ans[N];
int ptr1 = 0, ptr2 = N - 1;
for (int i = 0; i < N; i++) {
// Assign even indexes with maximum elements
if (i % 2 == 0)
ans[i] = arr[ptr2--];
// Assign odd indexes with remaining elements
else
ans[i] = arr[ptr1++];
}
// Print result
for (int i = 0; i < N; i++)
cout << ans[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
assign(arr, N);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
// Compare function for qsort
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
// function to rearrange the elements in array such that
// even positioned are greater than odd positioned elements
void assign(int arr[], int N)
{
// Sort the array
qsort(arr, N, sizeof(int), cmpfunc);
int ans[N];
int ptr1 = 0, ptr2 = N - 1;
for (int i = 0; i < N; i++) {
// Assign even indexes with maximum elements
if (i % 2 == 0)
ans[i] = arr[ptr2--];
// Assign odd indexes with remaining elements
else
ans[i] = arr[ptr1++];
}
// Print result
for (int i = 0; i < N; i++)
printf("%d ", ans[i]);
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
assign(arr, N);
return 0;
}
// This code is contributed by Sania Kumari Gupta
import java.io.*;
import java.util.*;
class GFG {
// function to rearrange the elements
// in array such that even positioned are
// greater than odd positioned elements
static void assign(int arr[], int N)
{
// Sort the array
Arrays.sort(arr);
int ans[] = new int[N];
int ptr1 = 0, ptr2 = N - 1;
for (int i = 0; i < N; i++) {
// Assign even indexes with maximum elements
if (i % 2 == 0)
ans[i] = arr[ptr2--];
// Assign odd indexes with remaining elements
else
ans[i] = arr[ptr1++];
}
// Print result
for (int i = 0; i < N; i++)
System.out.print(ans[i] + " ");
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 2, 2, 1 };
int N = arr.length;
assign(arr, N);
}
}
// This code is contributed by Nikita Tiwari.
# function to rearrange the
# elements in array such that
# even positioned are greater
# than odd positioned elements
def assign(arr, N):
# Sort the array
arr.sort()
ans = [0] * N
ptr1 = 0
ptr2 = N - 1
for i in range(N):
# Assign even indexes with
# maximum elements
if i % 2 == 0:
ans[i] = arr[ptr2]
ptr2 = ptr2 - 1
# Assign odd indexes with
# remaining elements
else:
ans[i] = arr[ptr1]
ptr1 = ptr1 + 1
# Print result
for i in range(N):
print(ans[i], end = " ")
# Driver Code
arr = [ 1, 2, 2, 1]
N = len(arr)
assign(arr, N)
# This code is contributed by "Sharad_Bhardwaj".
using System;
class GFG {
// function to rearrange the elements
// in array such that even positioned are
// greater than odd positioned elements
static void assign(int[] arr, int N)
{
// Sort the array
Array.Sort(arr);
int[] ans = new int[N];
int ptr1 = 0, ptr2 = N - 1;
for (int i = 0; i < N; i++) {
// Assign even indexes with maximum elements
if (i % 2 == 0)
ans[i] = arr[ptr2--];
// Assign odd indexes with remaining elements
else
ans[i] = arr[ptr1++];
}
// Print result
for (int i = 0; i < N; i++)
Console.Write(ans[i] + " ");
}
// Driver code
public static void Main()
{
int[] arr = { 1, 2, 2, 1 };
int N = arr.Length;
assign(arr, N);
}
}
// This code is contributed by vt_m.
// function to rearrange the elements
// in array such that even positioned are
// greater than odd positioned elements
function assign(arr, N)
{
// Sort the array
arr.sort();
let ans = [];
let ptr1 = 0, ptr2 = N - 1;
for (let i = 0; i < N; i++) {
// Assign even indexes with maximum elements
if (i % 2 == 0)
ans[i] = arr[ptr2--];
// Assign odd indexes with remaining elements
else
ans[i] = arr[ptr1++];
}
// Print result
for (let i = 0; i < N; i++)
console.log(ans[i] + " ");
}
// Driver code
let arr = [ 1, 2, 2, 1 ];
let N = arr.length;
assign(arr, N);
<?php
// function to rearrange the
// elements in array such that
// even positioned are greater
// than odd positioned elements
function assign($arr, $N)
{
// Sort the array
sort($arr);
$ptr1 = 0; $ptr2 = $N - 1;
for ($i = 0; $i < $N; $i++)
{
// Assign even indexes
// with maximum elements
if ($i % 2 == 0)
$ans[$i] = $arr[$ptr2--];
// Assign odd indexes
// with remaining elements
else
$ans[$i] = $arr[$ptr1++];
}
// Print result
for ($i = 0; $i < $N; $i++)
echo($ans[$i] . " ");
}
// Driver Code
$arr = array( 1, 2, 2, 1 );
$N = sizeof($arr);
assign($arr, $N);
// This code is contributed by Ajit.
?>
Output
2 1 2 1
Time Complexity: O(N * log N), where N is the size of input array arr[].
Auxiliary Space: O(N)
Approach 2: Rearranging array by swapping elements
One other approach is to traverse the array from the first element till N – 1 and swap the element with the next one if the condition is not satisfied. This is implemented as follows:
#include <iostream>
using namespace std;
// function to rearrange the elements in array such that
// even positioned are greater than odd positioned elements
void rearrange(int arr[], int N)
{
for (int i = 0; i < N; i += 2) {
// Compare it with the previous element
if (i > 0 && arr[i - 1] > arr[i])
swap(arr[i - 1], arr[i]);
// Compare it with the next element
if (i < N - 1 && arr[i + 1] > arr[i])
swap(arr[i + 1], arr[i]);
}
}
int main()
{
// Sample Input
int N = 4;
int arr[] = { 1, 2, 2, 1 };
rearrange(arr, N);
for (int i = 0; i < N; i++)
cout << arr[i] << " ";
cout << "\n";
return 0;
}
import java.io.*;
class GFG {
// function to rearrange the elements in array such that
// even positioned are greater than odd positioned
// elements
static void rearrange(int[] arr, int N)
{
for (int i = 0; i < N; i += 2) {
// Compare it with the previous element
if (i > 0 && arr[i - 1] > arr[i]) {
int temp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = temp;
}
// Compare it with the next element
if (i < N - 1 && arr[i + 1] > arr[i]) {
int temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
}
}
public static void main(String[] args)
{
// Sample Input
int N = 4;
int[] arr = { 1, 2, 2, 1 };
rearrange(arr, N);
for (int i = 0; i < N; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
// This code is contributed by avanitrachhadiya2155
# function to rearrange the elements in array such that
# even positioned are greater than odd positioned elements
def rearrange(arr, N):
for i in range(0, N, 2):
# Compare it with the previous element
if i > 0 and arr[i - 1] > arr[i]:
arr[i - 1], arr[i] = arr[i], arr[i - 1]
# Compare it with the next element
if i < N - 1 and arr[i + 1] > arr[i]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
# Sample Input
N = 4
arr = [1, 2, 2, 1]
rearrange(arr, N)
for i in range(N):
print(arr[i], end=" ")
print()
// C# program to rearrange the elements
// in the array such that even positioned are
// greater than odd positioned elements
using System;
class GFG {
// function to rearrange the elements in array such that
// even positioned are greater than odd positioned
// elements
static void Rearrange(int[] arr, int N)
{
for (int i = 0; i < N; i += 2) {
// Compare it with the previous element
if (i > 0 && arr[i - 1] > arr[i]) {
int temp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = temp;
}
// Compare it with the next element
if (i < N - 1 && arr[i + 1] > arr[i]) {
int temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
}
}
static void Main()
{
// Sample Input
int N = 4;
int[] arr = { 1, 2, 2, 1 };
Rearrange(arr, N);
for (int i = 0; i < N; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
}
// This code is contributed by shivanisinghss2110
// function to rearrange the elements in array such that
// even positioned are greater than odd positioned elements
function rearrange(arr, N) {
for (let i = 0; i < N; i += 2) {
// Compare it with the previous element
if (i > 0 && arr[i - 1] > arr[i]) {
[arr[i - 1], arr[i]] = [arr[i], arr[i - 1]];
}
// Compare it with the next element
if (i < N - 1 && arr[i + 1] > arr[i]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
}
}
}
// Sample Input
const N = 4;
const arr = [1, 2, 2, 1];
rearrange(arr, N);
console.log(arr.join(" "));
Output
2 1 2 1
Time Complexity: O(N), where N is the size of input array arr[].
Auxiliary Space: O(1)
Contact Us