Sorting an array containing three elements only

general
, ,
1

Give an array of length 10^7 but having only three elements R,G,B …What is the best approach to sort it in least time and space complexity…
one of the methods is memory map…I got to know that this question has multiple solutions

2

There are many approaches to the problem.

  • Iterate through the array and keep three counts, countr,countb,countg. You have these three counts now. Set the first countr entries in the string to R, next countg to G and then rest to B.
  • Use counting sort, it’ll not add on to the space compelxity becuase we need an array of just three elements. So, constant space and linear time.
  • Binary tree can be used
  • Its a famous problem called by the
    name Dutch National Flag problem
    which is very well explained
    here.
3

thanks @damn_me …you are very knowledgeable …I was searching for the last solution …But it would be great if you please explain me your second solution about counting sort

1 Like
4

See this code for the counting sort:

If we’ll go the very same way we go in counting sort, then we’ll get this, currently it has O(n) space complexity.

cin>>n;
int i,a[n+1];
int cnt[4]={0};  // it adds to auxillary space, not space complexity.
for(i=0;i<n;i++)
 {
 	cin>>a[i];
 	cnt[a[i]]++;
 }
 
 for(i=1;i<=2;i++)
  {
  	cnt[i]+=cnt[i-1];  // calculating cumulative frequency
  	//cout<<cnt[i]<<" ";
  }
 
 int b[n+1];
 
 for(i=n-1;i>=0;i--)
 {
 	b[cnt[a[i]]-1]=a[i];   // the very same thing we do in counting sort
 	cnt[a[i]]--;
 }
// instead of the above loop, we could have done this in array a[] itself, because we now know the //cumulative counts of all three, the very same way by separately counting.
 for(i=0;i<n;i++)
  cout<<b[i]<<" ";

Let me know if anything is unclear… :slight_smile:

5

@nickzuck_007 See below…