6

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.

Improve this question
9
  • How would you solve it with plain Java? Is the input an array or a set? Commented Sep 5, 2019 at 12:46
  • Your example input is {1,2,3,4,5}. Is the input guaranteed to be sorted in ascending order? Commented Sep 5, 2019 at 12:47
  • @Andrew Tobilko Input is an array int[]. In plain Java I would use a any well-known algo like insertion sort etc stopping after needed elements get sorted in desc order. The problem is that I need to pass a testcase and using such a naive algo I get timeout. Commented Sep 5, 2019 at 12:49
  • Also is it necessary that the "other" elements are in their original order? If not, then wouldn't a normal sort basically solve this? Edit: I just saw your comment about timeout. Commented Sep 5, 2019 at 12:50
  • 3
    @curveball I highly doubt you will speed up things by rewriting them to Stream API... Commented Sep 5, 2019 at 12:51

5 Answers 5

Reset to default
4

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;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thank you! I will look at this more in depth later. Now I am overwhelmed with all this java stuff...
Apart from streams, there are few ways to solve the problem certainly. Other than that, is this tested on the inputs? Doesn't seem to be appropriate with the result[--b] = el and result[bound++] = i combination in the code. Would get back to you with the details in a while
@Naman edited. actually yes, tested both your input and OP's.
I’d say, this is way more efficient than the accepted answer, even for small arrays. The accepted answer’s solution even bears a full sort operation at the beginning, on boxed values, before doing lots of stuff to emulate a partial sort operation. It does maintain the original order though, but according to this comment that’s not a requirement.
1

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.

Improve this answer

11 Comments

Sorry, but what is IntStream? I use java 8 and it throws an error.
@curveball java.util.stream.IntStream is a part of JDK 8
It's not obvious from the question but if the array contains duplicates, like {1,2,3,4,5,5,5} you might lose one or two of the largest elements
@Eritrean they are unique, I corrected the original post.
@Eritrean I tested {1,2,3,4,5,5,5} and expect {5,5,5,1,2,3,4} as a result. And that's the result of the function. What do you mean?
|
1

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.

Improve this answer

8 Comments

"Using Java 8 Streams does not mean that your code will be written nicely." - Conciseness and expressiveness is one of its purposes, not the major one, though.
"Comparator does not know how many elements have been sorted" - It may know it, which would make it stateful. However, Stream API wants us to write stateless Comparators. I don't downvote any answers, btw.
@AndrewTobilko I wholeheartedly agree, but simply using Streams won't make your code better. They may, certainly, but it's not a rule. Not everything that can be rewritten using Streams should be. These are rare cases, but they do happen.
@AndrewTobilko A stateful comparator violates the contract of comparator itself, regardless of which API you use. In the current implementation, it doesn’t matter whether you use Stream.sorted, List.sort, or Arrays.sort, it will end up at the same code anyway, which will break with a stateful comparator. But once you’ve taught your comparator how to remember the 3 biggest numbers, you did the crucial work anyway. Combining the facility to remember the 3 biggest numbers with a single linear traversal is way more efficient than a sort operation.
@AndrewTobilko actually, the requirement that repeated evaluations return the same result is so fundamental that it is not even mentioned explicitly. But all other requirements, like “sgn(compare(x, y)) == -sgn(compare(y, x))” and “((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0” are building on it. A comparator may silently record encountered values when it doesn’t affect the order, but that would be less efficient than just doing a linear pass.
|
1

I would save the three largest elements in a set and then define my own comparator.

 public static void main(String[] args){
    int[] input = {1,2,3,4,5};
    Set<Integer> set = Arrays.stream(input).boxed().sorted(Comparator.reverseOrder()).limit(3).collect(Collectors.toSet());
    Comparator<Integer> customComp = (a,b) -> { 
        if(set.contains(a) && set.contains(b)){ return a.compareTo(b);}
        else if(set.contains(a)){ return 1;}
        else if(set.contains(b)){ return -1;}
        else { return 0;}
    };
    int[] sorted = Arrays.stream(input).boxed().sorted(customComp.reversed()).mapToInt(i->i).toArray();
    System.out.println(Arrays.toString(sorted));
}
Improve this answer

Comments

0

You won't be able to do this very nicely using streams. Here is one way to do it:

public static void main(String[] args) {

    Integer[] arr = {1, 2, 3, 4, 5};
    List<Integer> originalValues = new ArrayList<>(Arrays.asList(arr));

    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < 3; i++) {
        originalValues.stream().max(Integer::compareTo).ifPresent(v -> {
            list.add(v);
            originalValues.remove(v);
        });
    }
    list.addAll(originalValues);

    System.out.println(list);
    // [5, 4, 3, 1, 2]
}
Improve this answer

3 Comments

it gives an error like Exception in thread "main" java.lang.ClassCastException: [I cannot be cast to java.lang.Integer at .max(Integer::compareTo).ifPresent(v -> {
Not sure how. It works fine for me. Maybe try .stream().mapToInt(v->v).max()
@curveball this code uses Integer[], not int[]. You can’t use int[] with Arrays.asList.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.