I need to sort the array in a specific "descending" order: where the elements are inserted alternatively at the start or end of the array.

If the descending order of elements is a>b>c>d, then the final array should be

[] -> [a,_,_,_] -> [a,_,_,b] -> [a,c,_,b] -> [a,c,d,b]

Sample 1

Input: [4, 13, 8, 9, 7, 1, 6]
Output: [13, 8, 6, 1, 4, 7, 9]

Sample 2

Input: [16, 23, 7, 11, 3, 14]
Output: [23, 14, 7, 3, 11, 16]

How can I find a solution to this problem?

I tried only sort the first index but I need to sort the last index also.

public static void BubbleSort_First(int[] arr,int first){
        int n = arr.length;
        for (int i = 0; i < n - 1; i  )
        for (int j = 0; j < n - i - 1; j  )
            if(arr[i]==first){
                if (arr[j] < arr[j   1]) {
                    // swap arr[j 1] and arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j   1];
                    arr[j   1] = temp;
                }
            }
}

CodePudding user response：

Maybe you could just iterate backwards over a sorted version of the array while keeping two pointers to the next position at the front and back of the array respectively:

import java.util.Arrays;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        int[] a1 = {4, 13, 8, 9, 7, 1, 6};
        System.out.printf("Input1 = %s%n", Arrays.toString(a1));
        System.out.printf("Output1 = %s%n", Arrays.toString(frontBackSorted(a1)));
        System.out.println();
        int[] a2 = {16, 23, 7, 11, 3, 14};
        System.out.printf("Input2 = %s%n", Arrays.toString(a2));
        System.out.printf("Output2 = %s%n", Arrays.toString(frontBackSorted(a2)));
    }

    public static int[] frontBackSorted(int[] array) {
        int[] sortedArray = IntStream.of(array).sorted().toArray();
        int n = array.length;
        int[] result = new int[n];
        int i = 0, j = n - 1, k = n - 1;
        boolean front = true;
        while (i <= j) {
            if (front) {
                result[i  ] = sortedArray[k--];
            } else {
                result[j--] = sortedArray[k--];
            }
            front = !front;
        }
        return result;
    }
}

Output:

Input1 = [4, 13, 8, 9, 7, 1, 6]
Output1 = [13, 8, 6, 1, 4, 7, 9]

Input2 = [16, 23, 7, 11, 3, 14]
Output2 = [23, 14, 7, 3, 11, 16]