Условие задачи
Массив сортируется методом выбора по возрастанию. Сколько раз меняет свое место первый по порядку элемент?
Входные данные
Первая строка содержит количество элементов в массиве $n$ $\left(1\leqslant n\leqslant1000\right)$. Во второй строке задан сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10^9$.
Выходные данные
Вывести количество перемещений первого элемента.
Тесты
| № | Ввод | Вывод |
| 1 | 3
1 3 2 |
0 |
| 2 | 2
2 1 |
1 |
| 3 | 4
4 1 5 3 |
3 |
| 4 | 6
23 5 56 2 87 3 |
1 |
| 5 | 7 15 1 6 3 9 8 13 |
4 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { java.util.Scanner in = new java.util.Scanner(System.in); int n = in.nextInt(); int []x = new int [n]; int counter = 0; // количество перемещений for (int i = 0; i < n; i++){ x[i] = in.nextInt(); } int first = x[0]; // первый по порядку элемент for (int i = 0; i < n - 1; i++) { int min = i; // индекс минимального элемента for (int j = i + 1; j < n; j++) { if (x[j] < x[min]) min = j; } if((x[i] == first || x[min] == first) && x[i] != x[min]) counter ++; int t = x[i]; x[i] = x[min]; x[min] = t; } System.out.print(counter); } } |
Решение
Применяем метод выбора по возрастанию. Для этого мы ищем наименьший элемент в массиве и перемещаем его на первое место. Затем ищем второй наименьший элемент и перемещаем его уже на второе место после первого наименьшего элемента. Этот процесс продолжается до тех пор, пока в массиве не закончатся неотсортированные элементы. Для того, чтобы найти количество перемещений первого элемента, мы проверяем совпадает ли значение первого элемента со значениями перемещаемых элементов. Также смотрим, чтобы значения этих элементов не были равны между собой, так как в этом случае сам элемент никуда не сдвигается.
Подробное изложение алгоритма сортировки можно найти в этой статье .