Move All the Negative Elements to One Side of the Array

Understanding the Problem

The goal is to move all negative elements to one side of the array using different methods.

Method 1: Using Two Pointers

This method uses two pointers to swap negative and positive elements efficiently.

#include <iostream>
using namespace std;

void rearrange(int arr[], int n) {
    int left = 0, right = n - 1;
    while (left <= right) {
        if (arr[left] < 0) left++;
        else if (arr[right] >= 0) right--;
        else {
            swap(arr[left], arr[right]);
            left++;
            right--;
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {-12, 11, -13, -5, 6, -7, 5, -3, -6};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrange(arr, n);
    printArray(arr, n);
    return 0;
}
            

Output:

-12 -13 -5 -7 -3 -6 6 5 11

Method 2: Using Partition Process of QuickSort

This method places all negative elements before positive elements using partitioning.

#include <iostream>
using namespace std;

void partition(int arr[], int n) {
    int j = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] < 0) {
            if (i != j) {
                swap(arr[i], arr[j]);
            }
            j++;
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {-12, 11, -13, -5, 6, -7, 5, -3, -6};
    int n = sizeof(arr) / sizeof(arr[0]);
    partition(arr, n);
    printArray(arr, n);
    return 0;
}
            

Output:

-12 -13 -5 -7 -3 -6 6 5 11

Method 3: Using Extra Space

This method creates a new array and stores negative and positive elements separately.

#iinclude <iostream>
using namespace std;

void rearrangeWithExtraSpace(int arr[], int n) {
    int temp[n], index = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] < 0) temp[index++] = arr[i];
    }
    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0) temp[index++] = arr[i];
    }
    for (int i = 0; i < n; i++) arr[i] = temp[i];
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {-12, 11, -13, -5, 6, -7, 5, -3, -6};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrangeWithExtraSpace(arr, n);
    printArray(arr, n);
    return 0;
}
            

Output:

-12 -13 -5 -7 -3 -6 6 5 11