aspose file tools*
The moose likes Programming Diversions and the fly likes Sort Numbers Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Sort Numbers" Watch "Sort Numbers" New topic
Author

Sort Numbers

atul kumar
Greenhorn

Joined: Nov 14, 2008
Posts: 7
There is a array of numbers that contains a mix of positive and negative numbers. For example -2, -3, 4, 5, -6, -100, 50. Write a program to arrange the numbers such that all negative numbers appear first and then the positive numbers appear, but the relative order in which the initial array was given is the same. You can only use the array provided and cannot define any new array or other data structures.


For example -2, -3, 4, 5, -6, -100, 50 will become -2, -3, -6, -100, 4,5,50.

is there any way to do this without using any new DS?

[ November 14, 2008: Message edited by: atul kr ]
[ November 17, 2008: Message edited by: Bear Bibeault ]
Nitesh Kant
Bartender

Joined: Feb 25, 2007
Posts: 1638

This topic better suites in Programming diversions.
Moved it for you.
CarefullyChooseOneForum


apigee, a better way to API!
Gabriel Claramunt
Ranch Hand

Joined: May 26, 2007
Posts: 375
Think on what's the difference between your problem and a standard sorting problem. How do you compare the elements?


Gabriel
Software Surgeon
Bill Shirley
Ranch Hand

Joined: Nov 08, 2007
Posts: 457
Yes.

if a reference to an item in the list is not a "new data structure", then many sort methods will do - use one that maintains previous sort order, and doesn't require additional data structures (most of the simpler ones don't)


Bill Shirley - bshirley - frazerbilt.com
if (Posts < 30) you.read( JavaRanchFAQ);
J. Noah
Greenhorn

Joined: Nov 15, 2008
Posts: 9
Insertion sort is a simple place to start...


<a href="http://blog.expensivedna.com" target="_blank" rel="nofollow">http://blog.expensivedna.com</a>
Gabriel Claramunt
Ranch Hand

Joined: May 26, 2007
Posts: 375
Almost any sorting algorithm will do if you replace the comparation function with something adequate to the problem (hint hint)
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18124
    
    8

Originally posted by atul kr:
the relative order in which the initial array was given is the same
It took me a long time to figure out what this requirement meant. From the example given, it was fairly apparent to me that the negative numbers were to be sorted in decreasing order at the beginning of the array, followed by the positive numbers in increasing order.

But now I don't think so. That phrase I quoted there would be meaningless if sorting was to be done. I think the real problem is to just push all the negative numbers to the left end of the array without sorting them and push all the positive numbers to the right end of the array without sorting them. It was just that the example given was horribly misleading.
Nitesh Kant
Bartender

Joined: Feb 25, 2007
Posts: 1638

Paul:
I think the real problem is to just push all the negative numbers to the left end of the array without sorting them and push all the positive numbers to the right end of the array without sorting them.


I am glad that I was not the only person thinking on those lines and I just got bogged down by the other replies!
Paul Yule
Ranch Hand

Joined: May 12, 2008
Posts: 229
I would keep track of however many positive numbers you've seen and when you come across a negative bubble it backwards in the array that many.
Nitesh Kant
Bartender

Joined: Feb 25, 2007
Posts: 1638

Paul:
I would keep track of however many positive numbers you've seen


Or the index of the last -ve number and bubble up any other -ve number to the index next to the last -ve number.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10915
    
  12

I think you could easily use any sort algorithm - you just need to adjust your compare. Pretty much any sort has you compare two numbers. But instead of "if a > b then swap", you'd want "if a is positive and b is negative then swap".


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Gabriel Claramunt
Ranch Hand

Joined: May 26, 2007
Posts: 375
Originally posted by fred rosenberger:
I think you could easily use any sort algorithm - you just need to adjust your compare. Pretty much any sort has you compare two numbers. But instead of "if a > b then swap", you'd want "if a is positive and b is negative then swap".

Bingo! That was what I was hinting.
For example, in java, you would implement the comparator interface but instead of comparing the values of the numbers, just compare the signs...
[ November 19, 2008: Message edited by: Gabriel Claramunt ]
Paul Yule
Ranch Hand

Joined: May 12, 2008
Posts: 229
I think you could easily use any sort algorithm - you just need to adjust your compare. Pretty much any sort has you compare two numbers. But instead of "if a > b then swap", you'd want "if a is positive and b is negative then swap".


I thought that might work at first too. However if I understand the problem correctly you would lose the order it started in if you simply swapped elements...everything would be on the correct side but you would lose the order they were at when you started. It's entirely possible I'm missing something.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10915
    
  12

I'm not sure I agree...

i think the array would bubble like this:


First pass done. The order of the negatives is still preserved, as are the positives. A second pass would leave you with

-2, -3, -6, -100, 4, 5, 50

ane then I think you're done.
Gabriel Claramunt
Ranch Hand

Joined: May 26, 2007
Posts: 375
Originally posted by Paul Yule:


I thought that might work at first too. However if I understand the problem correctly you would lose the order it started in if you simply swapped elements...everything would be on the correct side but you would lose the order they were at when you started. It's entirely possible I'm missing something.

As you never swap negatives with negatives or positives with positives, the order between them is preserved
Paul Yule
Ranch Hand

Joined: May 12, 2008
Posts: 229
Yes, for the bubble that's totally acceptable. It's partial of the algorithm I suggested as well with a small modification. However with some of the more efficient algorithm's you switch numbers (which aren't immediately next to each other)...as is the case with the quickSort.

I only meant to be careful to use any algorithm because you might get unexpected results.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10915
    
  12

ah... i guess we need to use a 'stable sort' algorithm with a modified compare routine.
Paul Yule
Ranch Hand

Joined: May 12, 2008
Posts: 229
I think that's the right idea.
Also,Did a post get deleted from here? I am able to peruse the forums in spurts and was going to come back and reply in this one, but it hath vanished.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Sort Numbers
 
Similar Threads
Arrays.binarySearch() query
My journey in SCWCD5.0
Please explain this array question to me
List of contiguous numbers
summing each row in a 2-dimensional array