Sort Colors ใน Python - เรียงสี (Dutch National Flag Problem)

สมมติว่าเรามีอาร์เรย์ที่มี n อ็อบเจกต์ สีแดง ขาว หรือ น้ำเงิน เรียงในที่เดิม (in-place) ให้อ็อบเจกต์สีเดียวกันอยู่ติดกัน ตามลำดับสี แดง ขาว น้ำเงิน ใช้ตัวเลข 0, 1, 2 แทนสีแดง ขาว น้ำเงิน ตามลำดับ ตัวอย่าง [2,0,2,1,1,0] ผลลัพธ์ [0,0,1,1,2,2]

ขั้นตอนการทำงาน (Three-way Partition / Dutch National Flag)

1. ตั้งค่า low := 0, mid := 0, high := length of array - 1
2. วนลูป while mid <= high:
   • ถ้า arr[mid] = 0 สลับ arr[mid] และ arr[low] เพิ่ม low และ mid 1
   • ถ้า arr[mid] = 2 สลับ arr[high] และ arr[mid] ลด high 1
   • มิฉะนั้น (คือ 1) เพิ่ม mid 1

ตัวอย่างโค้ด (Python)

class Solution(object):
    def sortColors(self, nums):
        low = 0
        mid = 0
        high = len(nums) - 1
        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 2:
                nums[high], nums[mid] = nums[mid], nums[high]
                high -= 1
            else:
                mid += 1
        return nums

ob1 = Solution()
print(ob1.sortColors([2,0,2,1,1,0]))

อินพุต

[2,0,2,1,1,0]

เอาต์พุต

[0,0,1,1,2,2]