How would you sort the following array?

[EngIntoHW]

Hi,
I'm using C language for programming.

Say that you got an array (of size N) that contains only '1's, '2's, '3's, randomly placed.

how would you sort the array to the following form:

1, 1, ..., 1, 2, 2, ..., 2, 3, ...., 3

without using a second array?

Any guidance would be appreciated

 

[3v0]

Use a bubble sort.

Simply step through the array comparing element n to n+1 and swap if n>n+1.
Repeat until you make a pass where no swap is required.

I am sure wikipedia has a better explanation.

 

[EngIntoHW]

Hey,

I got you.

However, isn't there a way to do it more efficiently, as you know that there are only 1s, 2s and 3s?

This question taken from a job interview, that's why I assume they expect you to use an efficient method considering the given data.

 

[Exo]

Loop trough the array, count the number of 1's, the number of 2's and the number of 3's.
Then start filling the array with the required number of 1's, 2's and 3's.


Something along these lines:

#define N  100   //size of the array to sort

unsigned char ArrayToSort[N];                    //the actual array
unsigned char Counters[3] = {0, 0, 0};        //another array to store the number of 1's, 2's and 3's - its not used to copy the first array's data over so i assume it's ok ?

void   Sort(void)
{
int a;
int b;

   for (a = 0; a < N; a++)
   {
          if (ArrayToSort[a] & 0xFC)               //and value with b'11111100' - if result is not 0 then there is a value other then 1,2 or 3 in the array
          {
              //Invalid value, other then 1, 2 or 3 in our array, handle error here.
          }
          Counters[ArrayToSort[a]]++;           //add one to the counter of the corresponding value
   }

   a = 0;
   b = 0;
   while (b < 3)
   {
        while (Counters[b])
        {
            ArrayToSort[a] = b + 1;
            Counters[b]--;
            a++;  
        }
        b++;
    }
}

 

[EngIntoHW]

Thank you,

Thats a very nice idea

 

[Pommie]

I like Exo's idea. However, if you want an actual sort method that will work with any values, use (what I call) an insert sort. It's the same as a bubble sort but when you find a value out of place you work backward, moving the data as you go, until you find where it fits. This method is much quicker as it only needs 1 pass whereas a bubble sort could require N-1 passes.

Mike.

 

[EngIntoHW]

Oh its great.

Thank you