# which sorting

This topic is 4284 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

suppose i have an array with elements as 0 and 1 only. What will be the best way(running time) to sort it. I thought about adding all elements and then filling arrays with no of 0's and then 1's. Is there any better method than this??

##### Share on other sites
You have a O(n) algorithm, it can't get any better than that in terms of time complexity.

This is how I would do it (assuming C++)
void sort(int* p, int size){    int* q = p;    while ( size-- != 0 )    {        if ( !*p++ )        {            *q++ = 0;        }    }    while ( p != q )    {        *q++ = 1;    }}

Two pointers are kept, one (p) scans over the entire array, and each time it encounters a 0, a 0 is written at *q, and q is moved one position to the right. After p has scanned over the entire array, q is used to change all remaining elements to 1.

##### Share on other sites
I guess my algorithm requires O(2n) time...isn't it

for(i=0;i<size;i++)                                            {                                                                          num += arr[i];                                                   }                                                                                                                                                      for(i=0;i<size-num;i++)                                    {                                                                             arr[i] =0;                                                           }                                                                                                                                                      for(i=num;i<size;i++)                                       {                                                                             arr[i] =1;                                                           }                             [/code]

##### Share on other sites
In a way, yes. But as far as I know, people consider O(n) = O(2n).
The algorithm I posted is O(2n) as well.

I wouldn't know which one of our algorithms performs better in practice.

##### Share on other sites
I profiled it with only 10 elements

Time taken little more than 3 ms -My Version
Time Taken apprx 9 ms -Your version

##### Share on other sites
Usually, for profiling to be accurate, you should test with various array's size (and a lot bigger than 10 elements)

- edit

And different array's setup (already sorted, 1-0-1-0-1-0..., random, etc.) to test worse case / best case scenarios!

##### Share on other sites
With 10000000 elements, using patterns [1,0,1,0,...], [1,1,1,...,0,0,0,...], [0,0,0,...,1,1,1,...] and [0,0,0,0,...], my version is faster, but not by much. Yours is faster with [1,1,1,1,...].

(Not that this way of benchmarking is in any way accurate...)

##### Share on other sites

This topic is 4284 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.