Given a list and a value of x, split it such that all items less than x came before items greater than or equal to x

Question

I have a question. Is there a more efficient way to solve this issue? I made it like below but i created 3 new Lists.

public List<Integer> divideListByX1(List<Integer> list, int x) {
    List<Integer> beforeX = new ArrayList<>();
    List<Integer> afterX = new ArrayList<>();
    List<Integer> all = new ArrayList<>();
    for (Integer integer : list) {
        boolean b = (integer < x) ? beforeX.add(integer) : afterX.add(integer);
    }
    all.addAll(beforeX);
    all.addAll(afterX);
    return all;
}

Thanks for your help

Answer 1

This can be done in-place in linear time using the Pivot operation of Quicksort:

public static void pivot(List<Integer> list, int pivot) {
    int left = 0;
    int right = list.size() - 1;

    while (left < right) {
        while (left < list.size() && list.get(left) < pivot) {
            left++;
        }
        while (right >= 0 && list.get(right) >= pivot) {
            right--;
        }
        if (left < right)
            Collections.swap(list, left++, right--);
    }
}

Answer 2

The following way is very slightly more efficient because it adds the numbers straight into the resulting list in one go, instead of using intermediate lists:

public static List<Integer> divideListByX1(List<Integer> list, int x) {
    Integer[] result = new Integer[list.size()];
    int lowIndex = 0;
    int highIndex = result.length - 1;
    for (Integer n : list) {
        if (n < x)
            result[lowIndex++] = n;
        else
            result[highIndex--] = n;
    }
    return Arrays.asList(result);
}

The downside with that is that the "high numbers" part is not in the original order of the input list, but I guess that's not important.

Also, here's a way to do it using Streams, but is probably not more efficient than your initial attempt:

public List<Integer> divideListByX1(List<Integer> list, int x) {
    return list
        .stream()
        .collect(Collectors.partitioningBy(n -> n >= x))
        .values()
        .stream()
        .flatMap(List::stream)
        .toList();
}