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 <stdio.h>

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 {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

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 <stdio.h>

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

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

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.

#include <stdio.h>

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++)
        printf("%d ", arr[i]);
    printf("\n");
}

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