Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Sort Numbers

atul kumar
Greenhorn
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
Posts: 1638
This topic better suites in Programming diversions.
Moved it for you.
CarefullyChooseOneForum

Gabriel Claramunt
Ranch Hand
Posts: 375
Think on what's the difference between your problem and a standard sorting problem. How do you compare the elements?

Bill Shirley
Ranch Hand
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)

J. Noah
Greenhorn
Posts: 9
Insertion sort is a simple place to start...

Gabriel Claramunt
Ranch Hand
Posts: 375
Almost any sorting algorithm will do if you replace the comparation function with something adequate to the problem (hint hint)

Paul Clapham
Sheriff
Posts: 21443
33
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
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
Posts: 230
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
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
Posts: 12234
36
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".

Gabriel Claramunt
Ranch Hand
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
Posts: 230
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
Posts: 12234
36
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
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
Posts: 230
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
Posts: 12234
36
ah... i guess we need to use a 'stable sort' algorithm with a modified compare routine.

Paul Yule
Ranch Hand
Posts: 230
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.