1. Введение
В этом руководстве мы изучим сортировку выбором , увидим ее реализацию в Java и проанализируем ее производительность.
2. Обзор алгоритма
Сортировка выбором начинается с элемента в 1 ^-й позиции несортированного массива и просматривает последующие элементы, чтобы найти наименьший элемент . После нахождения наименьший элемент заменяется элементом в 1 ^-й позиции.
Затем алгоритм переходит к элементу во 2- ^й позиции и просматривает последующие элементы, чтобы найти индекс 2- ^го наименьшего элемента. После нахождения второй наименьший элемент заменяется элементом на 2- ^й позиции.
Этот процесс продолжается до тех пор, пока мы не достигнем n-1- ^го элемента массива, который помещает n-1- ^й наименьший элемент в n-1- ^ю позицию. Последний элемент автоматически становится на место, на n-1- ^й итерации, тем самым сортируя массив.
Мы находим самый большой элемент вместо самого маленького элемента, чтобы отсортировать массив в порядке убывания.
Давайте посмотрим на пример несортированного массива и отсортируем его в порядке возрастания, чтобы наглядно понять алгоритм.
2.1. Пример
Рассмотрим следующий несортированный массив:
int[] обр = { 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;
}
}
}
Конечно, чтобы обратить это, мы могли бы сделать что-то очень похожее:
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;
}
}
}
И с немного большим количеством локтя, мы могли бы объединить их с помощью Comparator s .
4. Обзор производительности
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 .