Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

Sort Numbers

 
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 ]
 
Bartender
Posts: 1638
IntelliJ IDE MySQL Database Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This topic better suites in Programming diversions.
Moved it for you.
CarefullyChooseOneForum
 
Ranch Hand
Posts: 376
Scala Monad
  • 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?
 
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)
 
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: 376
Scala Monad
  • 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)
 
Marshal
Posts: 25673
69
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 MySQL Database Java
  • 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!
 
Ranch Hand
Posts: 230
  • 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 MySQL Database Java
  • 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.
 
lowercase baba
Posts: 12871
62
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: 376
Scala Monad
  • 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: 230
  • 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
Posts: 12871
62
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: 376
Scala Monad
  • 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: 230
  • 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
Posts: 12871
62
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: 230
  • 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.
 
Don't get me started about those stupid light bulbs.
    Bookmark Topic Watch Topic
  • New Topic