## Introduction

This article will explain array rearrangement; we will learn how to manipulate an array by various methods to place positive elements at even and negative elements at odd positions. After reading this blog, you will learn array rearrangement techniques. We will discuss the algorithm for rearrangement with the given condition with its pseudocode, program, and time complexity.

Must Read, __Array Implementation of Queue____ __and __Rabin Karp Algorithm__

### Problem statement

We are given an array in this problem, and we must rearrange it so that all positive numbers are in even indexes and all negative numbers are in odd indexes. If the number of positive and negative values is uneven, we shall not transfer any additional values.

### Examples

**Input **

`N=6, arr[]={1 -3 -2 4 5 -9}`

We want to get all positive numbers at the even index and all negative numbers at the odd index.

**Output**

`arr[] = {1, -3, 4, -2, 5, -9}`

**Input**

`N=6, arr[]={3, 9, 10, -3, -4, -7}`

**Output**

`arr[] = {3, -3, 9, -4, 10, -7} `

## Brute Force Approach

The brute force approach will be straightforward; in this, we will sort the whole array, and then we will make a copy array and place n/2 negative elements at even positions and n/2 odd elements at odd positions.

### Algorithm

- Take the input for the number of elements for the array.
- Take the input for the elements of the array.
- Sort the array in ascending order.
- Doing the above step will divide the array into n/2 negative elements and n/2 positive elements, n being the size of the array.
- We will make an empty array of the same as the input array.
- We will initialize a variable k with zero; we will fill the empty array with firstly all odd elements and then with all even elements.
- By doing so, we will get the positive element at even and the negative element at the odd position.

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
// initializing and taking input for no of elements.
int n;
cin >> n;
int a[n];
// initializing and taking input for the array.
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << "The size of the array: " << n << endl;
cout << "The array elements before the rearrangement: ";
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
// sorting the array
sort(a, a + n);
// making another array of size n
int b[n];
// fixing all negative numbers
int k = 0;
for (int i = 1; i < n; i += 2)
{
b[i] = a[k];
k++;
}
// fixing all even numbers
for (int i = 0; i < n; i += 2)
{
b[i] = a[k];
k++;
}
// printing the modified array
cout << "The array elements after the rearrangement: ";
for (int i = 0; i < n; i++)
{
cout << b[i] << " ";
}
cout << endl;
return 0;
}
```

**Input**

`n=8, arr[]={11, 5, 6, -1, -6, -7, -1, 7}`

**Output**

```
The size of the array: 8
The array elements before the rearrangement: 11 5 6 -1 -6 -7 -1 7
The array elements after the rearrangement: 5 -7 6 -6 7 -1 11 -1
```

**Complexity analysis**

**Time complexity**

The time complexity is O(Nlog(N)), where n is the size of the array as we used sorting to separate negative and positive elements.

**Space complexity**

O(N) will be the space complexity as we have taken an extra array to make a copy of the array.