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

Сортировка выбором (selection sort) в Java — это простой алгоритм упорядочивания массива, при котором на каждом шаге в неотсортированной части находится минимальный элемент и ставится на своё место в начале. Алгоритм работает на месте (in-place), не требует дополнительной памяти и имеет временную сложность O(n²). Его часто изучают одним из первых, потому что он интуитивно понятен и легко реализуется на любом языке.

Идея алгоритма 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));
        }
    }
}

Сложность и устойчивость

Сортировка выбором всегда делает одно и то же количество сравнений независимо от входных данных: внешний цикл выполняется n раз, внутренний — в среднем n/2 раз. Поэтому её временная сложность одинакова в лучшем, среднем и худшем случаях.

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

Этот алгоритм не самый эффективный по скорости, особенно для больших объёмов данных. Однако его полезно знать, чтобы понять принципы работы сортировок на месте и приёма многократного выбора минимума. По сравнению с пузырьковой сортировкой метод выбора делает столько же сравнений, но заметно меньше обменов.

На чём чаще всего ошибаются

• Начинают внутренний цикл с нуля. Поиск минимума нужно вести с индекса i + 1, а не с начала массива — иначе теряется смысл прохода и растёт число лишних сравнений.
• Забывают сохранить индекс минимума. Обмен делается по позиции pos, а не с первым попавшимся меньшим элементом; иначе массив не отсортируется.
• Ждут ускорения на почти отсортированных данных. В отличие от сортировки вставками, selection sort всегда выполняет O(n²) сравнений — ранний выход невозможен.
• Путают с пузырьковой сортировкой. Обе имеют сложность O(n²), но пузырьковая обменивает соседние элементы на каждом сравнении, а выбором — лишь один раз за проход.

Заключение

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