Win a copy of Java EE 8 High Performance this week in the Java/Jakarta EE forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

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

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

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 ?

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)

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 ]

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

Rancher
Posts: 42975
76

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.

Sheriff
Posts: 21208
87
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.

 mooooooo ..... tiny ad .... The WEB SERVICES and JAX-RS Course https://coderanch.com/t/690789/WEB-SERVICES-JAX-RS