Solution For Sort Colors
Problem Statement:
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.
Example:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Algorithm:
The problem can be solved using a two-point approach. We need to choose two pointers namely low and high. We keep low pointer at the beginning and high pointer at the end of an array and then we traverse the array from the starting index until the low pointer reaches the end of the array. At each step, we compare the element at the low index with the element at the high index. If the element at the low index is 2, we swap it with the element at the high index and decrement the high index by 1. If the element at the low index is 0, we swap it with the element at the low index and increment the low index by 1. If the element at the low index is 1, we simply increment the low index by 1. This way we keep the red elements at the beginning, white elements in the middle, and blue elements at the end.
Code:
class Solution {
public:
void sortColors(vector
int low = 0, high = nums.size() – 1, mid = 0;
while(mid <= high) {
if(nums[mid] == 0) {
swap(nums[low], nums[mid]);
low++;
mid++;
}
else if(nums[mid] == 2) {
swap(nums[high], nums[mid]);
high–;
}
else {
mid++;
}
}
}
};
Time Complexity:
The time complexity of the above solution is O(n) as we need to traverse the array only once.
Space Complexity:
The space complexity of the above solution is O(1) as we are not using any extra space for sorting.
Step by Step Implementation For Sort Colors
class Solution {
// Function to sort the array
// arr: array to be sorted
// n: size of the array
void sortColors(int arr[], int n)
{
// Initialize counts of 0, 1 and 2
// as 0
int count0 = 0, count1 = 0, count2 = 0;
// Traverse all array elements and
// count number of 0's, 1's and 2's
for (int i = 0; i < n; i++) {
if (arr[i] == 0)
count0++;
if (arr[i] == 1)
count1++;
if (arr[i] == 2)
count2++;
}
// Now modify original array
// To put all 0's in array
int i = 0;
while (count0 > 0) {
arr[i++] = 0;
count0--;
}
// To put all 1's in array
while (count1 > 0) {
arr[i++] = 1;
count1--;
}
// To put all 2's in array
while (count2 > 0) {
arr[i++] = 2;
count2--;
}
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
int n = arr.length;
sortColors(arr, n);
System.out.println("Array after seggregation ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}"""
Given an array 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.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library's sort function for this problem.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
"""
def sortColors(nums):
"""
Do not return anything, modify nums in-place instead.
"""
# two pass algorithm using counting sort
# first pass: count number of 0's, 1's, and 2's
# second pass: fill array with total count of 0's, then 1's and followed by 2's
count = [0, 0, 0]
for i in range(len(nums)):
if nums[i] == 0:
count[0] += 1
elif nums[i] == 1:
count[1] += 1
else:
count[2] += 1
for i in range(len(nums)):
if i < count[0]:
nums[i] = 0
elif i < count[0] + count[1]:
nums[i] = 1
else:
nums[i] = 2var sortColors = function(nums) {
// create a map to store the count of each color
let colorCount = {
0: 0,
1: 0,
2: 0
}
// iterate over the array and increment the count for each color
for (let i = 0; i < nums.length; i++) {
colorCount[nums[i]]++;
}
// iterate over the array again and overwrite the values with the correct color in the correct order
let index = 0;
for (let color in colorCount) {
for (let j = 0; j < colorCount[color]; j++) {
nums[index] = parseInt(color);
index++;
}
}
};class Solution {
public:
void sortColors(vector& nums) {
int n = nums.size();
int i = 0, j = n - 1;
while (i < j) {
while (i < j && nums[i] <= nums[j]) {
i++;
}
swap(nums[i], nums[j]);
while (i < j && nums[i] <= nums[j]) {
j--;
}
swap(nums[i], nums[j]);
}
int k = 0;
while (k <= j) {
if (nums[k] == 0) {
swap(nums[k], nums[0]);
k++;
i++;
}
else if (nums[k] == 1) {
k++;
}
else {
swap(nums[k], nums[j]);
j--;
}
}
}
}; using System;
class GFG {
// Function to sort the array
// in wave form
static void sortInWave(int[] arr,
int n)
{
// Traverse the array
for (int i = 0; i < n; i++)
{
// If i is even, check
// if it is greater than
// its next element
if (i % 2 == 0)
{
// If yes, swap the elements
if (i < n - 1 && arr[i] > arr[i + 1])
{
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
// If i is odd, check if
// it is less than its
// next element
else
{
// If yes, swap the elements
if (i < n - 1 && arr[i] < arr[i + 1])
{
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
// Driver code
public static void Main()
{
int[] arr = { 10, 90, 49, 2, 1, 5, 23 };
int n = arr.Length;
sortInWave(arr, n);
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}