Выбор Сортировка Java Программа с примером
Редакционная коллегия
⚡ Умное резюме
Сортировка по выбору Java многократно сканирует несортированную часть массива, находит наименьшее оставшееся значение и меняет его местами, завершая работу не более чем за n-1 обменов независимо от порядка входных данных.
Как работает сортировка выбором?
Сортировка выбором реализует простой алгоритм сортировки следующим образом:
- Алгоритм неоднократно ищет наименьший элемент.
- Замените текущий элемент элементом, имеющим наименьшее значение.
- При каждой итерации/проходе сортировки выбором элементы меняются местами.
Таким образом, каждый проход обрабатывает массив в виде двух областей: отсортированного блока, который увеличивается слева, и неотсортированного блока, который уменьшается справа. Алгоритм проходит по неотсортированному блоку, запоминает индекс наименьшего значения, которое он встречает, и заменяет это значение первой неотсортированной позицией.
Поскольку за один проход происходит только один обмен, массив из n элементов упорядочивается не более чем после n-1 обменов. Именно это свойство отличает данную процедуру от других процедур начального уровня. Java алгоритмы сортировки, которые перемещают данные гораздо чаще.
tracПриведенный ниже пример массива {860, 8, 200, 9} отображается точно так же, как это делает программа в следующем разделе во время выполнения.
| Проходить | Напечатанные сравнения | Наименьшее найденное значение | Массив после обмена |
|---|---|---|---|
| Начать | - | - | 860 8 200 9 |
| 1 | 860 и 8, 8 и 200, 8 и 9 | 8 | 8 860 200 9 |
| 2 | 860 и 200, 200 и 9 | 9 | 8 9 200 860 |
| 3 | 200 и 860 | 200 | 8 9 200 860 |
В этом есть две детали. tracНа них стоит обратить внимание. Во-первых, на третьем проходе по-прежнему сообщается об обмене, даже если порядок не меняется, потому что наименьшее оставшееся значение уже находится по текущему индексу, и программа обменивает элемент сам с собой. Во-вторых, количество сравнений уменьшается на единицу на каждом проходе (сначала три, затем два, затем одно), что объясняет закономерность, лежащую в основе показателей сложности, приведенных ниже на странице.
Java Программа для реализации сортировки выбором
Приведённый ниже класс называется SelectionSortAlgo и находится в пакете com.guru99. Метод main() объявляет пример массива, выводит его на экран, передаёт в метод selection() для сортировки и снова выводит на экран. Вспомогательный метод printArray() записывает все элементы в одну строку, что и создаёт читаемый пошаговый лог.
Внутри функции selection() внешний цикл отмечает границу между отсортированной и неотсортированной областями, переменная index хранит позицию наименьшего значения, обнаруженного до сих пор, а три присваивания в конце каждого прохода выполняют обмен.
package com.guru99; public class SelectionSortAlgo { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("------Before Selection Sort-----"); printArray(myArray); selection(myArray);//sorting array using selection sort System.out.println("-----After Selection Sort-----"); printArray(myArray); } public static void selection(int[] array) { for (int i = 0; i < array.length - 1; i++) { System.out.println("Sort Pass Number "+(i+1)); int index = i; for (int j = i + 1; j < array.length; j++) { System.out.println("Comparing "+ array[index] + " and " + array[j]); if (array[j] < array[index]){ System.out.println(array[index] + " is greater than " + array[j] ); index = j; } } int smallerNumber = array[index]; array[index] = array[i]; array[i] = smallerNumber; System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Выход:
Компиляция и запуск класса приводят к выводу в консоль следующего текста, причём каждый проход выводится одним блоком.
------Before Selection Sort----- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Comparing 8 and 200 Comparing 8 and 9 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 860 and 200 860 is greater than 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 9 200 860 -----After Selection Sort----- 8 9 200 860
Две проблемы могут сбить с толку новичков при первом запуске этого примера. Потому что в файле объявлено package com.guru99;, источник должен находиться в соответствующем месте. com/guru99 директории, в противном случае компилятор сообщит о несоответствии имени пакета или класса. В этом случае класс необходимо запускать по его полному имени. java com.guru99.SelectionSortAlgo, потому что простой java SelectionSortAlgo вызывает ошибку NoClassDefFoundError.
Еще одна распространенная ловушка — это ограничения цикла. Внешний цикл останавливается на определенной точке. array.length - 1 и внутренний цикл начинается в i + 1Изменение любой из границ приводит к дополнительному пустому проходу или к исключению ArrayIndexOutOfBoundsException.
Временная и пространственная сложность сортировки выбором
Внутренний цикл в программе всегда доходит до конца массива, поэтому алгоритм выполняет одинаковое количество сравнений независимо от типа данных. Для массива из n элементов это число равно n(n-1)/2, что для выборки из четырех элементов равно шести, и приведенный выше вывод действительно выводит ровно шесть строк сравнения.
| Кейсы | Сравнения | свопы | Сложность времени | Вспомогательное пространство |
|---|---|---|---|---|
| Лучший (массив уже отсортирован) | п (п-1) / 2 | п-1 | O (n²) | O (1) |
| Среднее значение (в случайном порядке) | п (п-1) / 2 | п-1 | O (n²) | O (1) |
| Худший (в обратном порядке) | п (п-1) / 2 | п-1 | O (n²) | O (1) |
Из этого однородного ряда цифр вытекают три следствия:
- Сортировка выбором не является адаптивной. Обработка отсортированных входных данных обходится ровно столько же, сколько и обработка обратных входных данных, поэтому нет быстрого выхода из системы. пузырьковая сортировка .
- Сильная сторона алгоритма — количество обменов. Производится максимум n-1 обменов, что намного меньше, чем квадратичное число ходов, которые могут совершить другие простые типы данных.
- Использование памяти постоянно. Требуются только счетчики циклов и две временные переменные index и smallerNumber, поэтому вспомогательное пространство имеет сложность O(1), а сортировка происходит на месте.
Квадратичный рост является практическим пределом. Удвоение размера массива примерно в четыре раза увеличивает объем сравниваемых данных, поэтому сортировка выбором больше подходит для обучения, небольших массивов и встроенного кода, чем для производственных наборов данных, где алгоритмы со сложностью O(n log n) являются оптимальным выбором.
Преимущества и недостатки сортировки выбором
Понимание того, в каких случаях алгоритм помогает, а в каких вредит, облегчает принятие решения о целесообразности его использования.
Преимущества
- Логика изложена кратко и понятно, поэтому это стандартное упражнение для первого этапа сортировки. сортировка вставок.
- Сортировка происходит на месте, поэтому второй массив не выделяется, и объем используемой памяти не увеличивается с ростом входных данных.
- Она выполняет максимум n-1 операций записи в массив, что важно для хранилищ, где запись происходит медленно или приводит к износу носителя.
- Время выполнения полностью предсказуемо, поскольку количество сравнений зависит только от длины массива.
Недостатки
- В каждом случае сложность алгоритма составляет O(n²), поэтому он не масштабируется для больших наборов данных.
- Он не может обнаружить уже отсортированный массив и поэтому никогда не завершает работу досрочно.
- Представленная выше классическая форма неустойчива, поэтому два равных значения могут оказаться в обратном порядке.
- Этот метод сравнивается чаще, чем сортировка вставками, на данных, близких к упорядоченному виду, где сортировка вставками приближается к линейному времени.
Короче говоря, сортировку выбором следует выбирать, когда массив невелик и каждая операция записи обходится дорого, и избегать её, когда набор данных велик или уже близок к отсортированному.
Сортировка выбором против Bubble-сортировка против сортировки вставками
Все три алгоритма используют квадратичную сортировку с сравнением на месте, однако они ведут себя по-разному при изменении формы входных данных.
| Критерий | Сортировка выбора | Bubblэ сорт | Вид вставки |
|---|---|---|---|
| лучшее время | O (n²) | О (п) | О (п) |
| Среднее и наихудшее время | O (n²) | O (n²) | O (n²) |
| В худшем случае — обмены или перераспределения. | n-1 обменов | n(n-1)/2 обменов | До n(n-1)/2 сдвигов |
| Стабильный | Нет | Да | Да |
| Адаптируется к отсортированным входным данным. | Нет | Да | Да |
| Вспомогательное пространство | O (1) | O (1) | O (1) |
| Типичное использование | Минимальное количество необходимых операций записи | Обучение и выявление отсортированных данных | Небольшие или почти отсортированные массивы |
В таблице приведен распространенный ответ на собеседовании. Сортировка выбором выигрывает по количеству обменов, пузырьковая сортировка выигрывает по распознаванию уже упорядоченных входных данных, а сортировка вставками обычно является самой быстрой из трех на практике, поскольку реальные данные часто частично отсортированы. Ни одна из них не может конкурировать с сортировкой слиянием или быстрой сортировкой, когда массив разрастается до нескольких десятков элементов.
