What exactly is a Sorting Algorithm?
Sorting is a class of algorithms tasked with changing the positions of array members so that they are all in ascending or descending order. A decent Sorting algorithm must also ensure that elements with the same value do not move in the sorted array. Sorting is required to gain a solid understanding of data structures and algorithms.
5 Popular Java Sorting Algorithms
Java is a universal programming language that can run a wide range of sorting algorithms. Most of these algorithms are flexible and can be implemented in both a recursive and iterative manner. Here are the top five Sorting algorithms in Java:
Merge Sort
Heap Sort
Insertion Sort
Selection Sort
Bubble Sort
Let's take a closer look at each of these Java Sorting techniques.
Merge Sort Algorithm
Merge sort is one of Java's most adaptable Sorting algorithms (no, seriously). It sorts elements in an array using the divide-and-conquer approach. It's also a stable sort, which means it won't modify the order of the initial elements in an array about each other.
The underlying approach divides the array into smaller parts until segments of only two (or one) elements are produced. These segments' elements are now sorted, and the segments are merged to make more significant segments. This method is repeated until the entire array is sorted.
This algorithm is divided into two parts:
mergeSort() - This Function calculates the center index for the subarray and then divides it in half. The first half goes from index left to index middle+1, and the second half runs from index middle+1 to index right. After partitioning, this Function automatically runs the merge() Function to sort the subarray handled by the mergeSort() call.
Merge () - This Function handles all the heavy lifting for the Sorting process. It requires four parameters to be entered:
The array
The beginning index (left)
The middle index (middle)
The ending index (right)
When the subarray is received, merge() divides it into two subarrays, one on the left and one on the right. The left subarray extends from index left to index middle+1, whereas the right subarray extends from index middle+1 to index right. The sorted subarray is then obtained by merging the two subarrays.
Example:
import java.util.Arrays;
// Merge sort in Java
class Main {
// Merge two sub-arrays, L and M, into an array
void merge(int array[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int L[] = new int[n1];
int M[] = new int[n2];
//Fill the left and right array
for (int i = 0; i < n1; i++)
L[i] = array[p + i];
for (int j = 0; j < n2; j++)
M[j] = array[q + 1 + j];
// Maintain current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = p;
// Until we reach either end of either L or M, pick larger among
// elements L and M and place them in the correct position at A[p..r]
// for sorting in descending
// use if(L[i] >= <[j])
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
array[k] = L[i];
i++;
} else {
array[k] = M[j];
j++;
}
k++;
}
// When we run out of elements in either L or M,
//Pick up the remaining elements and put in A[p..r]
while (i < n1) {
array[k] = L[i];
i++;
k++;
}
while (j < n2) {
array[k] = M[j];
j++;
k++;
}
}
// Divide the array into two sub-arrays, sort them, and merge them
void mergeSort(int array[], int left, int right) {
if (left < right) {
// m is the point where the array is divided into two sub-arrays
int mid = (left + right) / 2;
// recursive call to each sub-array
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
// Merge the sorted sub-arrays
merge(array, left, mid, right);
}
}
public static void main(String args[]) {
// created an unsorted array
int[] array = { 6, 5, 12, 10, 9, 1 };
Main ob = new Main();
// call the method mergeSort()
// pass argument: array, first index and last index
ob.mergeSort(array, 0, array.length - 1);
System.out.println("Sorted Array:");
System.out.println(Arrays.toString(array));
}
}
Output:
Unsorted Array:
[6, 5, 12, 10, 9, 1]
Sorted Array:
[1, 5, 6, 9, 10, 12]
Heap Sort Algorithm
In Java, heap sorting is one of the essential Sorting methods that everybody interested in sorting should master. It blends the notions of a tree with Sorting, properly emphasizing both. A heap is a complete binary search tree that stores items in a specific sequence based on the demand.
A min-heap has the smallest element at the root, and each child of the root must be greater than the root itself. The children at the next level must be older than these youngsters, and so on. A max-heap, on the other hand, has the maximum element at the root. The heap is kept as an array for the Sorting operation, with the left child at index 2 * i + 1 and the correct child at index 2 * i + 2 for each parent node at position i.
The elements of the unsorted array are used to construct a max heap, and the maximum element is retrieved from the root of the array and exchanged with the array's last element. After that, the max heap is rebuilt to obtain the next maximum element. This method is repeated until just one node is left in a heap.
This algorithm is divided into two parts:
heapSort(): This Function aids in initially constructing the maximum heap for utilization. After that, each root element is taken and moved to the end of the array. After that, the max heap is rebuilt from the root. The root is extracted once more and transferred to the end of the array, and thus the process continues.
heapify(): The heap sort method is built on this Function. This Function computes the maximum from the element under consideration as the root and its two children. The root and its child are switched if the maximum is found among the root's offspring. This procedure is then carried out for the new root. The Function terminates when the maximum element in the array is identified (such that its children are more minor than it). The left child of the node at index i is at index 2 * i + 1, and the right child is at index 2 * i + 1. (Because array indexing begins at 0, the root is at 0).
Example:
// Heap Sort in Java
public class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
// Build the max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
//heap sort
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify root element
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
// Find the largest among root, left child, and right child
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
// Swap and continue heapifying if the root is not the largest
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
//Function to print an array
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver code
public static void main(String args[]) {
int arr[] = { 1, 12, 9, 5, 6, 10 };
HeapSort hs = new HeapSort();
hs.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
Output:
Sorted array is
1 5 6 9 10 12
Insertion Sort Algorithm
If you're tired of more difficult Sorting algorithms and want to try something new, insertion sort is the way to go. While there are more optimized techniques for sorting an array, it is one of the simpler ones. Implementation is also relatively simple. In insertion sort, an element is chosen and considered the key. If the key is smaller than its predecessor, it is moved to its proper place in the array.
Algorithm:
START
Repeat steps 2–4 until the end of the array is reached.
Compare the current index i element to its predecessor. Step 3 should be repeated if it is smaller.
Continue shifting elements from the array's "sorted" section until the correct location of the key is determined.
loop variable incrementation
STOP
Example:
public class InsertionSortExample {
public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
}
array[i+1] = key;
}
}
public static void main(String a[]){
int[] arr1 = {9,14,3,2,43,11,58,22};
System.out.println("Before Insertion Sorting");
for(int i:arr1){
System.out.print(i+" ");
}
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int i:arr1){
System.out.print(i+" ");
}
}
}
Output:
Before Insertion Sorting 9 14 3 2 43 11 58 22
After Insertion Sorting 2 3 9 11 14 22 43 58
Selection Sort Algorithm
Some of the most popular Sorting algorithms that are simple to learn and apply include quadratic sorting algorithms. These do not provide a unique or optimized technique for sorting the array; instead, they should serve as building blocks for someone new to the concept of Sorting. Selection sort employs two loops.
The inner loop one selects the smallest member in the array and shifts it to the index provided by the outer loop. Every time the outer loop is executed, one element in the array is relocated to its proper spot. It is also a popular sorting method in Java and Python.
Algorithm
START
Run two loops, one inner and one outer.
Repeat procedures until the smallest element is discovered.
Make the element identified by the outer loop variable the minimum.
If the current element in the inner loop is less than the marked minimum element, set the minimum element's value to the current element.
Swap the value of the minimal element with the value of the outer loop variable.
STOP
Example:
// Selection sort in Java
import java.util.Arrays;
public class SelectionSort {
void selectionSort(int array[]) {
int size = array.length;
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
// To sort in descending order, change > to < in this line.
// Select the minimum element in each loop.
if (array[i] < array[min_idx]) {
min_idx = i;
}
}
//Put min at the correct position
int temp = array[step];
array[step] = array[min_idx];
array[min_idx] = temp;
}
}
// driver code
public static void main(String args[]) {
int[] data = { 11, 99, 15, 8, 1 };
SelectionSort ss = new SelectionSort();
ss.selectionSort(data);
System.out.println("Sorted Array in Ascending Order is as follows: ");
System.out.println(Arrays.toString(data));
}
}
Output:
Sorted Array in Ascending Order is as follows:
[1, 8, 11, 15, 99]
Bubble Sort Algorithm
Bubble sort and selection sort are the two algorithms that most beginners begin their sorting career with. These Sorting algorithms are inefficient, but they provide essential information on what Sorting is and how a Sorting algorithm works behind the scenes.
Instead of a single-like selection sort, bubble sort uses many swaps. The algorithm loops through the array, swapping out elements that must be appropriately placed.
Algorithm:
START
Run two loops, one inner and one outer.
Steps should be repeated until the outer loop is exhausted.
Swap their values if the current element in the inner loop is smaller than the next element.
STOP
Example:
public class BubbleSortExample {
static void bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(arr[j-1] > arr[j]){
//swap elements
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
public static void main(String[] args) {
int arr[] ={3,60,35,2,45,320,5};
System.out.println("Array Before Bubble Sort");
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
bubbleSort(arr);//sorting array elements using bubble sort
System.out.println("Array After Bubble Sorting");
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
}
}
Output:
Array Before Bubble Sort
3 60 35 2 45 320 5
Array After Bubble Sort
2 3 5 35 45 60 320
Sorting Algorithm Complexity
The time complexity and spatial complexity of any Sorting method determine its efficiency.
Time Complexity: The time it takes an algorithm to finish its execution with the input size. It can be expressed in several ways:
Big-O notation (O)
Omega notation
Theta notation (Θ)
Space Complexity: The total amount of memory the method uses for a complete execution is called space complexity. It contains both auxiliary memory and input.
The auxiliary memory is the extra space the method occupies in addition to the input data. Auxiliary memory is typically used to calculate an algorithm's space complexity.
Benefits of Sorting Algorithms in Java
Sorting algorithms are a fundamental component of computer programming and are frequently utilized in various applications, including Java. Java's standard library includes several built-in Sorting algorithms, such as Arrays.sort() and Collections.sort(), which have several advantages. Here are some of the benefits of sorting algorithms in Java:
Sorting algorithms are meant to efficiently rearrange items in a specific order, which can increase the performance of applications that require sorted data. The Sorting algorithms in Java are performance-optimized and designed to handle massive datasets efficiently, making them appropriate for high-performance applications.
Java includes several Sorting algorithms, including quicksort, mergesort, heapsort, and insertion sort, that can be utilized depending on the application's needs. This flexibility enables developers to select the best Sorting algorithm based on parameters such as dataset size, data type, and desired performance characteristics.
Because they are part of the standard library and do not require any additional third-party libraries or code, Java's built-in sorting algorithms are simple to use. To sort arrays or collections of objects, developers can call Arrays.sort() or Collections.sort() methods with the proper arguments, making it simple to build sorting capabilities in Java applications.
Java's Sorting algorithms are stable, which means that the relative order of equal elements is maintained during the Sorting process. This is useful in applications where maintaining the relative order of identical components is critical, such as when sorting objects based on various criteria.
Customization is possible with Java's Sorting algorithms thanks to the usage of comparators. Comparators define the comparison mechanism for sorting elements, allowing developers to sort objects using specific criteria. This enables greater flexibility and agility in data sorting based on unique application requirements.
Java's built-in Sorting algorithms work in tandem with the Java Collections Framework, which offers a diverse variety of data structures such as lists, sets, and maps. This makes it simple to sort object collections without creating custom sorting logic.
The Sorting algorithms in Java have been rigorously tested and optimized for performance and stability. They are part of the standard Java library and are frequently used in production contexts. Thus their dependability and robustness are guaranteed.
Conclusion
Finally, sorting algorithms in Java have various benefits: efficiency, flexibility, ease of usage, stability, customization, integration with the Java Collections Framework, and reliability. Java includes performance-optimized Sorting algorithms, allowing developers to quickly sort arrays or collections of objects based on their individual needs. These Sorting algorithms have been thoroughly evaluated and are frequently used in production contexts, making them a solid choice for sorting data in Java applications. Whether sorting small or large datasets, Java's Sorting algorithms help organize data and optimize Java application performance.
Read More: Searching & Sorting Algorithms in Java
Comentarios