CODEWITHSUNDEEP
javakotlin
Zorgan
Zorgan

Reputation: 9123

How Comparator.compare() works?

Learning Kotlin, I'm trying to understand how Java's Comparator interface works - mainly the compare() function so I can utilize it.

I've tried reading the docs for compare() but I'd like a much simpler explanation of how it works.

What exactly is x and y in compare(x, y) when iterating over a list? Does it target & compare each pair of numbers when iterating? e.g:

arrayOf(1, 2, 3, 4)

would it compare 1 and 2 (x and y), then 2 and 3 (x and y), then 3 and 4 (x and y)?

I have a Kotlin function that provides a comparator to sort a list in a descending order:

import java.util.*

fun getList(): List<Int> {
    val arrayList = arrayListOf(1, 5, 2)
    Collections.sort(arrayList, object: Comparator<Int> {
        override fun compare(x: Int, y: Int){
            return x < y
        }
    } )
    return arrayList

I'm not sure why the above function isn't the right syntax to complete that.

Upvotes: 2

Views: 2567

Answers (4)

s1m0nw1
s1m0nw1

Reputation: 81899

The compare documentation is pretty clear:

return a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

So you have to return an Int from your function rather than a boolean.

To provide working Kotlin code, I include an example:

val list = listOf(1, 5, 2)
list.sortedWith(Comparator { x, y ->
       x.compareTo(y)
})

Sorting itself can be performed with different algorithms but they will utilize compareTo internally. The Collections documentation gives an idea:

The documentation for the polymorphic algorithms contained in this class generally includes a brief description of the implementation. Such descriptions should be regarded as implementation notes, rather than parts of the specification. Implementors should feel free to substitute other algorithms, so long as the specification itself is adhered to. (For example, the algorithm used by sort does not have to be a mergesort, but it does have to be stable.)

Upvotes: 1

Joffrey
Joffrey

Reputation: 37690

A Comparator<T> is simply a way to compare any 2 elements of type T.

What exactly is x and y in compare(x, y) when iterating over a list?

When iterating, the comparator is not called at all.

When passed to the Collections.sort() method, the comparator is used anytime the underlying sorting algorithm needs to compare 2 elements.

I'm not sure why the above function isn't the right syntax to complete that.

Your current implementation does not satisfy the documentation. compare() needs to return a negative integer, 0, or a positive integer depending on how to 2 elements relate to each other.

Upvotes: 3

GhostCat
GhostCat

Reputation: 140427

It boils down to this statement from the javadoc:

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

That is all there is to this. When you write a Comparator, you define what order you want. The key thing is that your method returns -1, 0, or 1. Depending on how you want those two incoming arguments to be ordered. (and yes, it doesn't need to -1 or 1, just negative, zero, positive).

In other words: the key point is that compare() serves in that contract. It defines an order on two elements. That is all there is to this.

When sorting data, it will be called each time when the underlying sorting code needs to know the order of two elements. So the exact "order" in which these calls take place, and what arguments are passed depends on the actual sorting algorithm, and the data you intend to sort.

From that point of view, your question implies that you are some overthinking the whole topic. Simply understand: you use a comparator when you intend to define a "custom" order for your objects/values.

And there is no sense in defining your "own" comparator for int, Int, or Integer, as these classes already define their natural order, so there is already Integer.compare() for example. The only use-case to define your own comparator for such a class would be when you want to order them differently. But most likely, you would then still use existing comparator functionality, and use other built in ways, for example to reverse the "natural" order.

Upvotes: 6

Cililing
Cililing

Reputation: 4753

Comparator is only interface for classes which can be compared. It's about comparing ANY two objects. Nothing more, nothing less. From docs:

@param o1 the first object to be compared.

@param o2 the second object to be compared.

@return a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

Sorting is completely other thing. It uses comparator (it would be hard to sort anything without knowing how to compare two elements), so you can provide your own way to sort collection.

But how is it sorted? All we know about sorting via Collections.sort(collection, comparator) is that sorting is stable. See more about sorting: https://www.geeksforgeeks.org/sorting-algorithms/

Upvotes: 1

Related Questions