Counting Sort is a linear sorting algorithm that works well when the range of input values is known and relatively small. In this case, you want to sort an array of colors represented by numbers 0, 1, and 2. Here’s how you can implement Counting Sort in Python to sort the colors in-place:
def sortColors(nums):
# Count the occurrences of each color
count = [0] * 3
# Count the occurrences of each color in the input array
for color in nums:
count[color] += 1
# Update the input array with sorted colors
index = 0
for i in range(3):
for _ in range(count[i]):
nums[index] = i
index += 1
# Example usage:
colors = [2, 0, 1, 2, 0, 1, 0, 2, 1, 1, 0, 2]
sortColors(colors)
print("Sorted Colors:", colors)
In this example, the sortColors function takes an array nums containing colors represented by numbers 0, 1, and 2. It initializes a count array to count the occurrences of each color (0, 1, 2). Then, it updates the input array with the sorted colors based on the count of occurrences.
After running this code, the colors array will be sorted in-place, and you can print the result to verify the sorting. Adjust the input array as needed for your specific use case.
Following are unit tests for this code:
import unittest
def sortColors(nums):
count = [0] * 3
for color in nums:
count[color] += 1
index = 0
for i in range(3):
for _ in range(count[i]):
nums[index] = i
index += 1
class TestSortColors(unittest.TestCase):
def test_sort_colors(self):
# Test case 1
colors_1 = [2, 0, 1, 2, 0, 1, 0, 2, 1, 1, 0, 2]
sortColors(colors_1)
self.assertEqual(colors_1, [0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2])
# Test case 2
colors_2 = [1, 0, 2]
sortColors(colors_2)
self.assertEqual(colors_2, [0, 1, 2])
# Test case 3
colors_3 = [2, 2, 2, 1, 1, 1, 0, 0, 0]
sortColors(colors_3)
self.assertEqual(colors_3, [0, 0, 0, 1, 1, 1, 2, 2, 2])
# Add more test cases as needed
if __name__ == '__main__':
unittest.main()
In this example, the TestSortColors class inherits from unittest.TestCase, and the test_sort_colors method defines individual test cases. The assertEqual method is used to check if the actual result matches the expected result after calling sortColors. You can add more test cases as needed to thoroughly test your sorting function.
To run the tests, save this script and execute it. If there are any issues with the sortColors function, the test cases will help identify them.