X
Sorting Colors
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function. Constraints: n == nums.length 1 <= n <= 300 nums[i] is either 0, 1, or 2.
.jpg)
We can solve this problem using the Dutch National Flag algorithm, which is designed for sorting objects with three possible values. It works by maintaining three-pointers to keep track of the positions where the next 0, 1, and 2 should be placed.
Here is a Ruby Solution:
Here is a Ruby Solution:
def sort_colors(nums)
low = 0
high = nums.length - 1
current = 0
while current <= high
case nums[current]
when 0
nums[current], nums[low] =nums[low], nums[current]
low += 1
current += 1
when 1
current += 1
when 2
nums[current], nums[high] = nums[high], nums[current]
high -= 1
end
end
endThe first step is to initialize the three pointers: `low` for the position where the next 0 should go, `high` for the position where the next 2 should go, and current for traversing the array.
low = 0 high = nums.length - 1 current = 0
The second step is to Iterate through the array until the current pointer reaches or surpasses the high pointer.
while current <= high
The third step is to evaluate the value at the current position using a case statement.
case nums[current]
when 0
nums[current], nums[low] = nums[low], nums[current]
low += 1
current += 1
If the current value is 0 (red), swap it with the element at the low pointer, then increment both low and current pointers.
Continue this process until the current pointer crosses the high pointer.
The Dutch National Flag algorithm ensures that 0s are placed to the left, 2s are placed to the right, and 1s are automatically in the correct position as elements are processed. The array is sorted in-place with a single pass through the array.
Continue this process until the current pointer crosses the high pointer.
The Dutch National Flag algorithm ensures that 0s are placed to the left, 2s are placed to the right, and 1s are automatically in the correct position as elements are processed. The array is sorted in-place with a single pass through the array.