Мне нужно реализовать вариант алгоритма сортировки выбором. В этом варианте алгоритм должен удалить повторяющиеся числа.
Мне удалось сделать это, отсортировав вектор, а затем удалив повторяющиеся элементы в последующем цикле.
Я предполагаю, что есть другой более эффективный способ сделать эту работу, но я ничего не могу придумать. У вас есть предложения?
Различия в эффективности будут незначительными, поскольку вы намеренно используете алгоритм квадратичного времени для чего-то, что, как мы знаем, можно сделать быстрее. Разница между n2 и n2 + n довольно незначительна после определенного момента, так как по сути это n * (n + 1).
С этой оговоркой сортировка выбором относится к категории, которую мы называем «сортировка сравнением», поскольку решения о размещении принимаются на основе попарного сравнения. Сортировка без сравнения аналогична сортировке подсчетом: сколько объектов каждого объекта мы нашли? Нас не интересуют никакие другие элементы, кроме того, который мы сейчас рассматриваем.
Итак, поскольку вам все равно нужно сравнить величину каждой пары элементов, вы уже должны знать, есть ли у вас дубликат на тот момент.
Хотя, возможно, это не вся история. То, как вы управляете этими повторяющимися значениями, может легко занять больше времени, чем этот один цикл, если не обрабатывать его осторожно.
