Chương trình sắp xếp mảng dựa trên giá trị chẵn lẻ (parity) trong Python

Giả sử chúng ta có một mảng A với một số số nguyên. Chúng ta phải sắp xếp các số theo thứ tự chẵn rồi lẻ. Nghĩa là đặt các số chẵn lên trước, sau đó là các số lẻ. Vì vậy, nếu mảng là A = [1, 5, 6, 8, 7, 2, 3], thì kết quả sẽ là [6, 8, 2, 1, 5, 7, 3]

Để giải quyết, chúng ta thực hiện các bước sau:

• đặt i := 0 và j := 0
• trong khi j < kích thước mảng:
  • nếu arr[j] là chẵn:
    • hoán đổi arr[i] và arr[j],
    • tăng i lên 1
  • tăng j lên 1
• trả về arr

Đây là thuật toán phân hoạch (partition) giống như trong QuickSort, với điều kiện phân hoạch là số chẵn (arr[j] % 2 == 0). Con trỏ i đánh dấu vị trí tiếp theo để đặt số chẵn, j duyệt qua mảng.

Ví dụ

class Solution(object):
    def sortArrayByParity(self, a):
        i = 0
        j = 0
        while j < len(a):
            if a[j] % 2 == 0:
                a[i], a[j] = a[j], a[i]
                i += 1
            j += 1
        return a

ob1 = Solution()
nums = [1, 5, 6, 8, 7, 2, 3]
print(ob1.sortArrayByParity(nums))

Input

[1, 5, 6, 8, 7, 2, 3]

Output

[6, 8, 2, 5, 7, 1, 3]