Rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest,

Question

public class RearrageArrayOrder {

public static void main(String[] args)
{
    int arr[]= { 5, 8, 1, 4, 2, 9, 3, 7, 6 };
    Arrays.sort(arr);
    int n=arr.length;
    for(int i=0,j=n-1;i<=n/2 ;i++,j--)
    {
        System.out.print(arr[i]+" "+arr[j]+" ");
    }
}

}

Expecting Output :1 9 2 8 3 7 4 6 5

My Output :1 9 2 8 3 7 4 6 5 5

Getting middle element of sorted array twice for odd length.For even length output is correct.

Thanks in Advance

Answer 1

    int n = array.length;
    for(int i=0,j=n-1;i<=n/2 ;i++,j--)
    {
        System.out.print(arr[i]+" "+arr[j]+" ");
    }

You need to understand what is happening over here. As you state Getting middle For even length output is correct. But for twice for odd length. Let's check your statements.

You are printing arr[i] and arr[j] each and every time in your print statement. Where i and j are acting as the index of the array.

Say, when the length is even. You have

1 2 3 4 5 6 7 8

n = array.length/2; // 4 since your condition says loop will move till i <= n So running the loop. This is what is happening.

i------ j

0 ---- 7     // arrayelements 1 8

1 ---- 6     // arrayelements 2 7

2 ---- 5    //  arrayelements 3 6

3 ---- 4    // arrayelements  4 5

4 ---- 3    // arrayelements  5 4

5   // i > n ; out of the loop!

output 1 8 2 7 3 6 4 5 5 4 // Even for even length your output is wrong

To fix that it's better you put i = n/2 - 1 but this will change the output you are getting currently when the length is odd.(you won't be getting the twice of middle elements) Actually you won't be printing the middle index element at all then.

So, keeping your logic, I would suggest this

 for(int i=0,j=n-1;i<=n/2 ;i++,j--)
 {
     if(n%2 == 0)  // if length is even
     {
         if(i==n/2)
         {
             break;      //not printing twice the elements as you can see above instead breaking out of the loop
         }
         else{
              System.out.print(arr[i]+" "+arr[j]+" ");
         }
      }
      else        //if length is odd
      {
          if (i == n/2)
          {
              System.out.print(arr[i]);     // when i has reached n/2 print value of i (one time of middle element, like 5 in your case) and break
               break;
           }
           else{
                System.out.print(arr[i]+" "+arr[j]+" ");
            }

       }


 }

Answer 2

Well though the existing answers do solve what is required here. Yet a different way to do the same could be:

public static void main(String[] args) {
    int arr[] = {5, 8, 1, 4, 2, 9, 3, 7, 6, 10};
    Arrays.sort(arr);
    while (arr.length != 0) { // unless there is any element in arr
        System.out.print(arr[0] + " "); // print the first element
        arr = Arrays.copyOfRange(arr, 1, arr.length); // clone the remaining elements
        arr = reverseArray(arr); // reverse the array
    } // repeat
}

where the reverseArray is as follows:

private static int[] reverseArray(int[] arr) {
    int n = arr.length - 1;
    int[] temp = new int[n + 1];
    int i = 0;
    while (i <= n) {
       temp[i] = arr[n - i];
       i++;
    }
    return temp;
}

and the reverseArray method was supposed to be added to solve flipping the array every iteration.

Answer 3

Sorting part is right but you mess it up in the printing part. Just do printing two elements until you get to a same index or left one larger than right one.

for(i=0,j=n-1;i<j;i++,j--) // i and j are declared outside loop.
{
 System.out.print(arr[i]+" "+arr[j]+" ");
}
if(i==j)
  print(arr[i]);

_{I have compared i and j outside the loop instead of inside to save the number of comparisons as a whole. (in general cases)}

For the middle one just print once checking the indices outside the loop.

How you could have solved it yourself?

1. By dry running the code and understanding why it is doing so? why is it deviating from correct answer?

2. Learn to use a debugger to step through the code. It might help later when you get into writing or even reading bigger code.

Answer 4

This is very simple solution for your problem

   int arr[]= { 5, 8, 1, 4, 2, 9, 3, 7, 6 };
    Arrays.sort(arr);
    int n=arr.length;
    for(int i=0, j=n-1; i<=j; i++, j--){
        if(i !=j)
        System.out.print(arr[i]+" "+arr[j]+" ");
        else{
            System.out.print(arr[i]);
        }

    }