Сортировка выбора в Java

Автор оригинала: Kristina Popovic.

Вступление

Сортировка данных-частая проблема в информатике. Учитывая набор элементов, цель состоит в том, чтобы переставить их в определенном порядке. Распространенными примерами являются сортировка массива в алфавитном порядке или от наименьшего к наибольшему.

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

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

Сортировка выбора

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

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

Это называется алгоритмом “грубой силы”, потому что он использует самый простой и неэффективный способ вычисления решения. Тем не менее, он компенсирует это своей простой реализацией.

Алгоритм делит массив на два подмассива:

• Сортированный подмассив
• Несортированный подмассив

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

Пример массива, который мы хотим отсортировать в порядке возрастания:

Реализация

Метод selection Sort() принимает только один аргумент-массив, который необходимо отсортировать. Мы пройдемся по несортированному массиву, который будет находиться между индексами i и j , найдем его минимум и поместим в отсортированный массив путем замены:

public static void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // min is the index of the smallest element with an index greater or equal to i
        int min = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        // Swapping i-th and min-th elements
        int swap = nums[i];
        nums[i] = nums[min];
        nums[min] = swap;
    }
}

Давайте протестируем код:

int[] array = new int[]{16, 5, 30, 6, 7, 2};
selectionSort(array);
System.out.println(Arrays.toString(array));

Это будет распечатано:

[2, 5, 6, 7, 16, 30]

Выбор Сложность Сортировки По времени

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

Производительность зависит как от аппаратного, так и от программного обеспечения, но одна и та же программа может выполняться на множестве различных типов оборудования. Обозначение Big-O упрощает приблизительное время, необходимое для выполнения программы, независимо от программного обеспечения.

Средняя и наихудшая временная сложность сортировки выбора составляет O(n ² ) . Это делает сортировку выбора намного медленнее, чем многие другие алгоритмы сортировки сравнения, такие как Сортировка слиянием или Сортировка вставкой , которые имеют наихудшую временную сложность (O(nlogn)) . Интересно, что O(nlogn) является лучшим, что может быть достигнуто с помощью любого алгоритма сортировки сравнения.

Анализ Временной Сложности

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

for (int i = 0; i < nums.length; i++) {

Все во внутреннем блоке цикла будет выполнено n раз, где n – длина данного массива:

int min = i;

min будет инициализирован в i ровно n раз. Теперь начинается самое сложное:

for (int j = i + 1; j < nums.length; j++)

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

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

Когда i равно 0, j перейдет от 1 к n , что означает, что каждая инструкция во внутреннем блоке будет выполняться n раз. Когда i увеличивается до 1, j останется между 2 и n , что означает, что внутренний блок будет выполняться n-2 раз. Подводя итог этому:

(n - 1) + (n - 2) + ... + 1

Сумма последовательности натуральных чисел вычисляется с помощью так называемого трюка Гаусса, и это приводит к (n ² – n)/2 . Упрощение этого приводит к O(n ² ) временная сложность.

Проще говоря, при вычислении сложности алгоритма O(f(n)) нам нужно искать наивысшую мощность n в функции f(n) и изолировать ее. Это связано с тем, что любая часть уравнения, имеющая меньшую мощность, не повлияет на результат каким-либо существенным образом.

Например, у нас есть функция f(x) ² + 13x+23

O(f(x)) будет наивысшей степенью x в уравнении, которая в данном случае равна x ² .

Вот как это выполняется после сортировки массива, содержащего 10 000 целых чисел в случайном порядке:

public static void main(String[] args) {
    int[] array = new int[10000];
    for (int i = 0; i < array.length; i++) {
          array[i] = i;
    }

    // Shuffle array
    Collections.shuffle(Arrays.asList(array));

    // Print shuffled collection
    System.out.println(Arrays.toString(array));
  
    long startTime = System.nanoTime();
    selectionSort(array);
    long endTime = System.nanoTime();
		
    // Print sorted collection
    System.out.println(Arrays.toString(array));

    // Print runtime in seconds
    System.out.println("Selection Sort runtime: " + (endTime - startTime)/1000000000);
}

Запустив его 10 раз, этот код дал следующие результаты:

Среднее время выполнения составляло 0.0236 секунды, однако, это также будет в значительной степени зависеть от вашей машины.

Сложность Пространства Сортировки выбора

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

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

Этот алгоритм имеет приличную производительность, если в коллекции не так много элементов. Если массив содержит ~10 элементов, разница в производительности между различными алгоритмами сортировки не должна быть такой заметной, и сортировка по выбору может даже превзойти другие алгоритмы “разделяй и властвуй”.

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

Вывод

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

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