Tuesday, May 3, 2011

Sort an array of 0, 1, 2, 3 symbols

with no additional memory and in linear time


  1. Count how many every symbol occurs in set, then output required amount of ones, twos, threes and fours?

  2. I was thinking about this: start from left and right and swap (2,3) on left with (0,1) on the right. After one pass we will have (0,1)s on the left and (2,3)s on the right. Then repeat same thing on these sub-arrays (swapping 1-0s and 3-2s). However I would need two indices.