Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach 1 (Using Swapping)
3.1.
Algorithm
3.2.
Implementation in C++
3.3.
Implementation in Java
3.4.
Output
3.5.
Complexity Analysis
4.
Approach 2 (Using Sorting)
4.1.
Algorithm
4.2.
Implementation in C++
4.3.
Implementation in Java
4.4.
Output
5.
5.1.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
What is the difference between an array and a linked list?
6.2.
Give a real-world example of where data structures are used.
6.3.
What's the difference between a queue and a stack?
6.4.
What is the purpose of sorting in a data structure?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Rearrange Array such that Even Positioned are Greater than Odd

Introduction

Hey, readers! I hope you are doing well. In our previous articles, we discussed different ways to rearrange an array in our previous articles “reorder an array according to given indexes,” and “Rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest and so on.”

In this article, we will learn to reorder an array such that the even positions are greater than the odd ones. We will learn to take different approaches to solve this problem.

Let's start with a brief overview of the problem statement.

Problem Statement

Let's assume we're given an integer type Array called arr [] that contains both positive and negative numbers of any size. The goal is to rearrange an array so that all elements in even positions or indexes are greater than those in odd positions or indexes and print the result.

Example

Input: Given an array, array [n] = [2, 4, 3, 5, 6], where "n" is the size of the array.

Output: The output array would be array [] = [2, 6, 3, 5, 4].

(Image showing the rearrangement of the array)

Explanation: Here, every element in an even position is greater than the elements in odd positions.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 0-based 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 even-numbered element is greater than the previously-numbered 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

  1. Traverse from index 0 to n in the array (length of the array).
  2. Determine whether the position is even or odd.                      

i. If the position is even and if arr [i] is bigger than arr [i-1],
– swap the array members.

ii. Else, if arr [i] is smaller than arr [i-1],
– swap the array members.

  1. 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 < n-1; 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 in-place 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 even-positioned 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

  1. Sort the array.
  2. Iterate through the array
  3. If the index is even, store the left pointer element in the temp array.

   – increment left pointer

  1. If the index is odd, store the right pointer element in the temp array.

   – decrement right pointer

  1. Print the temp array.

Implementation in C++

//Rearrange array such that even-position elements are greater than odd by sorting
#include <iostream>
#include <algorithm>
using namespace std;
// Function to rearrange array such that even-position 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=n-1; //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 even-position elements are greater than odd by sorting
import java.util.*;

class arrayEvengreater
{
    // Function to rearrange array such that even-position 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=n-1;
        
        //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 real-world 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 drive-in 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 StringsArraysHeap and Priority QueueLinked ListStackQueue. 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!

Live masterclass