Default sorting in java

Dual Pivot Quick Sort: Java’s default sorting algorithm for primitive data types.

What happens when we do Arrays.sort() in Java? which sorting algorithm does Java use in the background? Since Java 7 release back in 2011, default sorting algorithm used is DualPivotQuickSort which is an enhancement over classic quicksort algorithm. Dual pivot quicksort is a combination of insertion sort and quick sort. Insertion sort has faster runtime when the number of elements to be sorted is small, Double pivot quicksort uses this fact thus when the number of elements is <= 47 Java performs insertion sort under the hood. When input size array is larger than 47 Java uses Double pivot quicksort. As the name suggests DualPivotQuickSort algorithm picks 2 pivots instead of 1. Unlike quicksort in which we partition the array around 1 pivot, we partition the array in three parts around 2 pivots. 1st sub array : items < LP
2nd sub array : LP <= items <= RP
3rd sub array =: items >= RP Algorithm LP: Left Pivot
RP: Right Pivot 1.) Left most item in an array is taken as the left pivot and Rightmost item as the right pivot.
2.) Swap Left pivot with Right Pivot if LP > RP
3.) Partition array in three sub-arrays around left and right pivot. Once a partition is done we perform above 3 steps recursively on three sub-array. Let’s walk through an example-: No need to swap pivots in above image since LP < RP.
Now we partition the array following below schemes. 1st sub array : items < LP
2nd sub array : LP <= items <= RP
3rd sub array =: items >= RP Now we have 3 sub-array over which we’ll perform the same steps as above. Since the first two arrays have only 2 items, one will become left pivot and other will become right pivot. We’ll swap left pivot with right pivot if the left pivot is greater than right pivot which is not the case for first two sub-arrays. For the third sub-array as we can see in below image left pivot is greater than right pivot thus we’ll swap them. Swapping pivots.
We don’t have any more elements in the array that we can partition further.
References https://www.geeksforgeeks.org/dual-pivot-quicksort/
https://stackoverflow.com/questions/20917617/whats-the-difference-of-dual-pivot-quick-sort-and-quick-sort
http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf Conclusion
Similarly, Python uses Timsort which is a combination of insertion sort and merge sort. I’d like to read and write about different other variation of quicksort in the next few days. If you want me to write on a specific topic, please feel free to post them in the comment section below. You can support my work by buying me a coffee below. 💚💚💚💚💚💚 !!

Источник

How to Sort an Array, List, Map or Stream in Java

Learn to sort a Java Set , List and Map of primitive types and custom objects using Comparator, Comparable and new lambda expressions. We will learn to sort in ascending and descending order as well.

//Sorting an array Arrays.sort( arrayOfItems ); Arrays.sort( arrayOfItems, Collections.reverseOrder() ); Arrays.sort(arrayOfItems, 2, 6); Arrays.parallelSort(arrayOfItems); //Sorting a List Collections.sort(numbersList); Collections.sort(numbersList, Collections.reverseOrder()); //Sorting a Set Set to List -> Sort -> List to Set Collections.sort(numbersList); //Sorting a Map TreeMap treeMap = new TreeMap<>(map); unsortedeMap.entrySet() .stream() .sorted(Map.Entry.comparingByValue()) .forEachOrdered(x -> sortedMap.put(x.getKey(), x.getValue())); //Java 8 Lambda Comparator nameSorter = (a, b) -> a.getName().compareToIgnoreCase(b.getName()); Collections.sort(list, nameSorter); Collections.sort(list, Comparator.comparing(Employee::getName)); //Group By Sorting Collections.sort(list, Comparator .comparing(Employee::getName) .thenComparing(Employee::getDob));

1. Sorting a List of Objects

To sort a list of objects, we have two popular approaches i.e. Comparable and Comparator interfaces. In the upcoming examples, we will sort a collection of Employee objects in different ways.

public class Employee implements Comparable

Comparable interface enables the natural ordering of the classes that implements it. This makes the classes comparable to its other instances.

A class implementing Comparable interface must override compareTo() method in which it can specify the comparison logic between two instances of the same class.

• Lists (and arrays) of objects that implement Comparable interface can be sorted automatically by Collections.sort() and Arrays.sort() APIs.
• Objects that implement this interface will be automatically sorted when put in a sorted map (as keys) or sorted set (as elements).
• It is strongly recommended (though not required) that natural orderings be consistent with equals() method. Virtually all Java core classes that implement Comparable have natural orderings that are consistent with equals() .

ArrayList list = new ArrayList<>(); //add employees.. Collections.sort(list);

To sort the list in reversed order, the best way is to use the Comparator.reversed() API that imposes the reverse ordering.

ArrayList list = new ArrayList<>(); //add employees.. Collections.sort(list, Comparator.reversed());

When not seeking the natural ordering, we can take the help of Comparator interface to apply custom sorting behavior.

Comparator does not require modifying the source code of the class. We can create the comparison logic in a separate class which implements Comparator interface and override its compare() method.

During sorting, we pass an instance of this comparator to sort() method along with the list of custom objects.

For example, we want to sort the list of employees by their first name, while the natural sorting has been implemented by id field. So, to sort on name field, we must write the custom sorting logic using Comparator interface.

import java.util.Comparator; public class NameSorter implements Comparator<Employee> < @Override public int compare(Employee e1, Employee e2) < return e1.getName().compareToIgnoreCase( e2.getName() ); >>

Notice the use of NameSorter in sort() method as the second argument in the given example.

ArrayList list = new ArrayList<>(); //add employees to list Collections.sort(list, new NameSorter());

To do the reverse sorting, we just need to call the reversed() method on the Comparator instance.

ArrayList list = new ArrayList<>(); //add employees to list Collections.sort(list, new NameSorter().reversed());

1.3. Sorting with Lambda Expressions

Lambda expressions help in writing Comparator implementations on the fly. We do not need to create a separate class to provide the one-time comparison logic.

Comparator nameSorter = (a, b) -> a.getName().compareToIgnoreCase(b.getName()); Collections.sort(list, nameSorter);

To apply SQL style sorting on a collection of objects on different fields (group by sort), we can use multiple comparators in a chain. This chaining of comparators can be created using Comparator.comparing() and Comparator.thenComparing() methods.

For example, we can sort the list of employees by name and then sort again by their age.

ArrayList list = new ArrayList<>(); //add employees to list Collections.sort(list, Comparator .comparing(Employee::getName) .thenComparing(Employee::getDob));

Use java.util.Arrays.sort() method to sort a given array in a variety of ways. The sort() is an overloaded method that takes all sorts of types as the method argument.

This method implements a Dual-Pivot Quicksort sorting algorithm that offers O(n log(n)) performance on all data sets and is typically faster than traditional (one-pivot) Quicksort implementations.

Java program to sort an array of integers in ascending order using Arrays.sort() method.

//Unsorted array Integer[] numbers = new Integer[] < 15, 11, . >; //Sort the array Arrays.sort(numbers);

Java provides Collections.reverseOrder() comparator to reverse the default sorting behavior in one line. We can use this comparator to sort the array in descending order.

Note that all elements in the array must be mutually comparable by the specified comparator.

//Unsorted array Integer[] numbers = new Integer[] < 15, 11, . >; //Sort the array in reverse order Arrays.sort(numbers, Collections.reverseOrder());

Arrays.sort() method is an overloaded method and takes two additional parameters i.e. fromIndex (inclusive) and toIndex (exclusive).

When provided above arguments, the array will be sorted within the provided range from position fromIndex to position toIndex .

Given below is an example to sort the array from element 9 to 18. i.e. will be sorted and the rest elements will not be touched.

//Unsorted array Integer[] numbers = new Integer[] < 15, 11, 9, 55, 47, 18, 1123, 520, 366, 420 >; //Sort the array Arrays.sort(numbers, 2, 6); //Print array to confirm System.out.println(Arrays.toString(numbers));

[15, 11, 9, 18, 47, 55, 1123, 520, 366, 420]

Java 8 introduced lots of new APIs for parallel processing data sets and streams. One such API is Arrays.parallelSort() .

The parallelSort() method breaks the array into multiple sub-arrays and each sub-array is sorted with Arrays.sort() in different threads. Finally, all sorted sub-arrays are merged into one sorted array.

The output of the parallelSort() and sort() , both APIs, will be same at last. It’s just a matter of leveraging the Java concurrency.

 
//Parallel sort complete array Arrays.parallelSort(numbers); //Parallel sort array range Arrays.parallelSort(numbers, 2, 6); //Parallel sort array in reverse order Arrays.parallelSort(numbers, Collections.reverseOrder());
 
There is no direct support for sorting the Set in Java. To sort a Set , follow these steps:
 
 
Convert Set to List .
 
Sort List using Collections.sort() API.
 
Convert List back to Set .
 
 
//Unsorted set HashSet numbersSet = new LinkedHashSet<>(); //with Set items List numbersList = new ArrayList(numbersSet) ; //set -> list //Sort the list Collections.sort(numbersList); //sorted set numbersSet = new LinkedHashSet<>(numbersList); //list -> set
 
A Map is the collection of key-value pairs. So logically, we can sort the maps in two ways i.e. sort by key or sort by value.
 
The best and most effective a sort a map by keys is to add all map entries in TreeMap object. TreeMap stores the keys in sorted order, always.
 
HashMap map = new HashMap<>(); //Unsorted Map TreeMap treeMap = new TreeMap<>(map); //Sorted by map keys
 
In Java 8, Map.Entry class has static method comparingByValue() to help us in sorting the Map by values.
 
The comparingByValue() method returns a Comparator that compares Map.Entry in natural order on values.
 
HashMap unSortedMap = new HashMap<>(); //Unsorted Map //LinkedHashMap preserve the ordering of elements in which they are inserted LinkedHashMap sortedMap = new LinkedHashMap<>(); unSortedMap.entrySet() .stream() .sorted(Map.Entry.comparingByValue()) .forEachOrdered(x -> sortedMap.put(x.getKey(), x.getValue()));
 
In the above-given examples, we learned to sort an Array, List, Map, and Set.
 
We saw different ways to initialize and use Comparator interface including lambda expressions. We also learned to effectively use the Comparator interface.
 
Источник
 
Set by Default Sorted or Not?
 
Need some information that Set default sort Integer value when we add but if i Add String to Set it would not sort by default. Update: and Also Caps letter would always Sorted after runs many times. java version "1.6.0_26" Java(TM) SE Runtime Environment (build 1.6.0_26-b03) Java HotSpot(TM) Client VM (build 20.1-b02, mixed mode, sharing) please give me some idea. Thanks
 
4 Answers 4
 
HashSet does not guaranteed that its contents will be sorted in any way. There is a special interface for sets that do provide such a guarantee: it's called SortedSet :
 
 
A Set that further provides a total ordering on its elements. The elements are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time. The set's iterator will traverse the set in ascending element order. Several additional operations are provided to take advantage of the ordering. (This interface is the set analogue of SortedMap .)
 
 
In Java 6, there are two classes that implement this interface: ConcurrentSkipListSet and TreeSet .
 
No, HashSet is not sorted - or at least, not reliably. You may happen to get ordering in some situations, but you must not rely on it. For example, it's possible that it will always return the entries sorted by "hash code modulo some prime" - but it's not guaranteed, and it's almost certainly not useful anyway.
 
If you need a sorted set implementation, look at TreeSet .
 
@Ravi: That wasn't what I meant by resizing the hash table. Try inserting enough items to go above your hashmap's load factor and see what happens.
 
From Oracle documentation we can find the HashSet class implements the set interface and internally backed by Hash Table.It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. But My code Which is given bellow finds it sorted even after running number of time.
 
 public static void main(String[] args) < Random rand = new Random(47); SortedSetintset = new TreeSet(); Set intsetUnsorted = new HashSet(); for(int i=0;i <10000;i++)< intset.add(rand.nextInt(30)); >intsetUnsorted.add(500); for(int i=0;i <10000;i++)< intsetUnsorted.add(rand.nextInt(30)); >String version = System.getProperty("java.version"); System.out.println("JDK version-"+version); System.out.println("TreeSet o/p"); System.out.println(intset); System.out.println("Hash Set o/p"); System.out.println(intsetUnsorted); > 
 
JDK version-1.6.0 TreeSet o/p [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29] Hash Set o/p [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 16, 19, 18, 21, 20, 23, 22, 25, 24, 27, 26, 29, 28, 500] 
 
Источник