In Java, sorting data can sometimes be a bummer, especially if you don’t know which algorithm to use. In this blog, we’ll review the most used sorting algorithms in different spheres, compare their complexity and provide practical use examples. Afterwards, we will tackle the question of whether you should choose and implement a specific sorting algorithm or instead use libraries in which sorting is already implemented.
For comparisons, we’ll be using “Big O notation” (written as O(*)), which describes the time complexity or speed of a given algorithm.
The Famous Ones
According to a study, when it comes to learning sorting algorithms, people usually begin first with inefficient algorithms (which have average time complexity of O(n2) like Bubble sort and Insertion sort and then continue with some faster ones O(n log(n)) like Quicksort and Mergesort. Here, we’ll review only one from each group.
- Bubble Sort
The recurring step is simple – (let’s say we have ascending order) compare the first two values, and if the value of the second element is smaller than the first, we swap their places. Then, we do exactly the same for the next pair of values, and again, if the second element’s value is smaller, we swap those elements.
Although it’s quite simple, it is also quite inefficient as it sometimes requires traversing through the whole list just to move one element. This makes the algorithm’s average complexity of O(n2) where n is the number of items that are being sorted. And despite being this slow, it’s worth mentioning that it is a stable sorting algorithm, which means that it preserves the relative order of equal elements.
Due to this complexity, Bubble sort is avoided almost anywhere – the only two places that is popular is amongst youngsters, who are currently being introduced to sorting algorithms and also in computer graphics due to its capability to detect and fix small errors (in almost-sorted algorithms) with linear complexity (O(2n)), mostly used in a polygon filling algorithm, in which usually small amounts of swapping are required as the elements are initially sorted, and the order can change only at intersections of two lines.
- Quicksort
In comparison with the Bubble sort, the technique is not that simple. The algorithm revolves around one key concept – one element from the list is picked as a pivot, and then the list gets basically split by this pivot into two sub-arrays. The elements of these sub-arrays are determined by whether they are greater or smaller than the chosen pivot. This partitioning is made to the sub-arrays until they are sorted, and then everything gets combined into one list.
Its average time complexity is O(n log(n)), which brings a lot of practical benefits. However, due to the fact that it is not a stable sorting algorithm (it does not preserve the relative order of equal elements), it is often either combined with other algorithms or neglected if a stable one is required.
Thanks to its fast list traversal, it has a wide variety of practical applications in different spheres and topics. The most common use case is in searching (the familiar Ctrl + F) or whenever a task that requires finding an unique element, a pair of elements, frequency distribution or just a simple selection is needed.
Do it Yourself?
Many programmers, who have quite enormous experience in the field, tend to use third-party libraries for sorting instead of implementing the sorting function – examples are Arrays.sort() or Collections.sort(). But why is that? Let’s first see how they work.
- Arrays.sort()
It uses the java.util package, which includes the Arrays class, which provides static methods to dynamically access, create, modify and sort Java arrays. The sorting can be applied to the whole array or only for a particular range.
Under the hood of this sort() method is a dual-pivot Quicksort when it comes to primitives and a stable and adaptive implementation of merge sort algorithm when it comes to non-primitive objects, making it faster and quite efficient as the time complexity is O(n log(n)).
In Java 8, a new method was added in the Arrays class called “parallelSort”.Essentially, it is an Arrays.sort() but with multi-threading – its speed is just a matter of leveraging multi-threading.
We can either sort the whole array, specify a particular range and also choose whether to use a comparator or not (which is required for objects that are not comparable).
- Collections.sort()
What happens if we want to use the Arrays.sort() on different data structures like List, Set and Map? This is where Collections.sort() comes in handy – it does exactly what Arrays.sort() does but supports a huge variety of different data structures.
Considering that the specific algorithms are already implemented and are optimized to an extent, the obvious choice would be to use them instead of re-implementing them again in your projects.
Conclusion and Final Thoughts
As per usual, it depends. One is certain – unless you want to make a modification in the algorithm to behave differently, using the already provided sort() functions would deliver the highest efficiency. In the end, it all comes down to what you need to do: if it’s educational purposes – definitely start with implementing the algorithms by yourself. However, if you just need to simply sort a collection in Java, the Collections.sort() method would be your best friend!
