Rearrange an Array

Concept

Rearranging an array so that all negative numbers go to the right and all positive numbers go to the left is a commonly used operation in computer science. The goal is to segregate the elements based on their sign. This can be particularly useful in algorithms and problems that require elements to be in a specific order for optimized processing.

Example Code in Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public class Main {
    public static void main(String[] args) {
        int[] arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 };
        rearrange(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void rearrange(int[] arr) {
        int j = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 0) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                j++;
            }
        }
    }
}

Example Code in C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
#include <vector>

void rearrange(std::vector<int> &arr) {
    int j = 0;
    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] > 0) {
            std::swap(arr[i], arr[j]);
            ++j;
        }
    }
}

int main() {
    std::vector<int> arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 };
    rearrange(arr);
    for (const int &num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

Example Code in Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def rearrange(arr):
    j = 0
    for i in range(len(arr)):
        if arr[i] > 0:
            arr[i], arr[j] = arr[j], arr[i]
            j += 1

if __name__ == "__main__":
    arr = [-1, 2, -3, 4, 5, 6, -7, 8, 9]
    rearrange(arr)
    print(" ".join(map(str, arr)))

Note that all three code examples use a single loop and swap elements in-place, making the operation efficient. The order of the elements in each segregated part (positive and negative) is not guaranteed to be preserved.

The coding construct of rearranging elements in an array based on certain conditions is widely used in several algorithms and problem-solving paradigms:

1. Partitioning in Quick Sort: The core idea of quicksort involves partitioning an array so elements less than a pivot go to one side, and elements greater than the pivot go to the other.

2. Dutch National Flag Problem: Used in sorting algorithms like 3-way QuickSort, this construct is extended to segregate an array into three parts.

3. Two Pointer Technique: Problems involving finding a pair of elements that meet specific criteria often use a similar construct.

4. Balancing in Machine Learning Data Sets: When you have an imbalanced dataset, you might use similar logic to segregate data before resampling.

5. Caching Algorithms: Least Recently Used (LRU) or Most Recently Used (MRU) cache replacement algorithms may use a similar construct to move frequently or recently used items closer to the top of a list or array.

6. Stream Data Processing: In real-time data streams, similar constructs are often used to segregate or partition incoming data into various buckets for quicker processing.

7. Memory Management: In low-level programming, similar constructs can be used for partitioning memory blocks into used and free.

8. Collision Resolution in Hashing: Open addressing schemes like linear probing, quadratic probing use a similar idea to find the next available slot.

9. Load Balancing: Similar constructs can be used to distribute tasks across multiple servers based on their load.

10. Graph Algorithms: In algorithms like Dijkstra’s or Floyd-Warshall, similar constructs can be used to maintain a set of visited nodes.

This construct is versatile and forms the backbone of many complex operations in computer science.