Sorting Algorithms in Java

Sorting Algorithms in Java

Sorting is the technique that puts the elements of an array or list either in descending or ascending order. For example, take an array A, whose elements are {x1, x2, x3, … xn}.

The array A is said sorted when its elements either follow ascending order, i.e., x1 > x2 > x3 > … > xn, or descending order, i.e., x1 < x2 < x3 < … < xn. The sorting algorithms in Java talks about various algorithms that can be used for sorting the elements of the array or list.

Different algorithms of sorting

The following table demonstrates the different sorting algorithms that are used data structure.

Sorting Algorithms	Description
Merge Sort	It works on the principle of divide and conquer. This algorithm divides the given list into two halves of equal lengths. Those halves are recursively divided into further equal halves. These halves are sorted and then merge, ultimately resulting in the sorted list.
Quick Sort	It is a type of comparison sort which also follows the divide and conquer approach. In this algorithm, elements are chosen as the pivot, and then sorting is done.
Bubble Sort	Bubble sort is one of the simplest sorting algorithms that swaps adjacent elements of the given list till the array is sorted. Sometimes the bubble sort is also known as the sinking sort.
Insertion Sort	It puts an unsorted element at its appropriate position in each iteration, similar to the arrange of playing cards.
Selection Sort	It finds the smallest, second smallest, third smallest element, and so on in each iteration. Selection sort is not commonly used because better algorithms such as merge insertion or quick sort are present.
Heap Sort	Heap sort uses the binary heap for doing the sorting. For sorting in ascending order, a min-heap is used. For sorting in descending order, a max-heap is used.
Radix Sort	Radix sort is also known as the non-comparative sorting algorithm. This is because, unlike other sorting algorithms, it does not do the sorting of elements. In this sorting algorithm, sorting is done on the basis of digits of the number, moving from LSD (Least Significant Digit) to MSD (Most Significant Digit) of the number present in the list.
Topological Sort	It is used in a directed acyclic graph to put the linear style of the ordering of elements, where for every directed edge like x -> y, x comes before y. Topological sorting can be achieved by DFS (Depth First Search) as well as BFS (Breadth-First Search).
Bucket Sort	In this type of sorting, an element of the given list is put into a number of buckets. Each bucket is then sorted using different algorithms. In the end, the concatenation of the buckets gives the sorted list.
Counting Sort	To sort numbers between a given range provided the range is small, counting sort is used. Counting sort does not make any comparison between the elements of the list; hence it works very fast. In counting sort, the rank of the elements is found to do the sorting.

We will discuss each sorting algorithm in the coming sections.