Sort Colors

1. Problem Description

Given an array with n elements colored red, white, and blue, sort them in place so that elements of the same color are adjacent, in the order red, white, and blue.

In this problem, the integers 0, 1, and 2 represent red, white, and blue respectively.

2. Approach

1. Approach 1
   • Quicksort
2. Approach 2
   • Bucket sort
3. Approach 3
   • Move Zeroes

3. Implementation

3.1. Quicksort

func sortColors(nums []int)  {
    quickSort(nums, 0, len(nums)-1)
}

func quickSort(nums []int, left, right int) {
    if left >= right {
        return
    }

    p := partition(nums, left, right)
    quickSort(nums, left, p-1)
    quickSort(nums, p+1, right)
}

func partition(nums []int, left, right int) int {
    pivot := nums[left]
    for left < right {
        for left < right && nums[right] >= pivot {
            right--
        }
        nums[left] = nums[right]
        for left < right && nums[left] <= pivot {
            left++
        }
        nums[right] = nums[left]
    }
    nums[left] = pivot
    return left
}

3.2. Bucket Sort

func sortColors(nums []int)  {
    bucket := []int{0,0,0}
    for _, num := range nums {
        bucket[num]++
    }
    i:=0
    for num, count := range bucket {
        for j := 0; j < count; j++{
            nums[i] = num
            i++
        }
    }
}

3.3. Move Zeroes

func sortColors(nums []int)  {
    index := 0
    for i:=0; i<len(nums); i++{
        if nums[i] == 0 {
            nums[i],nums[index] = nums[index],nums[i]
            index++
        }
    }
    for i:=index; i<len(nums); i++{
        if nums[i] == 1 {
            nums[i],nums[index] = nums[index],nums[i]
            index++
        }
    }

}

4. References

• Sort Colors - Sort Colors - LeetCode