Problem Statement: Sort Colors using Bubble Sort

Description:

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 using Bubble Sort.
some companies that have asked the "Sort Colors" problem in their interviews-

• Google
• Amazon
• Microsoft
• facebook

Example 1:

Input: nums = [2,0,2,1,1,0]
Output = [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output = [0,1,2]

Constraints

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

Output Format

Return a integer array

Now try it yourself
.
.
.
.
.
.
.
.
.
.
.
.

Solution in C:

#include<stdio.h>
#include<stdlib.h>

int* sortColors(int* nums, int n){
   for(int i=0; i<n-1; i++){
        for(int j=0; j<n-1-i; j++){
             if(nums[j+1] < nums[j]){
                 int temp = nums[j];
                 nums[j] = nums[j+1];
                 nums[j+1] = temp;
             }
        }
    }
    return nums;
}

void m1(){
   int nums[6] = {2,0,2,1,1,0};
   int n = 6;
   int* result = sortColors(nums,n);
}

Solution in JAVA:

class Solution{

    public int[] sortColors(int[] nums){
        int n = nums.length;
        for(int i=0; i<n-1; i++){
            for(int j=0; j<n-1-i; j++){
                if(nums[j+1]<nums[j]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
             }
         }
         return nums;
    }

    public static main(String[] args){
        int nums = {2,0,2,1,1,0};
        Solution solve = new Solution();
        int[] result = solve.sortColors(nums);
    }
}

Solution in C++:

#include<bits/stdc++.h>
using namespace std;
void sort_colors(int nums[],int n){
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1-i;j++){
            if(nums[j]>nums[j+1]){
                int temp=nums[j];
                nums[j]=nums[j+1];
                nums[j+1]=temp;
            }
        }
    }
}
int main(){
    int nums[]={2,0,2,1,1,0};
    sort_colors(nums,6); //6 is the size of array 
    cout<<"result is"<<endl;
    for(int i=0;i<6;i++)
    cout<<nums[i]<<" ";
}

Time Complexity: O(n^2)
Space Complexity: O(1)

Explanation:

• Initializes an array nums with the values [2, 0, 2, 1, 1, 0].

• Then calls the sortColors method and stores the sorted array in the variable result.

• The length of the array nums is stored in the variable n.

• The outer loop runs from 0 to n-2, indicating the number of passes required to sort the array.

• The inner loop runs from 0 to n-2-i. With each pass of the outer loop, the range of the inner loop decreases by one, because the largest element gets placed in its correct position.

• Adjacent elements are compared, If nums[j+1] is less than nums[j], they are swapped to place the smaller element before the larger one.

• After the loops complete, the sorted array nums is returned.

Follow Up Question: Without bubble sort Can you reduce the time complexity of this function
.
.
.
.
Hint : Count the Occurence using mapping.
Try it Yourself...

Concept of Bubble Sort Click here.
For more interview problems Click here.

Happy Coding!