-2

Given an array of ints, I want to rearrange it alternately i.e. first element should be minimum, second should be maximum, third second-minimum, fourth second-maximum and so on...

I'm completely lost here...

0

5 Answers 5

3

Another method that doesn't require the space of three separate arrays but isn't as complex as reordering in place would be to sort the original array and then create a single new array. Then start iterating with a pointer to the current i-th index of the new array and pointers starting at the 0-th index and the last index of the sorted array.

public class Foo {

    public static void main(String[] args) {
        // Take your original array
        int[] arr = { 1, 4, 5, 10, 6, 8, 3, 9 };
        // Use the Arrays sort method to sort it into ascending order (note this mutates the array instance)
        Arrays.sort(arr);
        // Create a new array of the same length
        int[] minMaxSorted = new int[arr.length];
        // Iterate through the array (from the left and right at the same time)
        for (int i = 0, min = 0, max = arr.length - 1; i < arr.length; i += 2, min++, max--) {
            // the next minimum goes into minMaxSorted[i]
            minMaxSorted[i] = arr[min];
            // the next maximum goes into minMaxSorted[i + 1] ... but
            // guard against index out of bounds for odd number arrays
            if (i + 1 < minMaxSorted.length) {
                minMaxSorted[i + 1] = arr[max];
            }
        }
        System.out.println(Arrays.toString(minMaxSorted));
    }
}
0
0

Hint:

Create two new arrays, 1st is sorted in assenting order and other is in descending order. Than select 1st element from 2nd array and 1st element from 1st array, repeat this selection until you reach half of both 1st and second array. and you will get your desired array.

Hope this will help you.

3
  • This is probably the best approach for a beginner. An advanced programmer might consider sorting the array once, and then rearranging the elements. It should work ... but the logic is complicated.
    – Stephen C
    Aug 6, 2016 at 4:02
  • I think rearranging the element is more complex for a beginner@StephenC
    – Kaushal28
    Aug 6, 2016 at 4:04
  • 1
    That's what I just said. Didn't I?
    – Stephen C
    Aug 6, 2016 at 4:05
0

The approach in @Kaushal28's answer is the best approach for a beginner. It requires more space (2 extra copies of the array) but it is easy to understand and code.

An advanced programmer might consider sorting the array once, and then rearranging the elements. It should work, but the logic is complicated.

Hint: have you ever played "Clock Patience"?

0

This solution is based on Aaron Davis solution. I tried to make the looping easier to follow:

public class AltSort  {

    //list of array elements that were sorted
    static Set<Integer> indexSorted = new HashSet<Integer>();

    public static void main (String[] args) throws java.lang.Exception

    {
        //test case
        int[] array = new int[]{7,22,4,67,5,11,-9,23,48, 3, 73, 1, 10};
        System.out.println(Arrays.toString(altSort(array)));

        //test case
        array = new int[]{ 1, 4, 5, 10, 6, 8, 3, 9 };
        System.out.println(Arrays.toString(altSort(array)));
    }

    private static int[] altSort(int[] array) {

        if((array == null) || (array.length == 0)) {
            System.err.println("Empty or null array can not be sorted.");
        }

        Arrays.sort(array);

        //returned array
        int[] sortedArray = new int[array.length];
        int firstIndex = 0, lastIndex = array.length-1;

        for (int i = 0; i < array.length; i++) {

            if((i%2) == 0) { //even indices

                sortedArray[i] = array[firstIndex++];
            }
            else {
                sortedArray[i] = array[lastIndex --];
            }
        }

        return sortedArray;
    }
}
0

Here is another alternative: monitor the indices that have been sorted, and search the rest for the next min / max:

import java.util.Arrays; import java.util.Set;

/**
 * Demonstrates an option for sorting an int[] array as requested,
 * by keeping a list of the array indices that has been sorted, and searching
 * for the next min / max.
 * This code is not optimal nor robust. It serves a demo for this option only.
 *
 */
public class AltSort  {

    //list of array elements that were sorted
    static Set<Integer> indexSorted ;

    public static void main (String[] args) throws java.lang.Exception      {
        //test case
        int[] array = new int[]{7,22,4,67,5,11,-9,23,48, 3, 73, 1, 10};
        System.out.println(Arrays.toString(altSort2(array)));

        //test case
        array = new int[]{ 1, 4, 5, 10, 6, 8, 3, 9 };
        System.out.println(Arrays.toString(altSort2(array)));
    }

    private static int[] altSort2(int[] array) {

        if((array == null) || (array.length == 0)) {
            System.err.println("Empty or null array can not be sorted.");
        }

        //returned array
        int[] sortedArray = new int[array.length];

        //flag indicating wether to look for min or max
        boolean lookForMin = true;

        int index = 0;
        while(index < array.length) {

            if(lookForMin) {
                sortedArray[index] = lookForArrayMin(array);

            }else {
                sortedArray[index] = lookForArrayMax(array);
            }

            index++;
            //alternate look for min / look for max
            lookForMin = ! lookForMin;
        }

        return sortedArray;
    }

    private static int lookForArrayMin(int[] array) {

        int minValue = Integer.MAX_VALUE;
        int minValueIndex = 0;

        for( int i =0; i< array.length; i++ ){

            //if array[i] is min and was not sorted before, keep it as min
            if( (array[i]< minValue) && ! indexSorted.contains(i) ) {

                minValue = array[i]; //keep min
                minValueIndex = i;   //keep min index
            }
        }

        //add the index to the list of sorted indices
        indexSorted.add(minValueIndex);
        return minValue;
    }

    private static int lookForArrayMax(int[] array) {

        int maxValue = Integer.MIN_VALUE; //max value
        int maxValueIndex = 0;   //index of max value

        for( int i =0; i< array.length; i++ ){

            //if array[i] is max and was not sorted before, keep it as max
            if( (array[i] > maxValue) && ! indexSorted.contains(i)) {
                maxValue = array[i]; //keep max
                maxValueIndex = i;   //keep max index
            }
        }

        //add the index to the list of sorted indices
        indexSorted.add(maxValueIndex);
        return maxValue;
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.