Partially sort an array in descending order using Java Stream API

Question

I need to know how to partially sort an array of primitive unique integers in descending order using Stream API. For example, if there is an array like {1,2,3,4,5}, I want to get {5,4,3, 1,2} - 3 biggest elements first and then the rest. Is it even possible using streams? I checked the docs - there are two methods skip and limit but they change the stream content and work from the beginning of the array.

I can sort the whole array like

Arrays.stream(arr)
.boxed()
.sorted(Collections.reverseOrder())
.mapToInt(Integer::intValue)
.toArray();

but how to make this sorting partial? I said Stream API because I want it to be written nicely.

Also I intuitively feel that concat may have a go here. Another approach I could think about - is to use a custom comparator limiting the number of sorted elements. What do you think?

P.S. I am not a Java expert.

Answer 1

Though the code is longer than the accepted answer, it does a lot less sorting: for big arrays this will matter:

private static int[] partiallySorted(int[] input, int bound) {
    int[] result = new int[input.length];

    int i = -1;
    PriorityQueue<Integer> pq = new PriorityQueue<>(bound, Comparator.naturalOrder());
    for (int x : input) {
        pq.add(x);
        if (pq.size() > bound) {
            int el = pq.poll();
            result[bound + ++i] = el;
        }
    }

    while (!pq.isEmpty()) {
        result[--bound] = pq.poll();
    }

    return result;
}

Answer 2

Here's an approach using streams.

int[] sortPartially(int[] inputArray, int limit) {
    Map<Integer, Long> maxValues = IntStream.of(inputArray)
                                            .boxed()
                                            .sorted(Comparator.reverseOrder())
                                            .limit(limit)
                                            .collect(Collectors.groupingBy(x -> x, LinkedHashMap::new, Collectors.counting()));

    IntStream head = maxValues.entrySet()
                              .stream()
                              .flatMapToInt(e -> IntStream.iterate(e.getKey(), i -> i)
                                                          .limit(e.getValue().intValue()));

    IntStream tail = IntStream.of(inputArray)
                              .filter(x -> {
        Long remainingDuplication = maxValues.computeIfPresent(x, (y, count) -> count - 1);
        return remainingDuplication == null || remainingDuplication < 0;
    });

    return IntStream.concat(head, tail).toArray();
}

Above example of course sorts the entire input array, but keeps the order of unsorted elements stable.

Another stream example using priority queue (as others mentioned) reduces the runtime complexity:

Collection<Integer> sortPartially(int[] inputArray, int sortedPartLength) {
    Queue<Integer> pq = new PriorityQueue<>(sortedPartLength);

    Deque<Integer> result = IntStream.of(inputArray).boxed().map(x -> {
        pq.add(x);
        return pq.size() > sortedPartLength ? pq.poll() : null;
    }).filter(Objects::nonNull).collect(Collectors.toCollection(ArrayDeque::new));

    Stream.generate(pq::remove).limit(sortedPartLength).forEach(result::addFirst);

    return result;
}

If there are duplicates in the input array, the order of unsorted elements can change.

Answer 3

I need to know how to partially sort an array of primitive integers in descending order using Stream API.

There is no built-in tool that lets you do this in Java. Neither in the Stream API nor in the Collections API. You either need to implement it on your own or change your approach.

I said Stream API because I want it to be written nicely.

Using Java 8 Streams does not mean that your code will be written nicely. Streams are not universal tools. Sometimes they offer enhanced readability and sometimes you have to use something else.

Another approach I could think about - is to use a custom comparator limiting the number of sorted elements.

That can't be done, since Comparator does not know how many elements have been sorted. Simply counting the calls will not give you any meaningful information in this regard.

---

What I would suggest is implementing something like C++'s std::partial_sort, which is most likely based on the heap approach.