Продолжаем знакомство с элементарными сортировками. На этот раз разберем алгоритм сортировки методом “Выбора”. Он немного сложнее сортировки пузырьком, но только для понимания и занимает 9 срок кода. Да, метрика количество строк кода вообще не гуд, но я все же упоминаю ее для подтверждения элементарности алгоритма. Итак, как работает сортировка методом “Выбора”? Обратим внимание на название алгоритма. Вообще наименование методов, алгоритмов, переменных отдельный вид искусства. Сортировка “Выбором”. Похоже, что алгоритм что-то выбирает, скажите вы. Да, отвечу я. Мы выбираем минимальный/максимальный элемент в массиве.
Далее я буду писать “минимальный”, но вы помните что можете задать направление сортировки сами.
Описание алгоритма сортировки методом “Выбора”.
“Выбираем” минимальным первый элемент массива, и последовательно сравниваем его с другими. Если находим элемент, меньше нашего минимума, то “выбираем” его минимальным. Далее продолжаем сравнивать новый минимум с остальными элементами массива, если находим меньший – “выбираем” его как минимум и так далее. Когда мы дойдем до конца массива, минимальный элемент гарантировано будет “выбран” корректно. Меняем местами первый и минимальный элемент массива. Теперь мы видим, что в начале массива самый минимальный элемент. Эта часть теперь отсортирована и мы двигаемся дальше. Теперь “выбираем” минимальным элемент второй элемент, и сравниваем его по уже известному алгоритму. После того, меняем местами второй элемент с минимальным и “выбираем” минимальным третий и так далее. В итоге мы получим отсортированный массив.
Сложность алгоритма сортировки методом “Выбора”.
Алгоритм сортировки имеет такое же количество сравнений, что и метод сортировки пузырьком (N^2/2), однако количество перестановок гораздо ниже. В определении О-синтаксиса сложность алгоритма будет O(N^2).
Код сортировки на языке Java выглядит следующим образом:
|
1 2 3 4 5 6 7 8 9 10 11 |
int temp, in, out, min; // вводим переменные для циклов и замены for (out = 0; out < array.length-1; out++) { // начинаем внешний цикл min = out; // считаем что минимум в позиции out for (in = out + 1; in < array.length; in++) { // внутрений цикл для сравнения элементов if (array[in] < array[min]) // если текущий меньше минимума min = in; // меняем индекс минимального } temp = array[out]; // после нахождения индекса минимального array[out] = array[min]; // кладем минимум в позицию out array[min] = temp; } |
Инвариантом в алгоритме сортировки методом “Выбора” является факт того, что элементы, с индексом меньше out будут отсортированы.
Для сортировки в обратную сторону нужно заменить условие в if с “<” на “>”. Так же лучше переименовать min на max. Помните, наименование очень важно!
2 comments On Полулегендарная сортировка методом “Выбора”
>> сложность алгоритма будет O(N)
Все-таки, сложность будет O(n^2)
Благодарю, Andrey! Вы абсолютно правы!