CODEWITHSUNDEEP
arraysalgorithmperformancebig-o
Manjeet Rulhania
Manjeet Rulhania

Reputation: 81

Arrange odd numbers first, followed by even number. order of odd even should not be changed

Below is code snippet to reorder odd numbers followed by even numbers without changing the order of even/odd numbers in original array.

input - {1, 4, 8, 3, 9, 12, 7} output - {1, 3, 9, 7, 4, 8, 12}

Can We improve this from O(n2) in space (without using extra space)?

public  static void reOrder(int[] arr) {
     int evenIndex  = arr.length;
     for(int i=0; i < arr.length;i++) {
            if(arr[i] % 2 == 0 && evenIndex == arr.length) //even index
                evenIndex = i;

            else if( arr[i] % 2 != 0 ) {
                if(i > evenIndex ) {
                    shift (arr, evenIndex , i);
                    evenIndex ++;
                }
            }
     }
}

static void shift(int[] arr, int evenIndex, int endIndex) {
    int temp = arr[endIndex];
    for(int i = endIndex; i > evenIndex ;i --) {
        arr[i] = arr[i-1];
    }
    arr[evenIndex] = temp;
}

Upvotes: 2

Views: 978

Answers (2)

wcochran
wcochran

Reputation: 10896

Stable partition is what you are looking for

std::vector<int> l = {1, 4, 8, 3, 9, 12, 7};
std::stable_partition(l.begin(), l.end(),
                      [](int A) -> bool {
                          return (A & 1) == 1; // A is odd
                      });

Exactly N applications of the predicate and O(N) swaps if there is enough extra memory. O(N log N) swaps and O(N) applications of the predicate

Question on how stable partition works along with its complexity.

A stable quick sort, for example, will use a stable partitioning under the hood. Check out the accepted answer here for an O(n*log(n)) implementation of a stable partition algorithm that is beautifully recursive.

Upvotes: 2

ChatterOne
ChatterOne

Reputation: 3541

You didn't specify any language tag, so I'll answer using python (just because it's quicker for me to use it at the moment).

If you only care about space complexity you can do something like this:

l = [1, 4, 8, 3, 9, 12, 7]
even_index = -1

for index in range(0, len(l)):
    if (l[index] % 2) == 0:
        if even_index == -1:
            even_index = index
    else:
        if (index > 0) and (even_index > -1):
            num = l[index]
            l.insert(even_index, num)
            del l[index + 1]
            even_index += 1
print(l)

You keep an index of where the first even number is and insert the odd number as you find them going through the list. Then you remove the odd number at the "old" index (which is now increased by 1).

I think the space complexity is what you need, but the time complexity can be improved.

For example, in Python a collections.deque is probably better in this case, but time complexity was not a priority.

Upvotes: -1

Related Questions