# what's the best way to sort primitive array ?

Bharat Makwana
Ranch Hand
Posts: 107
Hi Ranchers !!

Can anybody tell me, what the best way to sort a primitive array,which contains only 1(one) and 0(zero) as it's element ?

Thanks & Regards
Bharat

Christophe Verré
Sheriff
Posts: 14691
16
Arrays.sort

Bharat Makwana
Ranch Hand
Posts: 107
Originally posted by Christophe Verre:
Arrays.sort

Thanks you Christophe.

But I was asked to write logic and which algoritham to use ?

Gaurav Faujdar
Greenhorn
Posts: 7
just loop through the array count the occurances of 1's or 0's and fill the array. you should have sorted array in O(n)

Bharat Makwana
Ranch Hand
Posts: 107
Originally posted by Gaurav Faujdar:
just loop through the array count the occurances of 1's or 0's and fill the array. you should have sorted array in O(n)

Joanne Neal
Rancher
Posts: 3742
16
Here's a different solution. I doubt it's better than Gaurav's, which seems about as simple as you can get to me.

[ September 04, 2007: Message edited by: Joanne Neal ]

bart zagers
Ranch Hand
Posts: 234
1 Step from the start to the first '1'
2 Step from the end to the first '0'
3 exchange both
4 goto 1 until the counters/steppers pass each other

Ulf Dittmer
Rancher
Posts: 42968
73
Originally posted by Bharat Makwana:

You should define what a "better" solution would look like. Sort algorithms are most often measured in time complexity, and you won't get much faster than what Gaurav mentioned.

Rob Spoor
Sheriff
Posts: 20671
65
I have just tested both methods and overall the counting then filling is slower, although for an array size of 10.000.000 the difference is a mere 50ms at most.

I have also tried Arrays.sort, and it is about twice as slow as the second method, and 33% slower than the first. This is logically, because it cannot use the fact that the array only stores zeros and ones.
[ September 04, 2007: Message edited by: Rob Prime ]

Bharat Makwana
Ranch Hand
Posts: 107
Thank you everyone for your time.

So I think Gaurav's solution is best in this case.

Thanks again.

Joanne Neal
Rancher
Posts: 3742
16
Rob - you don't need to swap the values in the two elements because you already know the values.
i.e. you can change the last part of the loop to

Although you should also check in the two inner while loops that the index is not negative, to handle the case where the array contains all zeros or all ones. Alternatively you could just put the outer while loop in a try/catch IndexOutOfBoundsException block.
[ September 04, 2007: Message edited by: Joanne Neal ]

bart zagers
Ranch Hand
Posts: 234
In the counting solution, it is also not needed to count the 1's.
Just the 0's and the total length will do.