Trying to Rearrange Array to Max Min format

[Rohit Gaikwad]

Code--

public class MinMaxPair {
	static int[] input;
	 static int posMin ,posMax;
	 public static void main(String[] args){
		 input =new int[]{7,6,3,2,5,1,4};
		
		 for(int i =0;i<input.length;i++){
			 
			 for(int j = input.length-1 ; j> i ;j--)
			 {
				 if(i==0){
				
					
					 if(input[i] < input[j]);
					 {
						 int temp = input[i];
						 input[i]=input[j];
						 input[j] =temp;
					 }
					 
				 }
				
				 if(i!=0&&i%2==0){//even index
					
				 if( input[i] < input[j] );
				 {
					 int temp = input[i];
					 input[i]=input[j];
					 input[j] =temp;
				 }
					 
			 }
				 
				  if(i%2==1){//odd index
					
				 if(input[i]>input[j]){
					 int temp = input[i];
					 input[i]=input[j];
					 input[j] =temp;
					 
					  
				 }
				 
			 }
		}
			
	
		 }
			System.out.println(Arrays.toString(input));
	 }
}

i do have some prblem on the line 1 if(input[i] < input[j]); which is always returning true
for i=0 input[i] =7 which is greater then input[j] which is 4
but still if loop is running and changing the value
Please help me

Thanks in Advance

[Rohit Gaikwad]

Current Output is [6, 1, 5, 2, 7, 3, 4]
required is [7,1,6,2,5,3,4]

[Knute Snortum]

Have you tried using another array to put the output into?

[Campbell Ritchie]

Why are you trying to swap elements inside the main method? You should have a swap method; look at all that repeated code.
What do the even index and odd index bits mean? Why is index 0 insdie that loop in the first place?

[Liutauras Vilda]

ohit Gaikwad wrote:i do have some prblem on the line 1

I think otherway round. Your line 1 probably is the only one which is good. You declared class in correct way, camel casing is also looks good.

Could you please describe us your problem in english, non Java language. What is the task about?

After you understand the problem, you'll need to learn how to indent your code. You can find indentation guidelines here. This document is from 1999, but the techniques are still being applied among Java developers.

[Piet Souris]

hi Rohit,

all good advices, think about these carefully.

Assuming you have a method that outputs an array in the required order, given some input array (one of the advices given):

- can't you use a copy of your input array first? Then sort it.
- From this sorted array, it is very easy to create either a new array in the required order and return that, or overwrite your input array in the same way.

I think that that is very much easier than what you have now.

[Rohit Gaikwad]

Hi all
Let me tell you why i am trying to do it with a Single array and why not using an Result array.
Yesterday i was in an Interview where the guy asked me to rearrange the Array in Max Min format
As you every one said using 2 arrays like an input array and result array will solve this issue. I did the same but the Examiner asked me to do it with a single array and he said it can be done.
So that's the reason i guess this will even help other on there Interview part
Can any one please tell me the Logic behind my code is correct or not so i can try it more harder

Thanks to all

[Rohit Gaikwad]

One more thing he mentioned not to sort array
like you cant short array and then arrange the array
you need to do it by finding Max and Min logic only
i cant do [1,2,3,4,5,6,7] and then rearrange.


and i know that's really easy to do it that way
Thanks again

[Rohit Gaikwad]

i guess i should Explain the task
So the task is
1) we have an unsorted array example [7,4,2,1,5,6,3]
2) we need to rearrange this array in Max Min Max Min... format
3) so all even index will be Max like max of all at index 0 then second max at index 2 and so on
4) and all odd will be minimum like at index 1 we need the lowest number
then on index 3 we need second lowest and so on
example on index 1 we have 1 and on index 3 we have 2
so the output should be like [7,1,6,2,5,3,4]
[Max,Min,Max,Min,Max,Min,Max]
but the conditions are
1) you can use only one array that's the input array (cant use any result or output array)
2)you cant sort array by any means (no-Arrays.sort();) or any other thing

i guess that will be clear now if no i will post a Picture describing this

[Piet Souris]

Well, can you describe your algorithm? I see many if's and swappings, so it is very hard to follow.

But take the advices given. The assignment can be done in an easy way, as described, but the logic will only be easy to follow if you create some handy helper methods
For instance:

int indexOf(int[] array, int lowerbound, int higherbound, boolean smallestWithinTheBounds) {...}

[Junilu Lacar]

Here's a way to think about this problem:

1. Starting from position 0, iterate over the array, swapping element 0 with any number found that's larger than it.
2. Go on to the next position and iterate over the rest of the array, only this time swapping with any smaller number.
3. Go on to the next position and iterate over the rest of the array, only this time swapping with any larger number.
4. Go on to the next position and iterate over the rest of the array, only this time swapping with any smaller number.
5. continue the above pattern until you get to the last element of the array

I suggest using a variable like this:

boolean isLookingForMax = true;

for (...) {
   ...
}

Somewhere inside that for-loop, you will have the statement:

   isLookingForMax = !isLookingForMax;

Basically, the variable isLookingForMax is a toggle. That is, it's a boolean variable that you flip back and forth between its true and false states. This allows you to use alternative algorithms. This can actually be solved very elegantly using lambda expressions (Edit: Or maybe not. I thought it could at first but my few attempts to do so have proven me wrong).

I think with those hints and a little bit of thinking it through, you should be able to figure this out.

Good luck.

[Junilu Lacar]

There's also a recursive solution to this that can eliminate one level of nesting that you have in the iterative solution I described above. There is another solution that involves interleaving two intermediate arrays or lists but I don't like it that much because it increases the amount of memory required to solve the problem and it's less elegant than the first two solutions.

[Junilu Lacar]

BTW, using a Boolean variable like isLookingForMax is better than writing code like this:

if (i % 2 == 0) // even index 

First of all, that code and its comment is at a very low level of abstraction. In fact, it's all about implementation rather than intent. Even the comment fails to reveal intent. So what if the index is even or odd, how is that relevant to the solution? By using a name like isLookingForMax instead, you are revealing the intent of the code rather than focusing on the implementation. This makes the code self-documenting and more readable.

[Liutauras Vilda]

Junilu Lacar wrote:1. Starting from position 0, iterate over the array, swapping element 0 with any number found that's larger than it.

Shouldn't be "swapping element 0 with any number found that's larger than him and largest among the others", or simply "swapping element 0 with the largest one in case there is such"?

=Junilu Lacar wrote:2. Go on to the next position and iterate over the rest of the array, only this time swapping with any smaller number.

Same as above, probably not smaller, but in fact smallest element within the array.

Or I misunderstood you Junilu?

[Junilu Lacar]

Think about it some more, Liutauras. Decompose the problem into the smallest problem. You'll find that in this case, if you only worry about the small stuff, the bigger picture will fall in line. If I just iterate and keep looking for a larger number to most recent largest number I found so far, it follows that at the end of the iterations, I should have found the largest number. When I "move to the next element", I'm basically saying, "Ok, done with that, now to find the next largest/smallest number."

[Junilu Lacar]

In other words, every time you do a swap, you're saying, "This is the largest/smallest number I have found so far."

[Junilu Lacar]

Liutauras, I think you have fallen into a premature optimization trap. By wanting to look at the entirety of the array before swapping, you are avoiding unnecessary swaps but you also make it necessary to introduce another variable to track the index with which you will potentially perform a swap at the end of an iteration. This complicates the algorithm. Not thinking about optimizing too soon helps you consider the more straightforward solution first. If you really need to optimize, then it's not that hard to add the temporary variable.

[Piet Souris]

All this swapping is not necessary.

If you look at the helper method I suggested, then this is what I had in mind:

start at index 0. Now, call the helper method with lowerbound = 0. higherbound = array.length - 1, and with the boolean set to false for we want to get the index of the largest element.
Swap element[0] with element[index found].
Now repeat the procedure, starting with element[1], lowerbound = 1, boolean = true, et cetera. Actually, the higherbound is unnecessary.

[Rohit Gaikwad]

the Logic your talking about like creating two helper methods like getMax(); and getMin(); i did that already in that case you need to keep track on current position and new position where we found the highest/lowest int.
But in that case we cant go with a single array.
Reason --
Thik about it your calling a Helper method every time (like when index is 0 or its 1,2,3..) what we can do is call getMax(); for even and call getMin(); for odd Index but how will you guide the helper methods to search like 1st you search or highest then 2nd time you look for second highest and so on same or the getMin() method too.

Trust me i Tried that already.
and this Was the easiest implementation i found
but i still have to try that
isLookingForMax = !isLookingForMax;
once i am done with that will let you know

[Liutauras Vilda]

Junilu Lacar wrote:Liutauras, I think you have fallen into a premature optimization trap. By wanting to look at the entirety of the array before swapping, you are avoiding unnecessary swaps but you also make it necessary to introduce another variable to track the index with which you will potentially perform a swap at the end of an iteration. This complicates the algorithm. Not thinking about optimizing too soon helps you consider the more straightforward solution first. If you really need to optimize, then it's not that hard to add the temporary variable.

Well, I haven't thought about optimization yet

As you mentioned couple of weeks ago, it is interesting how differently everyone minds work. The way I mentioned it would be my first attempt.

[Liutauras Vilda]

Rohit Gaikwad wrote:for even and call getMin(); for odd Index but how will you guide the helper methods to search like 1st you search or highest then 2nd time you look for second highest and so on same or the getMin() method too.

As guys mentioned, probably it is not the best approach to get involved in thinking about even and odd indices, that gets too complicated (or maybe not). It has been suggested to use so called "flag" which should give you an answer what next you need to look for. Either for a max or min number.

Rohit Gaikwad wrote:how will you guide the helper methods to search like 1st you search or highest then 2nd time you look for second highest

That is the point. You don't look for 2nd or 3rd highest.. You always look for the highest among the rest of the array, which hasn't been rearranged yet. Remember, the top max or top min numbers should be left behind you (at the beginning of the array during each iteration).

Rohit Gaikwad wrote:...Trust me i Tried that already.
and this Was the easiest implementation i found

Was it most readable? Yes, sometimes there are shortest and might even most clever ways of doing some things, but not necessarily they are most readable.

Readability (apart from the corretness) should be the priority, unless there are special requirements for algorithm performance and most readable way is not good enough - then yes, things get complicated.

I have solved that exercise after you created that thread and showed it to one of moderators to revise it, and guess, I've got a comment about at least one of the parts which was cutting a corner in saving some lines of code, and in fact it wasn't a good idea to do so.

So think about readability always. That usually comes down to decomposing your problem and wrapping into methods with the self revealing names about their intent.

[Winston Gutkowski]

Liutauras Vilda wrote:Could you please describe us your problem in english, non Java language.

@Rohit: This is the best possible advice you can be given.

You say that you have already tried to do this, but your code is incredibly difficult to understand; which suggests to me that you don't understand the problem sufficiently yet to even start coding.

Just from your description, it's plain that you need at least two tasks:
1. Find a maximum value.
2. Find a minimum value.
and you need to move that value if it isn't already in the correct place as defined by your "max/min" order.

Obviously that description is very sparse and you need to "flesh it out" until you understand every single step required to complete this task, and can describe how to do it to a 10-year old child with no knowledge of Java.

For example: Suppose you have 10 wooden blocks, numbered '0' through '9' and you line them up for your child in random order. What exactly do they have to do to get the blocks in "max/min" order, and why?

Programming is thinking, not coding; and you should get in the habit of doing this - and writing it down - every single time you have a problem ... and before you write your first line of Java code.

HIH

Winston

[Liutauras Vilda]

Liutauras Vilda wrote:Your line 1 probably is the only one which is good. You declared class in correct way

I was mistaken. Unfortunately class name is misleading. I didn't notice that yesterday, fortunately it didn't hide from my eyes today

Rohit Gaikwad wrote:

public class MinMaxPair {

That should read MaxMinPair, but not the other way round. Some wouldn't notice probably, but it is worth of correcting. For this exercise might it is not that crucial, but in most cases that would be a serious mistake.