my dog learned polymorphism*
The moose likes Beginning Java and the fly likes what's the best way to sort primitive array ? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "what Watch "what New topic
Author

what's the best way to sort primitive array ?

Bharat Makwana
Ranch Hand

Joined: May 21, 2007
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


ॐ सर्वे जना: सुखिनो भवन्तु , तथास्तु |
'May the whole world be happy, so be it'

SCJP1.5, SCWCD1.5
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14687
    
  16

Arrays.sort


[My Blog]
All roads lead to JavaRanch
Bharat Makwana
Ranch Hand

Joined: May 21, 2007
Posts: 107
Originally posted by Christophe Verre:
Arrays.sort

Thanks you Christophe.

That was my answer , when I was asked this question.
But I was asked to write logic and which algoritham to use ?
Gaurav Faujdar
Greenhorn

Joined: Apr 11, 2007
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

Joined: May 21, 2007
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)


Thanks, Anyone else with better solution,please take time to reply.
Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3477
    
  13
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 ]

Joanne
bart zagers
Ranch Hand

Joined: Feb 05, 2003
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
Marshal

Joined: Mar 22, 2005
Posts: 41592
    
  55
Originally posted by Bharat Makwana:
Thanks, Anyone else with better solution,please take time to reply.

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.


Ping & DNS - my free Android networking tools app
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19674
    
  18

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 ]

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Bharat Makwana
Ranch Hand

Joined: May 21, 2007
Posts: 107
Thank you everyone for your time.

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

Thanks again.
Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3477
    
  13
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

Joined: Feb 05, 2003
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.
 
 
subject: what's the best way to sort primitive array ?