Сортировка выбором в Java: пошаговый пример и полный код

Что такое сортировка выбором?

Сортировка выбором — это простой алгоритм на основе сравнений, который многократно находит минимальный элемент в неотсортированной части массива и меняет его местами с первым элементом этой части. Хотя она не быстрее других методов для больших данных, её простота делает идеальной для обучения и небольших массивов.

Как работает алгоритм

• Начинаем с начала массива.
• Находим наименьший элемент в неотсортированной части.
• Меняем его местами с элементом в текущей позиции.
• Сдвигаем границу между отсортированной и неотсортированной частями на один шаг вправо.
• Повторяем до полной сортировки массива.

Реализация на Java

Ниже приведена краткая программа, демонстрирующая сортировку выбором на целочисленном массиве. Код выводит массив до и после сортировки, а также промежуточные шаги для иллюстрации каждого прохода.

package com.guru99;

public class SelectionSortAlgo {
    public static void main(String[] args) {
        int[] myArray = {860, 8, 200, 9};
        System.out.println("------До сортировки выбором-----");
        printArray(myArray);
        selection(myArray); // Сортировка массива
        System.out.println("-----После сортировки выбором-----");
        printArray(myArray);
    }

    public static void selection(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            System.out.println("Проход сортировки № " + (i + 1));
            int index = i;
            for (int j = i + 1; j < array.length; j++) {
                System.out.println("Сравнение " + array[index] + " и " + array[j]);
                if (array[j] < array[index]) {
                    System.out.println(array[index] + " больше чем " + array[j]);
                    index = j;
                }
            }
            int smallerNumber = array[index];
            array[index] = array[i];
            array[i] = smallerNumber;
            System.out.println("Обмен элементов: новый массив после обмена");
            printArray(array);
        }
    }

    private static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

Пример вывода

------До сортировки выбором-----
860 8 200 9
Проход сортировки № 1
Сравнение 860 и 8
860 больше чем 8
Сравнение 8 и 200
Сравнение 8 и 9
Обмен элементов: новый массив после обмена
8 860 200 9
Проход сортировки № 2
Сравнение 860 и 200
860 больше чем 200
Сравнение 200 и 9
200 больше чем 9
Обмен элементов: новый массив после обмена
8 9 200 860
Проход сортировки № 3
Сравнение 200 и 860
Обмен элементов: новый массив после обмена
8 9 200 860
-----После сортировки выбором-----
8 9 200 860

Заметки о производительности

Сортировка выбором выполняет O(n²) сравнений независимо от входных данных и использует не более O(1) дополнительной памяти. Её детерминированное поведение делает её подходящей для сред с ограниченной памятью.