Sorting Algorithms in Java

Sorting is the process of arranging elements in a specific order (usually ascending or descending). This tutorial covers common sorting algorithms implemented in Java, with practical examples and visual explanations.

Why Sorting Matters

Sorting is a fundamental operation in computer science for several reasons:

• It makes searching more efficient (enabling binary search)
• It simplifies finding duplicates, minimum, and maximum values
• It’s essential for many algorithms and data processing tasks
• It helps in presenting data in a more readable format

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.

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]) {
                // Swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Bubble sort is easy to understand but inefficient for large datasets.

Selection Sort

Selection sort divides the input list into two parts: the sorted sublist and the unsorted sublist. It repeatedly finds the minimum element from the unsorted sublist and moves it to the beginning of the unsorted sublist.

public static void selectionSort(int[] arr) {
    int n = arr.length;

    for (int i = 0; i < n - 1; i++) {
        // Find the minimum element in unsorted array
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap the found minimum element with the first element
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Selection sort performs well on small lists but is inefficient for large datasets.

Insertion Sort

Insertion sort builds the final sorted array one item at a time. It is efficient for small data sets and nearly sorted 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;

        // Move elements greater than key to one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Quick Sort

Quick sort is a divide-and-conquer algorithm that works by selecting a ‘pivot’ element and partitioning the array around the pivot.

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        // Partition the array and get the pivot position
        int pivotIndex = partition(arr, low, high);

        // Sort the subarrays
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

private 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++;
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // Swap arr[i+1] and arr[high] (pivot)
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

Quick sort is generally faster than other sorting algorithms for large datasets.

Merge Sort

Merge sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves.

public 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);
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    // Create temporary arrays
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] L = new int[n1];
    int[] R = new int[n2];

    // Copy data to temporary arrays
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    // Merge the temporary arrays
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy remaining elements
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Merge sort is stable and predictable but requires additional memory.

Choosing the Right Sorting Algorithm

When selecting a sorting algorithm, consider:

Using Java’s Built-in Sorting Methods

Java provides built-in methods for sorting:

// For arrays
import java.util.Arrays;

int[] numbers = {5, 3, 8, 4, 2};
Arrays.sort(numbers);  // numbers is now {2, 3, 4, 5, 8}

// For ArrayLists
import java.util.ArrayList;
import java.util.Collections;

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(5, 3, 8, 4, 2));
Collections.sort(list);  // list is now [2, 3, 4, 5, 8]

// Custom sorting with Comparator
ArrayList<String> names = new ArrayList<>(Arrays.asList("Charlie", "Alice", "Bob"));
Collections.sort(names, (a, b) -> a.length() - b.length());  // Sort by length

Conclusion

Sorting algorithms are essential tools in a programmer’s toolkit. While understanding how different sorting algorithms work is important, for most practical applications, Java’s built-in sorting methods are optimized and sufficient.

When implementing your own sorting algorithm, consider:

1. The size and nature of your data
2. Whether stability is important (preserving the relative order of equal elements)
3. Memory constraints
4. Performance requirements

By choosing the right sorting algorithm for your specific needs, you can significantly improve the efficiency of your Java applications.