Sorting is an important operation in computer science, and it has many practical applications. There are many different algorithms for sorting, each with its own advantages and disadvantages. In this blog, we will compare several popular sorting algorithms in Java and provide code snippets for each.

1. Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Although it is simple, bubble sort is relatively inefficient and is not commonly used in practice.

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. Insertion Sort

Insertion sort is another simple sorting algorithm that builds the final sorted array one item at a time. It works by iterating through the array, and for each element, it finds the correct position to insert it. Insertion sort is efficient for small arrays, but it becomes inefficient for large arrays.

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

3. Selection Sort

Selection sort is an in-place comparison sorting algorithm that divides the input array into two parts: the sorted part and the unsorted part. It then repeatedly selects the smallest element from the unsorted part and swaps it with the first element of the unsorted part. Selection sort has O(n^2) time complexity, and it is inefficient for large lists.

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

4. Merge Sort

Merge sort is a divide and conquer algorithm that recursively divides the array into two halves, sorts each half, and then merges the two sorted halves. It has a time complexity of O(n log n), and it is a stable sorting algorithm.

public static void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

public static void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int[] L = new int[n1];
    int[] R = new int[n2];
    for (int i = 0; i < n1; ++i) {
        L[i] = arr[l + i];
    }
    for (int j = 0; j < n2; ++j) {
        R[j] = arr[m + 1 + j];
    }
    int i = 0, j = 0;
    int k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

4. Quick Sort

Quick sort is another divide-and-conquer algorithm that partitions the array into two parts, and then recursively sorts each part. The partitioning is done such that all the elements on the left of the pivot are smaller than the pivot, and all the elements on the right of the pivot are larger than the pivot. Quick sort has a time complexity of O(n log n), and it is an efficient algorithm for large lists.

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

Conclusion

Sorting is a fundamental operation in computer science and is widely used in many applications. In this blog, we have explored and compared different sorting algorithms in Java. Each algorithm has its strengths and weaknesses, and the best choice depends on the specific use case.

Bubble sort, selection sort, and insertion sort are simple and easy to implement, but their performance is not optimal, especially for large datasets. Merge sort and quick sort are more efficient, with a time complexity of O(n log n), and are suitable for large datasets. However, merge sort requires additional memory, while quick sort can be unstable and has worst-case time complexity of O(n^2).

When selecting a sorting algorithm, it is important to consider the size of the input data, the data type of the elements, and other requirements of the application. By understanding the different algorithms and their complexities, we can choose the best algorithm for our use case.

In summary, sorting algorithms are essential tools for programmers, and the choice of algorithm depends on the specific use case. Whether you are sorting a list of names, numbers, or any other data, it is important to understand the different sorting algorithms and their strengths and weaknesses to make the best choice for your application.