How to do Selection Sort in Java

Sorting algorithms are essential in computer science for organizing data efficiently. Selection Sort is a simple, comparison-based sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted portion of the list and moves it to the sorted portion. In this tutorial, we will walk through how Selection Sort works, provide a Java implementation, and compare its performance with Insertion Sort and Quick Sort.

What is Selection Sort?

Selection Sort divides the array into two parts: the sorted part on the left and the unsorted part on the right. The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion and swaps it with the leftmost unsorted element, moving the boundary of the sorted part one element to the right. This process continues until the entire array is sorted.

How Selection Sort Works:

1. Find the minimum element from the unsorted portion of the array.
2. Swap it with the first element of the unsorted portion.
3. Move the boundary between the sorted and unsorted sections to include the newly sorted element.
4. Repeat the process until the entire array is sorted.

Time Complexity:

• Best Case: O(n²)
• Worst Case: O(n²)
• Space Complexity: O(1) (in-place sorting)

Selection Sort Pseudocode

procedure SelectionSort(arr)
    n = length of arr
    
    for i = 0 to n-1 do
        minIndex = i  # Assume the first unsorted element is the minimum
        
        # Find the minimum element in the unsorted part
        for j = i+1 to n-1 do
            if arr[j] < arr[minIndex] then
                minIndex = j
        
        # Swap the found minimum element with the first unsorted element
        if minIndex != i then
            swap arr[minIndex] and arr[i]

end procedure

Java Implementation of Selection Sort

Here’s how you can implement selection sort in Java:

public class SelectionSort {

    // Method to perform Selection Sort
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // Traverse through the array
        for (int i = 0; i < n - 1; i++) {
            // Assume the first unsorted element is the minimum
            int minIndex = i;

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

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

    // Main method to test the Selection Sort algorithm
    public static void main(String[] args) {
        // Use a larger array for testing
        int[] arr = {64, 25, 12, 22, 11, 45, 33, 67, 89, 30, 72, 55, 5, 98, 35, 42, 8};

        // Print the original array
        System.out.println("Original Array: ");
        printArray(arr);

        // Perform Selection Sort
        selectionSort(arr);

        // Print the sorted array
        System.out.println("Sorted Array: ");
        printArray(arr);
    }

    // Helper method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(STR."\{i} ");
        }
        System.out.println();
    }
}

Output:

Original Array: 
64 25 12 22 11 45 33 67 89 30 72 55 5 98 35 42 8 
Sorted Array: 
5 8 11 12 22 25 30 33 35 42 45 55 64 67 72 89 98 

Step-by-Step Explanation of Selection Sort

Let’s break down how selection sort works on the array [64, 25, 12, 22, 11] step by step:

Step 1: Initial Array

[64, 25, 12, 22, 11] (Original array)

• Find the smallest element in the entire array: 11
• Swap 11 with the first element 64.

Array after Step 1:

[11, 25, 12, 22, 64]

Step 2: Second Pass

[11] | [25, 12, 22, 64] (First element is now part of the sorted section)

• Find the smallest element in the unsorted portion [25, 12, 22, 64]: 12
• Swap 12 with the first unsorted element 25.

Array after Step 2:

[11, 12, 25, 22, 64]

Step 3: Third Pass

[11, 12] | [25, 22, 64] (First two elements are now sorted)

• Find the smallest element in the unsorted portion [25, 22, 64]: 22
• Swap 22 with 25.

Array after Step 3:

[11, 12, 22, 25, 64]

Step 4: Fourth Pass

[11, 12, 22] | [25, 64] (First three elements are now sorted)

• Find the smallest element in the unsorted portion [25, 64]: 25
• No swap is needed since 25 is already in place.

Array after Step 4:

[11, 12, 22, 25, 64]

Step 5: Final Pass

[11, 12, 22, 25] | [64] (First four elements are now sorted)

• Only one element (64) remains in the unsorted portion, so the array is fully sorted.

Array after Step 5:

[11, 12, 22, 25, 64] (Fully sorted array)

Performance Test: Selection Sort vs Insertion Sort vs Quick Sort

In this section, we will compare the performance of three popular sorting algorithms: Selection Sort, Insertion Sort, and Quick Sort. Each algorithm has strengths and weaknesses depending on the size and structure of the data being sorted. By running performance tests on arrays of various sizes and different levels of order—random, sorted, reverse-sorted, and partially sorted—we can observe how each algorithm behaves under specific conditions.

Insertion Sort builds the sorted array one element at a time, placing each element in its correct position. It is efficient for small or partially sorted datasets, with a best-case time complexity of O(n), but degrades to O(n²) in the worst case.

Quick Sort is one of the most efficient general-purpose sorting algorithms, with an average-case time complexity of O(n log n). However, in the worst case (e.g., with poor pivot selection on a reverse-sorted array), its performance can degrade to O(n²).

import java.util.Arrays;
import java.util.Random;

public class SelectionSortBenchmark {

    // Method to perform Selection Sort
    public 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;
        }
    }

    // Method to perform Insertion Sort
    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 = j - 1;
            }

            arr[j + 1] = key;
        }
    }

    // Method to perform Quick Sort
    public 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);
        }
    }

    // Partition method for Quick Sort
    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++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);
        return i + 1;
    }

    // Swap method
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Helper method to generate a partially sorted array
    public static int[] generatePartiallySortedArray(int size) {
        Random random = new Random();
        int[] arr = random.ints(size, 0, size).toArray();
        Arrays.sort(arr, 0, size / 2);  // Sort the first half, leave the second half unsorted
        return arr;
    }

    // Method to benchmark the sorting algorithm's performance
    public static void benchmark(String name, Runnable sort) {
        long start = System.nanoTime();
        sort.run();
        long duration = System.nanoTime() - start;
        System.out.printf("%s: %.3f ms%n", name, duration / 1e6);
    }

    // Main method to test the performance of Selection Sort, Insertion Sort, and Quick Sort
    public static void main(String[] args) {
        int[] sizes = {1000, 5000, 10000};  // Test array sizes
        Random rand = new Random();

        for (int size : sizes) {
            System.out.println("Array size: " + size);

            // Generate a random array
            int[] randomArray = rand.ints(size, 0, size).toArray();

            // Performance test for random arrays
            benchmark("Selection Sort (random)", () -> {
                int[] arr = Arrays.copyOf(randomArray, randomArray.length);
                selectionSort(arr);
            });
            benchmark("Insertion Sort (random)", () -> {
                int[] arr = Arrays.copyOf(randomArray, randomArray.length);
                insertionSort(arr);
            });
            benchmark("Quick Sort (random)", () -> {
                int[] arr = Arrays.copyOf(randomArray, randomArray.length);
                quickSort(arr, 0, arr.length - 1);
            });

            // Generate a sorted array
            int[] sortedArray = Arrays.copyOf(randomArray, randomArray.length);
            Arrays.sort(sortedArray);

            // Performance test for sorted arrays
            benchmark("Selection Sort (sorted)", () -> selectionSort(Arrays.copyOf(sortedArray, sortedArray.length)));
            benchmark("Insertion Sort (sorted)", () -> insertionSort(Arrays.copyOf(sortedArray, sortedArray.length)));
            benchmark("Quick Sort (sorted)", () -> quickSort(Arrays.copyOf(sortedArray, sortedArray.length), 0, sortedArray.length - 1));

            // Generate a reverse-sorted array
            int[] reverseArray = Arrays.copyOf(sortedArray, sortedArray.length);
            for (int i = 0; i < reverseArray.length / 2; i++) {
                swap(reverseArray, i, reverseArray.length - i - 1);
            }

            // Performance test for reverse-sorted arrays
            benchmark("Selection Sort (reverse)", () -> selectionSort(Arrays.copyOf(reverseArray, reverseArray.length)));
            benchmark("Insertion Sort (reverse)", () -> insertionSort(Arrays.copyOf(reverseArray, reverseArray.length)));
            benchmark("Quick Sort (reverse)", () -> quickSort(Arrays.copyOf(reverseArray, reverseArray.length), 0, reverseArray.length - 1));

            // Generate a partially sorted array
            int[] partiallySortedArray = generatePartiallySortedArray(size);

            // Performance test for partially sorted arrays
            benchmark("Selection Sort (partially sorted)", () -> selectionSort(Arrays.copyOf(partiallySortedArray, partiallySortedArray.length)));
            benchmark("Insertion Sort (partially sorted)", () -> insertionSort(Arrays.copyOf(partiallySortedArray, partiallySortedArray.length)));
            benchmark("Quick Sort (partially sorted)", () -> quickSort(Arrays.copyOf(partiallySortedArray, partiallySortedArray.length), 0, partiallySortedArray.length - 1));

            System.out.println();
        }
    }
}

Results

Here are the results from the performance test. Your numbers may vary from those in the table.

Performance Comparison: Selection Sort vs Insertion Sort vs Quick Sort

Array Size & Configuration	Selection Sort (ms)	Insertion Sort (ms)	Quick Sort (ms)
1000 (Random)	4.656	3.091	0.555
1000 (Sorted)	1.046	0.023	2.681
1000 (Reverse)	0.577	7.939	3.850
1000 (Partially Sorted)	0.399	0.344	0.119
5000 (Random)	9.086	2.941	0.366
5000 (Sorted)	9.192	0.039	13.253
5000 (Reverse)	28.559	6.629	12.165
5000 (Partially Sorted)	8.355	1.667	0.321
10000 (Random)	30.747	9.187	0.744
10000 (Sorted)	29.358	0.049	40.866
10000 (Reverse)	123.714	21.179	39.049
10000 (Partially Sorted)	34.090	7.995	1.034

Note: Times are rounded to three decimal places for readability. Actual performance may vary due to system conditions.

Key Takeaways

• Quick Sort consistently outperforms the others on random arrays:
  • Across all array sizes, Quick Sort is the fastest algorithm on random arrays, showcasing its average-case time complexity of O(n log n). For example, on 10000 random elements, Quick Sort only took 0.744 ms, compared to 30.747 ms for Selection Sort and 9.187 ms for Insertion Sort.

• Insertion Sort excels on sorted arrays:
  • Insertion Sort performs well on sorted arrays, with almost negligible time for arrays of all sizes due to its best-case time complexity of O(n). For 10000 sorted elements, Insertion Sort completed in just 0.049 ms, whereas Quick Sort took 40.866 ms, and Selection Sort took 29.358 ms.

• Quick Sort underperforms on sorted arrays:
  • Quick Sort suffers on sorted arrays because the standard pivot selection (often the last element) leads to unbalanced partitions, turning its time complexity into O(n²). This is evident in the test where Quick Sort took 40.866 ms on 10000 sorted elements, much slower than Insertion Sort.

• Reverse-sorted arrays are a challenge for Selection Sort:
  • In Selection Sort, the algorithm always scans the entire unsorted part of the array to find the smallest element, regardless of the array’s order. In the case of a reverse-sorted array, Selection Sort will always pick the last element during each iteration, meaning it still performs a full O(n²) number of comparisons and swaps, even though the array is already structured in reverse. This inefficiency becomes particularly noticeable as the array size grows, as seen when Selection Sort took 123.714 ms to sort 10000 reverse-sorted elements, far slower than Quick Sort or Insertion Sort.

• Insertion Sort is inefficient with reverse-sorted arrays:
  • Insertion Sort performs poorly on reverse-sorted arrays, where it takes the maximum number of shifts for each element. On 1000 reverse-sorted elements, it took 7.939 ms, while Quick Sort took 3.850 ms, and Selection Sort completed in just 0.577 ms.

• Quick Sort handles all configurations well:
  • Quick Sort maintains its efficiency across all array configurations (random, sorted, reverse, and partially sorted), consistently outperforming Selection Sort and Insertion Sort, except on sorted arrays where Insertion Sort has the advantage.

Summary

• Quick Sort is the best general-purpose algorithm. It performs excellently on random and partially sorted arrays and remains competitive even for reverse-sorted and sorted arrays.
• Insertion Sort is ideal for small datasets or when data is already sorted or nearly sorted due to its minimal overhead.
• Selection Sort is simple and easy to implement, but its quadratic time complexity makes it inefficient for large datasets, particularly reverse-sorted arrays. It should be avoided for larger arrays, especially if the data is reverse-sorted.

Limitations of Selection Sort

Selection sort is easy to understand but has some limitations:

• Inefficient for large datasets: Its O(n²) time complexity makes it slow for sorting large arrays compared to algorithms like quicksort or mergesort.
• Not a stable sort: Selection sort does not preserve the relative order of equal elements. A different algorithm, like Bubble Sort or Merge Sort, might be preferable if stability is required.
• Too many comparisons: Even if the array is already sorted, Selection Sort will still perform O(n²) comparisons.

When to Use Selection Sort

There are a few specific scenarios where Selection Sort may be useful:

• Small Datasets:
  • Selection Sort performs reasonably well on small arrays where the overhead of more complex algorithms isn’t justified. Its simplicity and low memory requirements can make it a good choice for datasets of a few dozen elements.
• Memory-Constrained Environments:
  • Selection Sort has a constant O(1) space complexity, meaning it does not require additional memory beyond the input array. This makes it a viable option in memory-constrained environments where minimizing space usage is crucial.
• When Stability Isn’t a Concern:
  • Selection Sort is not a stable sorting algorithm, meaning it doesn’t preserve the relative order of elements with equal values. If stability is not a requirement for your use case (i.e., if the order of equal elements doesn’t matter), Selection Sort can be considered.
• Educational Purposes:
  • Due to its simplicity and clear logic, Selection Sort is often used in educational contexts to teach the basics of sorting algorithms and introduce students to concepts like comparison-based sorting, swapping, and time complexity analysis.

Conclusion

Selection sort is an intuitive and straightforward algorithm, best suited for small datasets or educational purposes. Despite its inefficiency for large datasets, it can be useful in situations where simplicity and clarity are more important than performance.

Congratulations on reading to the end of this tutorial!