Home » Data Structure » Array Data Structure

Rearrange positive and negative elements in O(n) time and O(1) extra space

C++ implementation to rearrange positive and negative elements in o(n) time and o(1) extra space using quick sort.
Submitted by Vikneshwar GK, on April 08, 2022

Consider an integer array, of size n, containing positive and negative elements. The task at hand is to arrange the array in such a way that the negative and positive elements are placed alternatively, that is, negative elements at an even position and positive elements at an odd position. If the number of positive integers is greater than the number of negative integers, then place the remaining positive integers at the end of the array and vice-versa for negative integers.

Example:

Input:
array[]= {2, -1, -5, 3, 4, -6}

Output:
array[] = {3, -5, 4, -1, 2, -6} 

Input:
array[] = {-3, -1, -5, 7, 8, -2, 4, -6}

Output:
array[] = {7, -1, 4, -2, 8, -3, -5, -6}

Solution: Using Quick Sort

This approach uses the partition process of quick sort. While partitioning, consider 0 as the pivot element value so that all negative numbers are placed before positive numbers. Swapping start after the positive and negative numbers are separated. The first positive element and the first negative element are swapped and every alternate negative number with the next positive number is swapped.

C++ Implementation:

#include <bits/stdc++.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// Function to swap two elements
void swap(int* num1, int* num2)
{
    int temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

// Function to arrange positive and negative elements
void rearrange(int array[], int length)
{
    // partition and divide of quick sort
    // considering 0 as pivot
    int i = -1;
    for (int j = 0; j < length; j++) {
        if (array[j] < 0) {
            i++;
            swap(&array[i], &array[j]);
        }
    }

    // initialize indexes for positive
    // and negative elements
    int pos = i + 1, neg = 0;

    // swap until positive and negative elements
    // are placed alternatively
    while (pos < length && neg < pos && array[neg] < 0) {
        swap(&array[neg], &array[pos]);
        pos++;
        neg += 2;
    }
}

// Main function 
int main()
{
    int array[100];
    int N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    rearrange(array, N);
    printArray(array, N);

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1: 2
Enter element 2: -1
Enter element 3: -5
Enter element 4: 4
Enter element 5: 7
Enter element 6: -2
4 -5 7 -1 2 -2

Time Complexity: O(n), where n is the length of the array.