Sorting Algorithms in Java: Bubble, Selection, Insertion, Merge, and Quick Sort

Introduction to Sorting Algorithms

Sorting is a fundamental operation in computer science that arranges data in a particular order—typically ascending or descending. Efficient sorting is crucial for optimizing performance in searching, data processing, and algorithmic problem-solving. Java provides various sorting algorithms, each with its own advantages and applications.

This tutorial explores Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort with Java implementations, complexity analysis, comparisons, and real-world applications.

Comparison of Sorting Algorithms

The table below provides a comparison of different sorting algorithms based on time complexity, space complexity, and stability:

Sorting Algorithms with Java Implementation

1. Bubble Sort

Bubble Sort is a simple algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process repeats until the list is sorted.

Java Implementation:

public class BubbleSort {

    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;

                }

            }

        }

    }

    public static void main(String args[]) {

        int arr[] = {64, 25, 12, 22, 11};

        bubbleSort(arr);

        System.out.println(java.util.Arrays.toString(arr));

    }

}

Time Complexity:

• Best Case: O(n) (already sorted)
• Worst & Average Case: O(n²)

Space Complexity: O(1)

2. Selection Sort

Selection Sort repeatedly finds the minimum element from the unsorted portion and swaps it with the first unsorted element.

Java Implementation:

public class SelectionSort {

    static void selectionSort(int arr[]) {

        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {

            int minIndex = i;

            for (int j = i + 1; j < n; j++) {

                if (arr[j] < arr[minIndex]) {

                    minIndex = j;

                }

            }

            int temp = arr[minIndex];

            arr[minIndex] = arr[i];

            arr[i] = temp;

        }

    }

    public static void main(String args[]) {

        int arr[] = {64, 25, 12, 22, 11};

        selectionSort(arr);

        System.out.println(java.util.Arrays.toString(arr));

    }

}

Time Complexity:

• Best, Worst & Average Case: O(n²)

Space Complexity: O(1)

3. Insertion Sort

Insertion Sort builds the sorted array one element at a time by inserting each new element into its correct position.

Java Implementation:

public class InsertionSort {

    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;

        }

    }

    public static void main(String args[]) {

        int arr[] = {64, 25, 12, 22, 11};

        insertionSort(arr);

        System.out.println(java.util.Arrays.toString(arr));

    }

}

Time Complexity:

• Best Case: O(n)
• Worst & Average Case: O(n²)

Space Complexity: O(1)

4. Merge Sort

Merge Sort is a divide and conquer algorithm that splits the array into halves, sorts each half, and merges them back.

Java Implementation:

public class MergeSort {

    static void mergeSort(int arr[], int left, int right) {

        if (left < right) {

            int mid = left + (right - left) / 2;

            mergeSort(arr, left, mid);

            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);

        }

    }

    static void merge(int arr[], int left, int mid, int right) {

        int n1 = mid - left + 1;

        int n2 = right - mid;

        int leftArray[] = new int[n1];

        int rightArray[] = new int[n2];

        System.arraycopy(arr, left, leftArray, 0, n1);

        System.arraycopy(arr, mid + 1, rightArray, 0, n2);

        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2) {

            if (leftArray[i] <= rightArray[j]) {

                arr[k] = leftArray[i++];

            } else {

                arr[k] = rightArray[j++];

            }

            k++;

        }

        while (i < n1) arr[k++] = leftArray[i++];

        while (j < n2) arr[k++] = rightArray[j++];

    }

    public static void main(String args[]) {

        int arr[] = {64, 25, 12, 22, 11};

        mergeSort(arr, 0, arr.length - 1);

        System.out.println(java.util.Arrays.toString(arr));

    }

}

Time Complexity:

• Best, Worst & Average Case: O(n log n)

Space Complexity: O(n)

5. Quick Sort

Quick Sort selects a pivot, partitions the array around the pivot, and recursively sorts the partitions.

Java Implementation:

public class QuickSort {

    static void quickSort(int arr[], int low, int high) {

        if (low < high) {

            int pivotIndex = partition(arr, low, high);

            quickSort(arr, low, pivotIndex - 1);

            quickSort(arr, pivotIndex + 1, high);

        }

    }

    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;

    }

    public static void main(String args[]) {

        int arr[] = {64, 25, 12, 22, 11};

        quickSort(arr, 0, arr.length - 1);

        System.out.println(java.util.Arrays.toString(arr));

    }

}

Time Complexity:

• Best & Average Case: O(n log n)
• Worst Case: O(n²)

Space Complexity: O(log n)

Final Thoughts

This tutorial provides a comprehensive guide on sorting algorithms, their implementations, and comparisons. Whether you're a beginner or an experienced programmer, mastering sorting algorithms will enhance your problem-solving skills. 🚀