How to Sort Array By Parity?


Given an array of non-negative integers, re-arrange the numbers so that the even numbers come before the odd numbers. You may return any answer that satisfy the condition. If half of the array are even and another half are odd, you may also do a index parity sorting on the array.

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Two List Implementation

We can have two lists: one to store the odd numbers and the other to store the even numbers. By iterating the original array of numbers, we push each number to corresponding list and at last, we just need to append the odd list to the even list.

The runtime complexity is O(N) and the space complexity is also O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        vector<int> even;
        vector<int> odd;
        for (const auto &n: A) {
            if (n % 2 == 0) {
                even.push_back(n);
            } else {
                odd.push_back(n);
            }
        }
        even.insert(even.end(), odd.begin(), odd.end());
        return even;
    }
};
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        vector<int> even;
        vector<int> odd;
        for (const auto &n: A) {
            if (n % 2 == 0) {
                even.push_back(n);
            } else {
                odd.push_back(n);
            }
        }
        even.insert(even.end(), odd.begin(), odd.end());
        return even;
    }
};

Customize Sorting

We can use std::sort to do the customized sorting by giving it a function to compare two elements. The Complexity is O(n logn). The odd numbers are after the even numbers if we compare the modules.

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        std::sort(A.begin(), A.end(), [](auto &a, auto &b) { 
            return a%2 < b%2;            
        });
        return A;
    }
};
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        std::sort(A.begin(), A.end(), [](auto &a, auto &b) { 
            return a%2 < b%2;            
        });
        return A;
    }
};

C++ Partition Algorithm

C++ standard library has a partition method that allow you to partition a list of elements based on a boolean function.

1
2
3
4
5
6
7
8
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        auto is_even = [] (auto e) { return e % 2 == 0; };
        partition (A.begin (), A.end (), is_even);
        return A;
    }
};
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        auto is_even = [] (auto e) { return e % 2 == 0; };
        partition (A.begin (), A.end (), is_even);
        return A;
    }
};

Two Pointers

We can scan from both ends of the array, swap them if not in place. The complexity is O(N) and the space complexity is O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        int i = 0, j = A.size() - 1;
        while (i < j) {
            while ((i < j) && (A[i] % 2 == 0)) ++ i;
            while ((i < j) && (A[j] % 2 == 1)) -- j;
            swap(A[i], A[j]);
            i ++; 
            j --;
        }
        return A;
    }
};
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        int i = 0, j = A.size() - 1;
        while (i < j) {
            while ((i < j) && (A[i] % 2 == 0)) ++ i;
            while ((i < j) && (A[j] % 2 == 1)) -- j;
            swap(A[i], A[j]);
            i ++; 
            j --;
        }
        return A;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
465 words
Last Post: A Nice Alternative for PuTTY: Termius - A very nice portable SSH connection tool
Next Post: Compute the Maximum Product of Three Numbers in an Array

The Permanent URL is: How to Sort Array By Parity?

Leave a Reply