In this article, we have explained two efficient approaches to Move even number to front of array using Hoare's Partition and Lomuto Partition.

Table of content:

1. Problem Statement
2. Approach 1: Using Hoare's Partition
3. Approach 2: Using Lomuto Partition

Let us understand and solve this problem.

Problem Statement

Given an array of positive numbers, partition the array in such a way that all even numbers are at the front of array.

Example:

Input : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Output: {2, 4, 6, 8, 10, 1, 3, 5, 7, 9}

Note: Relative Ordering among even numbers and odd numbers doesn't matter.

Another Solution:
{2, 6, 4, 10, 8, 1, 3, 7, 9, 5}
Following Outputs are wrong.
{1, 3, 5, 7, 9, 2, 4, 6, 8, 10}
{2, 1, 4, 3, 6, 5, 8, 7, 10, 9}

The problem is similar to Segregate 0s and 1s and could be solved using variation of Dutch National Flag Algorithm.

Various Partition Schemes

This problem can be solved using a Partition scheme such as:

1. Hoare's Partition
2. Lomuto Partition

Approach 1: Using Hoare's Partition

It is based upon Two-Pointer Method, pointers start and end are initialized to both ends of an array and move towards each other until inversion occurs, odd number at left side and even number at right side. Swap operation performed at inversion and process repeats until start less than end.

Algorithm / Steps:

1. Initialize i = low and j = high.
2. Increment i by 1 until element present at i is even.
3. Decrement j by 1 until element present at i is odd.
4. Swap element present at i with element present at j.
5. Repeat steps 2-4 until i less than j.

Code:

def segregateEvenOdd(arr):
    j = 0
    i = len(arr) - 1
    
    while i < j:
        while i<len(arr) and arr[i]%2 == 0:
            i = i + 1
        
        while j>=0 and arr[j]%2 != 0:
            j =  j - 1
        
        if i < j :
            swap(arr[i],arr[j])  

Example:

Input: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Swaps performed: 0

1 2 3 4 5 6 7 8 9 10
|                  |
i                  j

Swaps performed: 0 + 1 = 1

10 2 3 4 5 6 7 8 9 1
|                  |
i                  j

Swaps performed: 1

10 2 3 4 5 6 7 8 9 1
     |             |
     i             j

Swaps performed: 1

10 2 3 4 5 6 7 8 9 1
     |         |
     i         j

Swaps performed: 1 + 1 = 2

10 2 8 4 5 6 7 3 9 1
     |         |
     i         j

Swaps performed: 2

10 2 8 4 5 6 7 3 9 1
         |     |
         i     j

Swaps performed: 2

10 2 8 4 5 6 7 3 9 1
         | |
         i j

Swaps performed: 2 + 1 = 3

10 2 8 4 6 5 7 3 9 1
         | |
         i j
END

There are more number of comparison operations but less swap operations. Hence, it is more efficient method but difficult to understand as compared to Lomuto Partition.

Time Complexity: O(N), where N is length of array

Space Complexity:: O(1)

Approach 2: Using Lomuto Partition

Instead moving pointers from both ends, we move from low to high position of array. As we iterate through the array, we swap the even elements with sliding target index. A sliding target index is a partition index that segregates even and odd elements,initially it points to -1.

Algorithm / Steps:

1. Initialize sliding_index = low - 1 as initially no even elements present in left sub array and i = low.
2. Check whether element present at i, is even or odd.
3. If even, increase sliding_index by 1 and swap element present at sliding_index and at i.
4. Else, do nothing.
5. Increment i by 1.
6. Repeat steps 2 - 5 until i is less than or equal to high.

Code:

def segregateEvenOdd(arr):
    sliding_indx = -1
    
    for i in range(0,len(arr)):
 
        if arr[i]%2 == 0:
            sliding_indx = sliding_indx + 1
            swap(arr[i],arr[sliding_indx])
            

Example:

Input: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Let sliding indx be i, and iterator be j

Swaps performed: 0

  1 2 3 4 5 6 7 8 9 10
| |
i j

Swaps performed: 0

  1 2 3 4 5 6 7 8 9 10
|   |
i   j

Swaps performed: 0 + 1 = 1

  2 1 3 4 5 6 7 8 9 10
  | |
  i j

Swaps performed: 1

  2 1 3 4 5 6 7 8 9 10
  |   |
  i   j

Swaps performed: 1

  2 1 3 4 5 6 7 8 9 10
  |     |
  i     j

Swaps performed: 1 + 1 = 2

  2 4 3 1 5 6 7 8 9 10
    |   |
    i   j

Swaps performed: 2

  2 4 3 1 5 6 7 8 9 10
    |     |
    i     j

Swaps performed: 2

  2 4 3 1 5 6 7 8 9 10
    |       |
    i       j

Swaps performed: 2 + 1 = 3

  2 4 6 1 5 3 7 8 9 10
      |     |
      i     j

Swaps performed: 3

  2 4 6 1 5 3 7 8 9 10
      |       |
      i       j

Swaps performed: 3

  2 4 6 1 5 3 7 8 9 10
      |         |
      i         j

Swaps performed: 3 + 1 = 4

  2 4 6 8 5 3 7 1 9 10
        |       |
        i       j

Swaps performed: 4

  2 4 6 8 5 3 7 1 9 10
        |         |
        i         j

Swaps performed: 4

  2 4 6 8 5 3 7 1 9 10
        |           |
        i           j

Swaps performed: 4 + 1 = 5

  2 4 6 8 10 3 7 1 9 5
          |          |
          i          j
END

Lomuto Partition is easy to implement and understand. But it is slower as compared to Hoare's Partition as more number of swap operations are performed.

Time Complexity: O(N), where N is length of array

Space Complexity:: O(1)

With this article at OpenGenus, you must have the complete idea of how to Move even number to the front of the array. Enjoy.