Sorting Algorithms in Java: Step-by-Step

A sorting algorithm rearranges a list of items in ascending or descending order using a comparison operator to determine which element is smaller or larger.

Input: 5 3 8 4 2 7

Output: 2 3 4 5 7 8

Sorting algorithms fall into two main categories based on their approach: Brute Force and Divide and Conquer. The 5 most common sorting algorithms in Java are Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, and Merge Sort.

Brute Force Approach

The Brute Force technique iterates through all elements and compares each one to its adjacent neighbor. When two adjacent elements are in the wrong order, the algorithm swaps them. It makes no attempt to reduce the number of comparisons based on earlier passes.

Examples: Bubble Sort, Insertion Sort, Selection Sort.

Divide and Conquer Approach

This approach splits the full problem into smaller sub-problems, solves each sub-problem independently, then merges the results. The time complexity is lower than Brute Force, but the implementation is more complex and the space complexity is higher because the algorithm allocates additional memory for sub-arrays rather than sorting in place.

Examples: Quick Sort, Merge Sort.

Bubble Sort

Bubble Sort iterates through each element and swaps it with its adjacent neighbor when the two are out of order. It uses the Brute Force approach.

Each pass through the array places one more element in its final sorted position. Pass 1 places the largest element at index n-1; Pass 2 places the second-largest at index n-2; and so on. The algorithm requires n passes total, regardless of whether the array is already sorted (unless you add an early-exit optimization).

The example below uses input 5 3 8 4 2 7.

Pass 1

Pass 2

The algorithm continues for 5 passes total.

Bubble Sort: Time Complexity

Best Case

Provide an already-sorted list: 1 2 3 4 5

The algorithm runs N x N iterations with zero swap operations because no elements are out of order.

Time Complexity: O(N^2)

Average and Worst Case

Provide a partially sorted list (average) or a fully reversed list (worst). The algorithm runs N x N iterations and performs up to N swap operations.

Time Complexity: O(N^2)

Bubble Sort: Java Implementation

import java.io.*;

class BubbleSortSample {

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

    public static void main(String[] args) {
        int[] arr = { 5, 3, 4, 8, 7, 6, 9 };
        bubbleSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output: 3 4 5 6 7 8 9

Bubble Sort: Step-by-Step Setup

Follow these steps to run Bubble Sort on your machine.

Step 1. Download and install the JDK from oracle.com/java/technologies/downloads/.

Step 2. Create a new file with the .java extension. Name the file BubbleSortSample.java.

Step 3. Declare the class with the same name as the file:

class BubbleSortSample {
}

Step 4. Add a static sorting method that accepts an integer array:

public static void bubbleSort(int[] arr) {
}

Step 5. Inside the method, declare a temp variable for swapping and read the array length into n:

int temp;
int n = arr.length;

Step 6. Add the outer loop (one iteration per pass) and the inner loop (one comparison per pair). The inner loop runs one fewer comparison each pass because the last i elements are already in place:

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

Step 7. Inside the inner loop, compare the current element to its right neighbor. When they are out of order, swap them using the temp variable:

if (arr[j] > arr[j + 1]) {
    temp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = temp;
}

Step 8. In main, declare a test array, call bubbleSort, then print the sorted result:

int[] arr = { 5, 3, 4, 8, 7, 6, 9 };
bubbleSort(arr);
for (int i = 0; i < arr.length; i++) {
    System.out.print(arr[i] + " ");
}

The program prints the array elements in ascending order.

Quick Sort

Quick Sort uses the Divide and Conquer approach. It selects one element as the pivot, partitions the array into two sub-arrays (elements smaller than the pivot go left; elements larger go right), then recursively sorts each sub-array until every sub-array contains one element.

Walk-through with input 3 4 2 8 5 7:

• Pass 1: Select 8 as the pivot. Left sub-array: 3 4 2. Right sub-array: 8 (nothing larger).
• Pass 2 (left): Select 2 as the pivot. Left: nothing smaller. Right: 3 4.
• Pass 2 (right): Select 8 as the pivot. Left: 5 7. Right: 8.
• Pass 3: Split 3 4 with pivot 4: left 3, right 4. Split 5 7 with pivot 7: left 5, right 7.
• Merge: All sub-arrays now have length 1. Recombine in sorted order.

No further comparisons are needed during the merge because the sub-arrays are already ordered.

Need Java Assignment Help for a sorting or algorithms assignment? GeeksProgramming connects you with a Java developer who tests the code before delivery.

Quick Sort: Time Complexity

Best Case

The pivot consistently splits the array into two equal halves. Each level of recursion processes N elements across log(N) levels.

Time Complexity: O(N log N)

Worst Case

The pivot is always the smallest or largest element, producing one sub-array of size N-1 and one empty sub-array every pass. This degrades to N passes each doing N work.

Time Complexity: O(N^2)

Quick Sort: Java Implementation

import java.io.*;

class QuickSortAlgorithm {

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

    public static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int pivot = partition(arr, start, end);
            quickSort(arr, start, pivot - 1);
            quickSort(arr, pivot + 1, end);
        }
    }

    public static void main(String[] args) {
        int[] arr = { 5, 3, 4, 8, 7, 6, 9 };
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output: 3 4 5 6 7 8 9

Quick Sort: Step-by-Step Setup

Step 1. Download and install the JDK from oracle.com/java/technologies/downloads/.

Step 2. Create QuickSortAlgorithm.java.

Step 3. Declare the class:

class QuickSortAlgorithm {
}

Step 4. Add a partition method that accepts the array, a start index, and an end index:

public static int partition(int[] arr, int start, int end) {
}

Step 5. Inside partition, set the pivot to the last element and initialize the left-boundary pointer i:

int temp;
int pivot = arr[end];
int i = start - 1;

Step 6. Loop from start to end - 1. When the current element is smaller than the pivot, advance i and swap the element at j with the element at i:

for (int j = start; j < end; j++) {
    if (arr[j] < pivot) {
        i++;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Step 7. After the loop, place the pivot into its final sorted position at index i + 1:

temp = arr[i + 1];
arr[i + 1] = arr[end];
arr[end] = temp;
return (i + 1);

Step 8. Add the quickSort method. When start < end, call partition to get the pivot index, then recurse on the left sub-array and the right sub-array:

public static void quickSort(int[] arr, int start, int end) {
    if (start < end) {
        int pivot = partition(arr, start, end);
        quickSort(arr, start, pivot - 1);
        quickSort(arr, pivot + 1, end);
    }
}

Step 9. In main, create a test array and call quickSort with 0 as the start index and arr.length - 1 as the end index:

int[] arr = { 5, 3, 4, 8, 7, 6, 9 };
quickSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
    System.out.print(arr[i] + " ");
}

The program prints each element in ascending order.

Related Java Reading

• Traversal Algorithms in Java and Python with Code covers Depth First Search and Breadth First Search with working Java examples.
• Binary Search Trees in Java: Complete Guide covers BST insertion, deletion, traversal, and balancing with AVL and Red-Black Trees.

Sorting and data-structure assignments in Java regularly show up in CS courses at every level. If you are stuck on an implementation or running out of time, the Java Assignment Help page explains how GeeksProgramming works and what a submission looks like.