In this tutorial, we will look at various sorting algorithms and their corresponding implementations in Java.
Table Of Contents
1. What is Sorting
In computer science, java sorting algorithms are used to put elements of a list in a particular order. Most commonly used are numerical order and lexicographical order. Sorting is a fundamental algorithm that enables various other algorithms (Binary Search etc.) to perform efficiently.
More formally, the output of any sorting algorithm must satisfy two conditions:
- Output is in a predefined order (E.g : ascending x1 < x2)
- Output is a permutation – if x1, x2 is original, output cannot be x2,x3
2. Complexity
One way to measure the performance of a java sorting algorithm is to actually run the program and measure it. This is not reasonable as we are interested in the order of growth and many times the size of the input is not exactly predictable. This leads us to the analysis of algorithms in case of time and space complexity with respect to the input size n.
Time complexity – specifically measures how the time increases with an increase in the input size. For example, a binary search can provide a time complexity of O(log n) for searching an already sorted array. We ignore constants and specifically the above notation indicates that the worst-case performance of binary search is log n. Asymptotic notation is used to compare the algorithms without running them. The best case is given by the notation Ω(n) while the average case is given by Θ(n).
The other aspect of the analysis is the space complexity. This matters when we use auxiliary space for our program. For example, Merge Sort which we will see in the below sections uses an auxiliary space to speed up the computation. This would increase the space complexity but in turn, can reduce the time complexity of the algorithm. But bubble sort uses no auxiliary space(space for a single element to swap) and is typically called in-place sorting algorithm. The in-place sorting algorithms typically use O(1) space complexity.
Another dimension of the algorithm is the stability. If two elements in input are the same, in the final sorted output it must be present in the same order of input. This is applicable when we sort by multiple fields. Consider we sort student records of a school that is already sorted by name. If a stable sort is used to sort the students by section result will have students sorted by section but within the student, names will be sorted.
These gives a good set of performance measure to compare and contrast the algorithms and choose the best one according to the needs.
3. Sorting Algorithms in Java
In this section, we will look at the various sorting algorithms and compare their performance with others. For all the algorithms below, we will consider input to be of size n > 0 where n is very large.
3.1. Bubble Sort
Bubble sort is one of the simplest sorting algorithms. It works by repeatedly swapping adjacent elements that are out of order. The idea is to fix the position for nth element first and then n-1 and so on till 0. It is an efficient algorithm with worst-case runtime of O(n2). The algorithm does not need auxiliary space and hence can do with no additional space. For a detailed discussion of the algorithm, you can refer to this article.
3.2. Selection Sort
It is similar to bubble sort but works the other way around. It selects the smallest element from the entire array and moves to the first position. Then it moves onto finding the smallest among 1 to n and so on till we reach all n positions. Basically it selects the element at each position from 0 to n. The worst-case runtime is O(n2) for selection sort as well. For a detailed discussion of the algorithm, you can refer to this article.
3.3. Insertion Sort
Insertion sort works similarly to how we order cards while playing with a deck of cards. During each iteration, let’s say of index j, the array 0 to j will be sorted while j to n is yet to be sorted. It starts with the element in the first position and repeatedly moves elements greater than it to the unsorted list. It is an efficient algorithm for sorting a small set of input and generally used by other algorithms to sort smaller sub-array. The worst-case runtime is O(n2) for insertion sort. For a detailed discussion of the algorithm, you can refer to this article.
3.4. QuickSort
Quicksort is the most widely used sorting algorithm. Quicksort is faster than most other common sorting algorithms. It was developed by the famous Computer Scientist Tony Hoare and it is based on the Divide and Conquer Algorithm. Quicksort works on the principle of recursion. Quicksort picks a random element as a pivot and splits the entire array of elements into two arrays. The left array contains all elements lesser than the pivot while the right subarray contains all elements greater than the pivot. These two sub-arrays recursively undergo the same procedure resulting in a sorted array. The worst case is similar to previous algorithms but the average case is ϴ(nlogn) which makes it attractive for a lot of use cases. For a detailed discussion of the algorithm, you can refer to this article.
3.5. Merge Sort
Merge sort is the fastest among the algorithms considering the worst-case scenario. It has a predictable runtime of nlogn but it uses an auxiliary space of n to perform the sorting. It follows the divide and conquer approach. The algorithm splits the entire array into the smallest sub-arrays as possible. During the merge of the sub-arrays, it compares and creates the merged array in a sorted manner. Since sub-arrays are sorted, the final array will also be in a sorted manner. For a detailed discussion of the algorithm, you can refer to this article.
3.6. Heap Sort
The fundamental component of this algorithm is the minimum Heap which is explained here. In a minimum heap, the minimum element is at the root and given by index 0. Heap Sort works by swapping the root and last element and calls the build Heap Operation to create the tree. It performs this operation n times to ensure the heap tree is built in a sorted manner. It has a very attractive runtime of nlogn and competes with Merge Sort and Quicksort. Heap Sort is an in-place sorting algorithm and generally works better for bigger datasets.
3.7. Counting Sort
Counting Sort is an algorithm for sorting a collection of objects according to keys that are small integers i.e. it is an integer sorting algorithm. This works by using an auxiliary space n+k where k is the largest integer in the list of integers. Let us understand the algorithm with the help of the program and sample data.
public class CountingSort {
public static void main(String[] args) {
final int[] input = { 7, 5, 4, 3, 5, 2, 2, 1 };
final int[] output = new int[input.length];
final int[] count = new int[8];
// Count of occurences
for (int i : input) {
count[i] += 1;
}
// Cumulative sum
for (int i = 1; i < count.length; i++) {
count[i] = count[i] + count[i - 1];
}
// Shift to identify actual position
for (int i = count.length - 1; i > 0; i--) {
count[i] = count[i - 1];
}
count[0] = 0;
// Find each element position
for (int i : input) {
output[count[i]] = i;
count[i] += 1;
}
// Print output
for (int i : output) {
System.out.println(i);
}
}
}The input is an unordered array of 7, 5, 4, 3, 5, 2, 2, 1. The maximum element of the list (k) is 7. So we create an array of 8 elements as Java arrays start with an index of 0. The first step in the algorithm is to create a simple count array where the count of occurrence of each element is stored. The count array looks like this
| Count Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Occurence | 0 | 1 | 2 | 1 | 1 | 2 | 0 | 1 |
The next step is to calculate the cumulative sum of the occurrences of various integers.
| Count Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Occurence | 0 | 1 | 3 | 4 | 5 | 7 | 7 | 8 |
One of the assumptions of Counting sort is going to be a non-zero integer. The next step is to shift the count array positions so that we can fix the correct position for each of the numbers.
| Count Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Occurence | 0 | 0 | 1 | 3 | 4 | 5 | 7 | 7 |
The final step is to just iterate the input array and find its corresponding index from the count array. One additional step is to increment the value in the count array to handle the case of duplicates. So after this step, the array looks like below and the output is sorted.
| Count Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Occurence | 0 | 1 | 3 | 4 | 5 | 7 | 7 | 8 |
4. Summary
We looked at the various sorting algorithms. The below table gives the comparison of space and time complexity among the various algorithms.
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable |
| Bubble | Ω(n2) | ϴ(n2) | O(n2) | 1 | Y |
| Selection | Ω(n2) | ϴ(n2) | O(n2) | 1 | N |
| Insertion | Ω(n) | ϴ(n2) | O(n2) | 1 | Y |
| Quick | Ω(nlogn) | ϴ(nlogn) | O(n2) | logn | N |
| Merge | Ω(nlogn) | ϴ(nlogn) | O(nlogn) | n | Y |
| Heap | Ω(nlogn) | ϴ(nlogn) | O(nlogn) | 1 | N |
| Counting | Ω(n+k) | ϴ(n+k) | O(n+k) | n+k | Y |
4. Download the Source Code
You can download the full source code of this example here: Sorting Algorithms Java Tutorial
