Вступление

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

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

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

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

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

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

Он называется алгоритмом «грубой силы», потому что он использует самый простой и самый неэффективный способ вычисления решения. Однако он компенсирует это простой реализацией.

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

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

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

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

Отсортированный массив Несортированный массив Минимальный элемент несортированного массива [] [16, 5, 30, 6, 2, 7] 2 [2] [16, 5, 20, 6, 7] 5 [2, 5] [16, 20, 6, 7] 6 [2, 5, 6] [16, 7, 20] 7 [2, 5, 6, 7] [16, 20] 16 [2, 5, 6, 7, 16] [20] 20 [2, 5, 6, 7, 16, 20] []

Выполнение

Метод selectionSort() принимает только один аргумент - массив, который нужно отсортировать. Мы будем перебирать несортированный массив, который будет находиться между индексами 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 ^2^ ) . Это делает сортировку выбора намного медленнее, чем многие другие алгоритмы сортировки сравнения, такие как сортировка слиянием или сортировка вставкой, которые имеют наихудшую временную сложность (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++) 

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

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

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

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

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

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

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

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

 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,024 Второй прогон 0,020 Третий пробег 0,022 Четвертый забег 0,020 Пятый заезд 0,025 Шестой пробег 0,022 Седьмой забег 0,021 Восьмерка 0,031 Девятый забег 0,022 Десятый забег 0,029

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

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

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

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

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

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

Заключение

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

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