Introduction to Sorting Algorithms in Java — A Brief Beginner’s Overview

5 min readMar 15, 2023

Introduction

Sorting algorithms are fundamental to computer science, as they provide a way to organize and manage data in a structured manner. From searching for specific items in a dataset to optimizing data processing, sorting is an essential skill for every programmer. In this article, we’ll introduce some popular sorting algorithms in Java and provide examples to help you understand their implementation and usage.

Key Concepts in Sorting Algorithms

Before diving into specific sorting algorithms, it’s important to understand some basic concepts:

Comparison-based sorting vs. non-comparison-based sorting: Comparison-based algorithms compare elements of a dataset to determine their order, while non-comparison-based algorithms use other techniques, like counting or radix sort.
Stable vs. unstable sorting: A stable sorting algorithm maintains the relative order of equal elements in the sorted output, while an unstable algorithm does not guarantee this.
In-place vs. out-of-place sorting: In-place sorting algorithms sort the data in the original memory location, requiring minimal extra memory. Out-of-place algorithms use additional memory to perform sorting.
Time complexity and space complexity: These measures indicate how an algorithm’s performance scales with the size of the input data, helping you evaluate its efficiency.

Popular Sorting Algorithms in Java

Let’s briefly overview some popular sorting algorithms:

Bubble Sort

A simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.

Selection Sort

Another comparison-based algorithm that works by dividing the input into a sorted and an unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region and moves it to the end of the sorted region.

Insertion Sort

This comparison-based algorithm builds the sorted output one item at a time. It’s efficient for small data sets or data that is already partially sorted.

Merge Sort

A divide-and-conquer algorithm that recursively divides the input into two halves, sorts each half, and then merges the sorted halves to produce the final sorted output.

Quick Sort

Another divide-and-conquer algorithm that works by selecting a ‘pivot’ element from the list and partitioning the other elements into two groups, according to whether they are less than or greater than the pivot. The sub-lists are then sorted recursively.

Implementing Sorting Algorithms in Java

Here are Java code examples for each algorithm, along with a brief explanation of how they work:

Bubble Sort:

public void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

In Bubble Sort, adjacent elements are compared and swapped if they are in the wrong order. This process is repeated until no swaps are needed, indicating that the list is sorted.

Selection Sort:

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

In Selection Sort, the algorithm divides the input into a sorted and an unsorted region. It repeatedly finds the minimum (or maximum) element in the unsorted region and moves it to the end of the sorted region until the entire list is sorted.

Insertion Sort:

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

Insertion Sort works by building the sorted output one item at a time. For each element, the algorithm compares it with the elements in the sorted region, shifting them right if they are greater than the current element, and inserts the element in its correct position.

Merge Sort:

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

public 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];

    for (int i = 0; i < n1; i++) {
        leftArray[i] = arr[left + i];
    }
    for (int i = 0; i < n2; i++) {
        rightArray[i] = arr[mid + 1 + i];
    }

    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++];
        }
    }

    while (i < n1) {
        arr[k++] = leftArray[i++];
    }
    while (j < n2) {
        arr[k++] = rightArray[j++];
    }
}

Merge Sort is a divide-and-conquer algorithm that recursively divides the input into two halves, sorts each half, and then merges the sorted halves to produce the final sorted output. The `merge` function combines two sorted subarrays into a single sorted array.

Quick Sort:

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

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

Quick Sort is another divide-and-conquer algorithm that works by selecting a ‘pivot’ element from the list and partitioning the other elements into two groups, according to whether they are less than or greater than the pivot. The sub-lists are then sorted recursively. The partition function rearranges the array and returns the pivot index.

Choosing the Right Sorting Algorithm

When selecting a sorting algorithm, consider the following factors:

Size of the dataset
Whether the data is already partially sorted
The importance of stability or extra memory usage

Keep in mind that each algorithm has its best-case, average-case, and worst-case scenarios, which impact performance. Understanding these scenarios will help you choose the right algorithm based on the problem and data set.

Conclusion

Understanding sorting algorithms in Java is crucial for any programmer, as it helps optimize data processing and manipulation tasks. By practicing the examples provided and exploring more advanced sorting algorithms, you’ll develop a solid foundation in this essential area of computer science. I encourage you to share your experiences with sorting algorithms in the comments below and join the conversation!