In the given random array with both positive and negative integers, rearrange the array so that positive and negative are placed alternatively
Number of positive and negative numbers need not be equal. If there are more positive or more negative they appear at the end of the array.
Here, we rearrange all positives at odd indices and negatives at even indices.
Example
a) Input array: [-5, -7, 9, 11, 12, -15, 17]
Output array: [-5, 11, -15, 17, -7, 12, 9]
Rearranged positives and negatives in alternative positions and excess in the end.
b) Input array: [-4, -7, 9, 11, -16, 13, 3, -5]
Output array: [-16, 11, -4, 3, -7, 13, -5, 9]
Rearranged positives and negatives in alternative positions.
c) Input array: [1, -2, 3, 4, 5, -6, 7, 8, -9]
Output array: [-2, 3, -6, 5, -9, 8, 1, 4, 7]
Rearranged positives and negatives in alternative positions and excess in the end.
Algorithm
Time complexity: O(n)
a. We modify the array such that all positives will be in the beginning of the array and negatives at the end.
[1, -2, 3, 4, 5, -6, 7, 8, -9] → [1, 3, 4, 5, 7, 8, -2, -6, -9]
b. We maintain two pointers i and j. if array[j] > 0 we move it to the front of the array by swap with first element. Else we move forward.
c. We initialize negative numbers start index as negative and positive as 0.
d. Increment the negative index by 1 and positive index by 2. That means we swap every alternate positive number with next negative number.
Algorithm working
C++ Program
#include <bits/stdc++.h> using namespace std; //swap two elements based on given addresses void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } //Rearrange function void Rearrange(int array[], int n) { int i = -1; //swap positive elements to the start of the array for (int j = 0; j < n; j++) { if (array[j] > 0) { i = i + 1; swap(&array[i], &array[j]); } } //Initialize positive_index, negative_index int positive_index = 0, negative_index = i + 1; //Increment postive by 2 and negative by 1. //swap elements after each increments and swap them. //such that alternative elements will be changed while (negative_index < n && negative_index > positive_index && array[negative_index] < 0) { swap(&array[negative_index], &array[positive_index]); positive_index = positive_index + 2; negative_index = negative_index + 1; } } //Main function int main() { int input_array[] = {1, -2, 3, -4, 5, -6, -7, 8, -9}; int size = sizeof(input_array)/sizeof(int); cout<<"Input array is: "; for (int i = 0; i < size; ++i) { cout<<input_array[i]<<" "; } Rearrange(input_array, size); cout<<"\nOutput array is: "; for (int i = 0; i < size; ++i) { cout<<input_array[i]<<" "; } return 0; }