Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Sort Numbers

 
atul kumar
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
IntelliJ IDE Java MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This topic better suites in Programming diversions.
Moved it for you.
CarefullyChooseOneForum
 
Gabriel Claramunt
Ranch Hand
Posts: 375
Monad Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Insertion sort is a simple place to start...
 
Gabriel Claramunt
Ranch Hand
Posts: 375
Monad Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Almost any sorting algorithm will do if you replace the comparation function with something adequate to the problem (hint hint)
 
Paul Clapham
Sheriff
Posts: 21107
32
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
IntelliJ IDE Java MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 229
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
IntelliJ IDE Java MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 12127
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Monad Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 229
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 12127
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Monad Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 229
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 12127
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ah... i guess we need to use a 'stable sort' algorithm with a modified compare routine.
 
Paul Yule
Ranch Hand
Posts: 229
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic