Java Sorting with Lambda Expression

Question

I am new to Java and this might be a dumb question to ask. I was looking at '905. Sort Array By Parity' on Leetcode. One of the solutions is

class Solution {
    public int[] sortArrayByParity(int[] A) {
        Integer[] B = new Integer[A.length];
        for (int t = 0; t < A.length; ++t)
            B[t] = A[t];

        Arrays.sort(B, (a, b) -> Integer.compare(a%2, b%2));

        for (int t = 0; t < A.length; ++t)
            A[t] = B[t];
        return A;

        /* Alternative:
        return Arrays.stream(A)
                     .boxed()
                     .sorted((a, b) -> Integer.compare(a%2, b%2))
                     .mapToInt(i -> i)
                     .toArray();
        */
    }
}

I am having trouble understanding the line with lambda expression in it.

Arrays.sort(B, (a, b) -> Integer.compare(a%2, b%2));

How does it sort the array exactly? Where do a and b come from?

"Where do a and b come from?" they are declared int (a, b) -> ... part. You may want to familiarize yourself with lambdas and its syntax. One of nice articles: lambdafaq.org/what-is-a-lambda-expression — Pshemo
– Pshemo, Commented Jun 25, 2020 at 23:21

DV82XL · Accepted Answer · 2021-02-14 19:15:22Z

Sort

The Java Array.sort method takes an array B as input and sorts it according to the compare(a, b) method of the array's elements. So if the array stored Integer objects, it would sort them according to Integer.compare(a, b) by default. This just sorts the integers in increasing order.

Comparator

Java has a Comparator interface that defines a method called compare(a, b). This method returns zero if (a==b), a negative value if (a < b), and a positive value if (a > b). The Comparator interface is often used in sorting methods or ordered data structures, like TreeMap.

Lambda

Now since this question asks for a custom sort order, you need to provide a custom compare(a, b) method. Fortunately, there is an overloaded version of Array.sort that allows you to do exactly this by providing a lambda method. A lambda is simply an inline function. In this case, it provides the desired comparison logic for the sort. In your example, (a, b) -> are the inputs to the lambda function, which are provided by the sort method. This is standard lambda syntax. The sort will run a mergesort algorithm on the array B, using your lambda compare method to determine how each pair of numbers are ordered.

Sort by Parity

Integer.compare(a%2, b%2) sorts integers a and b according to their least significant bits. % is the modulus operator (remainder after division). If a is even, a%2 returns 0. If a is odd, a%2 returns 1. https://leetcode.com/articles/sort-array-by-parity/ does a decent job of breaking down the logic of why this operation sorts the numbers by parity, but it's not really obvious. The more problems you solve, the more shortcuts like this you will learn.

References

Here are some SO threads that provide more information:

Andreas · Accepted Answer · 2020-06-25 23:31:19Z

3

You are calling Arrays.sort(T[] a, Comparator<? super T> c), where T is resolved by the compiler to Integer, which means that the lambda expression must implement method compare(Integer o1, Integer o2).

a and b are the two parameters to the method. That's how lambda expressions work, you must name (and optionally type) the formal parameters of the abstract method of the functional interface.

answered Jun 25, 2020 at 23:31

Andreas

160k13 gold badges164 silver badges262 bronze badges

Comments

Emma Marcier · Accepted Answer · 2020-08-02 00:34:53Z

For interviews, as much as you can, you should avoid using Java's specialized methods.
You can use this Solution, which is much simple to understand and is interview friendly.

Accepted Solution:

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int left = 0;
        int right = A.length - 1;

        while (left < right) {
            if (A[left] % 2 == 0)
                left++;

            else {
                if (A[right] % 2 != 0)
                    right--;

                if (A[right] % 2 == 0) {
                    swap(A, left, right);
                    left++;
                    right--;
                }
            }
        }

        return A;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int left = 0;
        int right = A.length - 1;

        while (left < right) {
            if ((A[left] & 1) == 0)
                left++;

            else {
                if ((A[right] & 1) != 0)
                    right--;

                if ((A[right] & 1) == 0) {
                    swap(A, left, right);
                    left++;
                    right--;
                }
            }
        }

        return A;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

References

For additional details, you can see the Discussion Board. In the Discussion Board, there are plenty of accepted solutions, explanations, efficient algorithms with a variety of languages, and time/space complexity analysis.

Collectives™ on Stack Overflow

Java Sorting with Lambda Expression

3 Answers 3

Sort

Comparator

Lambda

Sort by Parity

References

Comments

Comments

Accepted Solution:

References

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Sort

Comparator

Lambda

Sort by Parity

References

Comments

Comments

Accepted Solution:

References

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related