Сортировка методом выбора в Java

Еще один простой и наглядный способ упорядочить элементы массива — это сортировка методом выбора (Selection Sort). Этот алгоритм часто изучают на начальных этапах изучения алгоритмов, поскольку он интуитивно понятен и легко реализуется на любом языке программирования, включая Java.

Идея алгоритма Selection Sort

Суть метода выбора заключается в следующем:

1. Находим минимальный элемент в неотсортированной части массива.

2. Меняем его местами с первым элементом этой части.

3. Повторяем процесс для оставшегося массива (без уже отсортированных элементов).

Таким образом, с каждым проходом внутреннего цикла минимальные значения "всплывают" в начало массива.

Пример визуализации:

Реализация сортировки выбором в Java

Рассмотрим реализацию алгоритма. Внешний цикл for отвечает за номер прохода, а внутренний - за поиск минимального значения в текущем проходе. Обратите внимание, что во внутреннем цикле начинаем искать минимальный элемент не с самого начала, а пропускаем уже найденные на предыдущем шаге элементы:

public class SelectionSorter {
    public static void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {    // i - номер текущего шага
            int pos = i;
            int min = array[i];
            // цикл выбора наименьшего элемента
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < min) {
                    pos = j;    // pos - индекс наименьшего элемента
                    min = array[j];
                }
            }
            array[pos] = array[i];
            array[i] = min;    // меняем местами наименьший с array[i]
        }
    }
}

Пример использования сортировки

Ниже представлен пример с несколькими тестовыми массивами. Это позволяет наглядно увидеть, как работает метод выбора на различных входных данных.

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

Преимущества и недостатки Selection Sort

Заключение

Сортировка выбором в Java — это базовый, но важный алгоритм, который стоит изучить каждому начинающему разработчику. Несмотря на свою простоту и сравнительно низкую производительность, он дает хорошее представление о том, как работают внутренние циклы и обмен значениями в массивах.