There are balls of red, blue and green color. How will you sort them…?
I just wanted to know the best stratergy for it…!
Thanks in advance.
-
use counting sort…
-
just put some value to each color
- i.e. red=0; blue=1;green=2;
example ; red green blue look like 0 2 1
-
and just take a hash[3]={0}
for(all balls not taken){ if(ball==red) hash[0]++; else if(ball==blue) hash[1]++; else hash[2]++; }
-
you will got to know how many red ball and how many blue and how many green
-
in which order you want put them as you know the frequency of each colored ball…
-
just do this way…to more info of counting sort…Counting sort
HAPPY CODING
Hey va1ts7_100,
firstly you should give different value to red, green and blue balls.
Suppose there are n number of balls.
We define array of of size 3 and initialize them to 0.
red=0
blue=1
green=2
while(n–)
{
scanf(ball color)
array[ball color]++
}
for(i=0 to 2)
{
for(j=1 to array[ball color])
{
if(i==0)
print(red ball)
else `if(i==1)
print(blue ball)
else
print(green ball)
}
}
i think above code should help you!
just give them values 0 ,1 and 2
then sort them using any nlogn complexity sort like merge sort…
or you can use the in-built sort function if you are using c++…
-
**ok if you want to efficient than do one thing make an empty array ***
-
assumption ie. red=0,blue=1,green=2;
-
make three variable
- r=0;
- g=totalnumberofballs-1;
- b=g-1;
put[totalnumber of balls]//empty list while(all ball not scanned){ if(ball==red){ put[r]=red; r++; } else if(ball==green){ if(put[g]==blue){ put[b]=blue; b-- } put[g]=green; g--; } else { put[b]=blue; b--; } }
HAPPY CODING
- you can do this also …
- i will post that solution soon…just wait…
- i came to know that solution too…
just wait…
- or you have to do some shift but it take more time than this…
- i will see…
it means after counting the frequency and then arranging them in some order (say red first, then blue, then green), minimum 2n comparisons required at least .!
thanks@deepkmourya
in this type of question firstly you should check if other way to sort which has less complexity than n*log(n) , if it clicks in your mind your code take less time as compared to others.
HAAPY CODING
ONLY n COMPARISION IS NEEDED…HOPE IT HELP YOU…
i could have done the same using 2 arrays by myself, but i was trying to achieve it in only 1 array…!! thanks for ur solution…