Differencebetween an Ordered and a Sorted Collection

What's the difference between ordering and sorting?

• An "ordering" is basically a set of rules that determine what items come before, or after, what other items. IE: the relative order items would appear in if they were sorted. For collections that enforce an ordering, that ordering is generally specified in terms of comparison operators (particularly <), interfaces (a la Java's Comparable<T>), or comparison callbacks and/or function objects (like C++'s std::less).

  There are also collections described as "ordered collections". Slightly different use of the word, but related meaning. What that means is that the collection represents a sequence of items, and thus has some inbuilt concept of order. (Contrast with, say, hash tables. You add something to a hash table, you have no idea where it'll appear if ever you iterate over the contents. With an ordered collection, you know.) Lists, vectors, arrays, etc are the quintessential ordered collections. For a non-list example, though, PHP's "array" type is actually an "ordered map" — a dictionary type where the order of keys is retained. Keys appear in the order in which they were first inserted (or the order in which you last put them with a ksort() or the like) when you iterate over the array.

• "Sorting" is the process of actually arranging a sequence of items in accordance with a given ordering. It's typically only done with ordered collections...as it doesn't make much sense to put one item before another in a container that has no concept of "before" or won't let you rearrange items in the first place. (Structures like sets and heaps can use an ordering too, and adding and removing entries alters the underlying tree based on the ordering. One could argue they're "sorting" bit by bit. But the word is typically used to represent an operation that does the rearranging all at once.)

Difference between Collections.sort() and getting a sorted collection by adding into a TreeSet?

The difference is that a TreeSet keeps you data sorted at all times while the Collections.sort() method sorts it when you call the method on your Set.

The time complexity of Collections.sort() is O(n*log(n)) while the TreeSet's add()'s complexity is log(n). If you use the same size of data then the complexity in the TreeSet's case will be the same because you repeat the add operation n times.

So you only have to decide whether you want your Set ordered at all times or just at some point. If there is a case in your code when you don't need sorting then you don't need TreeSet but if you will always need it to be sorted then you should use TreeSet.

Please keep in mind that if you want to sort your Set you have to create a List from it first which might introduce some overhead!

Another caveat: As others mentioned TreeSet can only take 1 Comparator while you can supply different Comparators to Collections.sort(). So it depends on your usage. You should give us more information on your use case in order to give you a thorough answer.

Order By vs Sort for creating ordered collection

• You use Sort when you want to sort the original list. It performs an in-place sort.
• You use OrderBy when you don't want to change the original list as it returns an IOrderedEnumerable<T> that leaves the original list untouched. Or when you don't have a list but some other enumerable.

Difference between Collections.sort(list) and Collections.sort(list,comparator)

Collections.sort(List<T>) sorts the given List by the natural ordering of its elements. The natural ordering of an object can be defined by implementing the Comparable interface in the corresponding class. This interface provides a single method, compareTo, which returns

a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

On the other hand, Collections.sort(List<T>, Comparator<T>) orders the List's elements according to the given Comparator. Their natural ordering will be ignored for the sorting. This second method comes in hand when the List's elements already possess their natural ordering but we want to order them by a different criteria.

Here's a simple example with a Person class displaying name, last name and age.

class Person implements Comparable<Person> {
    private String name, lastName;
    private int age;

    public Person(String name, String lastName, int age) {
        this.name = name;
        this.lastName = lastName;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public String getLastName() {
        return lastName;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Person o) {
        //Defining Person's natural ordering by creating a comparator and comparing by last name and then name the current object and the given paramter 
        return Comparator.comparing(Person::getLastName).thenComparing(Person::getName).compare(this, o);
    }

    @Override
    public String toString() {
        return String.format("%s %s %d", name, lastName, age);
    }

    public static void main(String[] args) {
        List<Person> list = new ArrayList<>(List.of(
                new Person("Matt", "O'Brien", 30),
                new Person("Conan", "O'Brien", 25),
                new Person("Frank", "Johnson", 50)
        ));

        //Original unordered list
        System.out.println(list);

        //List ordered by Person's natural ordering (last name and then name)
        Collections.sort(list);
        System.out.println(list);

        //List ordered by custom criteria (age)
        Collections.sort(list, Comparator.comparing(Person::getAge));
        System.out.println(list);
    }
}

difference between natural ordering and total ordering

Total ordering means all values can be compared to all other values. For example, if you have a collection of BigDecimal and String there is no natural total order (but you could invent one)

In Java, the Natural order is defined as the ordering provided by the JVM. This might not match what a people might believe is the natural order. e.g. Strings are sorted ASCIIbetically. Meaning an uppercase Z comes before a lowercase a and 10 is before 2

http://docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html

This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method.

Difference between Collections.sort(list) and list.sort(Comparator)

The method List.sort(comparator) that you are refering to was introduced in Java 8, whereas the utility method Collections.sort has been there since Java 1.2.

As such, you will find a lot of reference on the Internet mentioning that utility method but that's just because it has been in the JDK for a lot longer.

Note that the change in implementation for Collections.sort was made in 8u20.

---

Related Topics