«1. Введение

В этом руководстве мы изучим сортировку выбором, увидим ее реализацию в Java и проанализируем ее производительность.

2. Обзор алгоритма

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

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

Этот процесс продолжается до тех пор, пока мы не достигнем n-1-го элемента массива, который помещает n-1-й наименьший элемент в n-1-ю позицию. Последний элемент автоматически встает на место, на n-1-й итерации, тем самым сортируя массив.

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

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

2.1. Пример

Рассмотрим следующий несортированный массив:

int[] arr = {5, 4, 1, 6, 2}

Итерация 1

Принимая во внимание приведенную выше работу алгоритма, мы начинаем с элемент в 1-й позиции — 5 — и просматриваем все последующие элементы, чтобы найти наименьший элемент — 1. Затем мы меняем наименьший элемент с элементом в 1-й позиции.

Измененный массив теперь выглядит так:

{1, 4, 5, 6, 2}

Всего выполнено сравнений: 4

Итерация 2

Во второй итерации мы переходим к 2-й элемент — 4 — и сканируем последующие элементы, чтобы найти второй наименьший элемент — 2. Затем мы меняем местами второй наименьший элемент с элементом на 2-й позиции.

Измененный массив теперь выглядит так:

{1, 2, 5, 6, 4}

Всего выполнено сравнений: 3

Продолжая аналогичным образом, мы имеем следующие итерации:

Итерация 3 ~ ~~ {1, 2, 4, 6, 5}

Всего выполнено сравнений: 2

Итерация 4

{1, 2, 4, 5, 6}

Всего выполнено сравнений: 1 ~~ ~ 3. Реализация

Давайте реализуем сортировку выбором, используя пару циклов for:

Конечно, чтобы обратить ее вспять, мы могли бы сделать что-то очень похожее:

И немного больше усилий. , мы могли бы объединить их с помощью компараторов. 

public static void sortAscending(final int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minElementIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[minElementIndex] > arr[j]) {
                minElementIndex = j;
            }
        }

        if (minElementIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minElementIndex];
            arr[minElementIndex] = temp;
        }
    }
}

4. Обзор производительности 

public static void sortDescending(final int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int maxElementIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[maxElementIndex] < arr[j]) {
                maxElementIndex = j;
            }
        }

        if (maxElementIndex != i) {
            int temp = arr[i];
            arr[i] = arr[maxElementIndex];
            arr[maxElementIndex] = temp;
        }
    }
}

4.1. Время

В примере, который мы видели ранее, выбор наименьшего элемента требовал в общей сложности (n-1) сравнений с последующей перестановкой его на 1-ю позицию. Точно так же для выбора следующего наименьшего элемента требовалось общее (n-2) сравнений с последующей заменой на 2-й позиции и так далее.

Таким образом, начиная с индекса 0, мы выполняем n-1, n-2, n-3, n-4 …. 1 сравнения. Последний элемент автоматически встает на место благодаря предыдущим итерациям и перестановкам.

Математически сумма первых n-1 натуральных чисел скажет нам, сколько сравнений нам нужно, чтобы отсортировать массив размера n с помощью сортировки выбором.

Формула суммы n натуральных чисел: n(n+1)/2.

В нашем случае нам нужна сумма первых n-1 натуральных чисел. Поэтому мы заменим n на n-1 в приведенной выше формуле, чтобы получить:

(n-1)(n-1+1)/2 = (n-1)n/2 = (n^2-n) /2

Поскольку n^2 заметно растет с ростом n, мы рассматриваем более высокую степень n в качестве критерия производительности, делая этот алгоритм временной сложностью O(n^2).

4.2. Пробел

С точки зрения сложности вспомогательного пространства, сортировке выбором требуется одна дополнительная переменная для временного хранения значения для замены. Таким образом, пространственная сложность сортировки выбором равна O(1).

5. Заключение

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

«Другие методы сортировки, такие как сортировка вставками и сортировка Шелла, также имеют квадратичную временную сложность в худшем случае, но они работают лучше в лучшем и среднем случаях.

Ознакомьтесь с полным кодом сортировки выбором на GitHub.

«

Check out the complete code for Selection Sort over on GitHub.