重排数组使负元素在正元素之前

1. Introduction

In this tutorial, we’ll show how to arrange a numeric array so that its negative elements come before its positive ones.

In doing so, we’ll require the solution to keep the relative order of the same-sign elements.

2. Problem Statement

Let’s say we have an array $a=[a_1, a_2, \ldots, a_n]$ . Our goal is to rearrange it into $a'=[a_1', a_2', \ldots, a_k', a_{k+1}', \ldots, a_n']$ so that all elements a_j for $j \leq k$ are negative, and all that come after a_k , if any, are positive.

Simultaneously, we want to keep the relative order in the negative and positive sub-arrays. So, for any i < j , it should hold that a_i' < 0 and a_j' > 0 or that sign(a_i')=sign(a_j') , but a_i' was to the left of a_j' in the original array.

For example, if a = [10, -2, 30, -4, 1, -20, 3, -40] , the correct rearrangement is a'=[-2, -4, -20, -40, 10, 30, 1, 3] .

Since sign(0)=1 , we’ll include any element equal to zero in the positive sub-array.

3. The Solution With Two Queues

We can start with two empty queues: queue_+ for the positive and queue_- for the negative elements of . We populate them by iterating over $\boldsymbol{a}$ and placing its elements into the queues based on their signs.

After that, we append queue_+ to queue_- to get :

algorithm SolutionWithQueues(a):
    // INPUT
    //    a = a numeric array [a1, a2, ..., an]
    // OUTPUT
    //    The array containing the elements of a sorted according to their signs 
    //    while keeping the relative order of the same-sign numbers.

    queue_negative , queue_positive <- make two empty queues

    for i <- 1, 2, ..., n:
        if a[i] < 0:
            Put a[i] into queue_negative
        else:
            Put a[i] into queue_positive

    a` <- append queue_positive to queue_negative
    
    return a`

Since we iterate over the input array once and concatenate two queues whose sizes sum to , the time complexity is $\boldsymbol{O(n)}$ . The only requirement is that storing a number in a queue be a constant-time operation.

The space complexity is also linear because we need O(n) space for and O(n) memory for queues.

4. The Solution With Merging

If we don’t want to take O(n) extra memory, we can rearrange the array using an algorithm similar to MergeSort.

First, we split the array into pairs of consecutive elements:

$[[a_1, a_2] [a_3, a_4] \ldots [a_{n-1}, a_n]]$

If is odd, we’ll let [a_n] be the last sub-array. For simplicity, we’ll assume is even since that won’t affect the correctness of this approach but will make it easier to explain.

In the next step, we swap the elements in each sub-array if the first one is positive and the second negative. So, we ensure that the signs are:

$[[-, +] [-, +] \ldots [-, +]]$

Afterward, we merge and arrange consecutive pairs of previously processed sub-arrays. That way, we arrange sub-arrays with four elements:

$[[-, -, +, +], [-, -, +, +], \ldots, [-, -, +, +]]$

Processing larger and larger sub-arrays, we eventually get to rearrange the entire input array .

4.1. Merging Two Sub-Arrays

Let’s focus on two consecutive sub-arrays of in an iteration of the rearrangement process:

[[L_- L_+ ] [R_- R_+]]

Let L_- be the left’s sub-array negative part, and let L_+ contain its positive elements. Similar goes for the right sub-array and its parts R_- and R_+ .

To merge the two sub-arrays to be in line with our requirements, we need to swap $\boldsymbol{L_+}$ with $\boldsymbol{R_-}$ while preserving relative orders in both:

[[L_- R_- L_+ R_+]]

First, we reverse $\boldsymbol{L_+}$ and $\boldsymbol{R_-}$ separately. Then, we reverse them together. To see why that works, let $L_+=[a_i, a_{i+1}, \ldots, a_{j}]$ and $R_-=[a_{j+1}, a_{j+2}, \ldots, a_r]$ .

So, we start with this:

$[a_i, a_{i+1}, \ldots, a_{j-1}, a_j, a_{j+1}, a_{j+2}, \ldots, a_{r-1}, a_r]$

If we first reverse the sub-arrays separately, we get:

$[a_j, a_{j-1}, \ldots, a_{i+1}, a_i, a_r, a_{r-1}, \ldots, a_{j+2}, a_{j+1}]$

Reversing them together gives us:

$[a_{j+1}, a_{j+2}, \ldots, a_r, a_i, a_{i+1}, \ldots, a_j]$

which is what we want to achieve.

4.2. Iterative MergeArrange

Let $a[i, \ldots, j]$ ( $i \leq j$ ) be the sub-array containing the elements of starting with a_i and ending with a_j (if j>n , it stops at a_n ). Here’s the pseudocode of our iterative MergeSort-like approach we call MergeArrange:

algorithm MergeArrange(a):
    // INPUT
    //    a = an array of numbers
    // OUTPUT
    //    The array containing the elements of a sorted according to their signs 
    //    while keeping the relative order of the same-sign numbers.

    l <- 1  // the length of sub-arrays
    m <- ceiling(n / 2)  // the number of sub-arrays

    while m > 1:
        for i <- 1, 1 + 2l, 1 + 4l, ..., 1 + 2l floor(n / 2ℓ):
            Reverse(a[i : i + l - 1])
            Reverse(a[i + l : i + 2l - 1])
            Reverse(a[i : i + 2l - 1])

        ℓ <- 2l
        m <- ceiling(n / l)

    return a

algorithm Reverse(a, i, j):
    // INPUT
    //    a = an array to be reversed
    //    i = starting index of the sub-array
    //    j = ending index of the sub-array
    // OUTPUT
    //    None

    left <- i
    right <- j

    while left < right:
        swap a[left] with a[right]
        left <- left + 1
        right <- right - 1

We start with sub-arrays of length $\boldsymbol{\ell = 1}$ to sort the consecutive pairs. Then, we double the length iteratively until covering the entire array.

In each iteration, the left sub-arrays for merging start at indices $1 + 2k \ell$ for some integer $k = 1, 2, \ldots, \lfloor n / 2\ell \rfloor$ since two consecutive sub-arrays together contain $2\ell$ elements. The corresponding right sub-arrays start at $\ell$ elements to the right.

4.3. Example

Let’s use the example from the start:

[a = [10, -2, 30, -4, 1, -20, 3, -40]]

In the first iteration, $\ell=1$ , so we have this split:

[[10] [ -2] [30] [ -4] [1] [-20] [3] [-40]]

After merging, we get:

[[-2, 10] [-4, 30] [-20, 1] [-40, 3]]

In the second iteration, $\ell=2$ , so we merge and arrange the consecutive pairs:

[[-2, -4, 10, 30] [-20, -40, 1, 3]]

In the third iteration, $\ell=4$ , so we process the remaining two sub-arrays of length 4:

[[-2, -4, -20, -40, 10, 30, 1, 3]]

Now, we get $\ell=8$ . That means there’s only one sub-array, i.e., the entire array. Therefore, we stop since it’s in the order we want it to be.

4.4. Complexity

There are at most $O(\log n)$ iterations, each of which makes at most swaps. So, the time complexity is $\boldsymbol{O(n \log n)}$ .

We use only a constant number of auxiliary variables for looping and swapping, so the extra space complexity is $\boldsymbol{O(1)}$ . However, the total space complexity is still $\boldsymbol{O(n)}$ since we need O(n) memory to store the initial array.

So, our MergeArrange algorithm has the same complexity as MergeSort. That isn’t a surprise because it works like bottom-up MergeSort sorting its input array using $sign(a_i) \cdot i$ instead of the actual values a_i .

In fact, any stable sorting algorithm using $sign(a_i) \cdot i$ to sort the a_i will do the job.

5. Conclusion

In this article, we showed two ways to rearrange a numeric array so that its negative elements get before its positive ones and those equal to zero, keeping the relative order of the elements in the same sub-array.

Our first solution uses two queues and runs in O(n) time and space. The algorithm we derived from MergeSort uses O(1) additional memory but runs in $O(n \log n)$ time.

Persistence

REST

Security