How can I reorder my array based off the first value?-CodePudding

I'm working on a problem that says "Write a function called splay that reorganizes a list based on the first value. The first value is called the splaymaster. This function will rearrange the list such that all of the values before the splaymaster are less than or equal to the splaymaster and all of the values after it are greater than the splaymaster. The function also returns the index where the splaymaster is located after the list is rearranged. For example, if the list is [8, 15, 4, 48, 26, 45, 18, 29, 2, 1], the function will rearrange it to become [2, 1, 4, 8, 26, 45, 18, 29, 48, 15] and return the value 3. You may not sort the list." The problem that I seem to be having is for the example above it complains that the index is out of bounds which is my first problem. The next is if I use another array such as {90, 8, 15, 4, 48, 26, 45, 18, 29, 2, 1} I get {1, 90, 8, 15, 4, 48, 26, 45, 18, 29, 2} this is my output when it's not correct. What am I doing wrong? and How do I fix it?

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static int splay(int[] x) {
        int left = 1;
        int right = x.length;
        int splaymaster = x[0];
        while (left < right) {
            if (x[left] <= splaymaster) {
                left  ;
            } else {
                swap(x, left, right);
            }
            swap(x, 0, left - 1);
        }
        return splaymaster;
    }
}

CodePudding user response：

int right = x.length;

The index of the last element in an array is x.length - 1, hence the index is out of bounds. Nonetheless, your algorithm seems incorrect. Merely swapping the elements at different locations is not sufficient. If an element is less than the splaymaster then you need to move all the elements up one and insert the smaller element into the array before the splaymaster. I assume there may be other conditions regarding the way to solve the problem but if there are then they are not clear to me from your question, for example it appears that the order of the elements is not important just as long as all elements before the splaymaster are less than or equal to it. I also assume you need to change the array in place, i.e. you are not allowed to use a second array.

Consider the following code:

import java.util.Arrays;

public class SplayTst {

    public static int splay(int x[]) {
        int index = 0;
        int splaymaster = x[0];
        for (int i = 1; i < x.length; i  ) {
            if (x[i] <= splaymaster) {
                int temp = x[i];
                for (int j = i; --j >= 0;) {
                    x[j   1] = x[j];
                }
                x[0] = temp;
                index  ;
            }
        }
        return index;
    }

    public static void main(String[] args) {
        int[] test = new int[]{8, 15, 4, 48, 26, 45, 18, 29, 2, 1};
        int ndx = splay(test);
        System.out.println(Arrays.toString(test));
        System.out.println(ndx);
        test = new int[]{90, 8, 15, 4, 48, 26, 45, 18, 29, 2, 1};
        ndx = splay(test);
        System.out.println(Arrays.toString(test));
        System.out.println(ndx);
    }
}

Running the above code produces the following output:

[1, 2, 4, 8, 15, 48, 26, 45, 18, 29]
3
[1, 2, 29, 18, 45, 26, 48, 4, 15, 8, 90]
10

Alternatively, assuming that you can use any method to solve the problem, consider the following which uses ArrayList and then converts it to an array and then all the array elements are copied to the original array. Note that the single code line for converting ArrayList<Integer> to int[] is taken from the following question:

How to convert an ArrayList containing Integers to primitive int array?

I refer to this line of the below code:

int[] arr = list.stream().mapToInt(i -> i).toArray();

I iterate through the original array. If an element is greater than the splaymaster then it is appended to the ArrayList, otherwise it is inserted as the first element in the ArrayList.

import java.util.ArrayList;
import java.util.Arrays;

public class SplayTst {

    public static int splay(int[] x) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(x[0]);
        int index = 0;
        for (int i = 1; i < x.length; i  ) {
            if (x[i] <= x[0]) {
                list.add(0, x[i]);
                index  ;
            }
            else {
                list.add(x[i]);
            }
        }
        int[] arr = list.stream().mapToInt(i -> i).toArray();
        for (int i = 0; i < x.length; i  ) {
            x[i] = arr[i];
        }
        return index;
    }

    public static void main(String[] args) {
        int[] test = new int[]{8, 15, 4, 48, 26, 45, 18, 29, 2, 1};
        int ndx = splay(test);
        System.out.println(Arrays.toString(test));
        System.out.println(ndx);
        test = new int[]{90, 8, 15, 4, 48, 26, 45, 18, 29, 2, 1};
        ndx = splay(test);
        System.out.println(Arrays.toString(test));
        System.out.println(ndx);
    }
}