Selection Sort

Selection Sort Photo
Author: Tatyana Milkina

Another simple and intuitive way to sort array elements is Selection Sort (Selection Sort). This algorithm is often introduced at the early stages of learning sorting methods because it is easy to understand and implement in most programming languages, including Java.

Idea Behind the Selection Sort Algorithm

The essence of Selection Sort can be described as follows:

  1. Find the minimum element in the unsorted part of the array.

  2. Swap it with the first element of the unsorted part.

  3. Repeat the process for the remaining unsorted portion of the array.

Thus, with each pass of the inner loop, the minimum values "bubble up" to the beginning of the array.

Visualization example:

Selection Sort illustration

Java Implementation of Selection Sort

Let’s take a look at the implementation. The outer for loop controls the number of passes, while the inner one searches for the smallest value in the current pass. Note that the search starts after the already sorted portion:

public class SelectionSorter {
    public static void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {    // i - current step
            int pos = i;
            int min = array[i];
            // search for the minimum element
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < min) {
                    pos = j;    // pos - index of the smallest element
                    min = array[j];
                }
            }
            array[pos] = array[i];
            array[i] = min;    // swap smallest with array[i]
        }
    }
}

Example Usage of Selection Sort

Below is an example with several test arrays, which clearly demonstrates how selection sort works with different inputs.

import java.util.Arrays;

public class SelectionSorterExample {
    public static void main(String[] args) {
        int[][] data = {
                {},
                {1},
                {0, 3, 2, 1},
                {4, 3, 2, 1, 0},
                {6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7},
        };
        for (int[] arr : data) {
            System.out.print(Arrays.toString(arr) + " => ");
            SelectionSorter.sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }
}

Advantages and Disadvantages of Selection Sort

Pros Cons
Simple to implement Low performance (O(n²))
Does not require extra memory Slow for large datasets

Conclusion

Selection Sort in Java is a fundamental yet important algorithm every beginner should understand. Despite its simplicity and low efficiency, it provides a good introduction to loops and element swapping in arrays.

Курс 'Java для начинающих' на Udemy Курс 'Java для начинающих' на Udemy
Read also:
Comments