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:

**Find the minimum element**from the unsorted portion of the array.**Swap**it with the first element of the unsorted portion.**Move the boundary**between the sorted and unsorted sections to include the newly sorted element.- 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.

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.

- Across all array sizes,

**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.

- In

**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.

- Selection Sort has a constant
**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.

- Due to its simplicity and clear logic,

## 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!

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.