Найти минимальное количество свопов для сортировки массива
Учитывая массив с различными элементами, какое минимальное количество подкачки необходимо для его сортировки?
Например, массив [4, 2, 1, 3] необходимо как минимум 2 обмена (например, поменять местами 4 и 1, затем 4 и 3).
Это мой подход:
B = sort(copy(A))
for i = 0 ... len(A) - 1
if A[i] != B[i]
find j such that A[j] == B[i]
swap(A[i], A[j])
Мой подход правильный? Есть ли другой способ решить это?
Решение
Это зависит от того, пытаетесь ли вы найти минимальное количество перестановок или действительно пытаетесь отсортировать массив.
Если вы пытаетесь отсортировать массив, минимальное количество перестановок не поможет вам быстрее его отсортировать. Поиск лучшего алгоритма сортировки поможет вам сортировать быстрее. Как правило, это означает, что нужно найти объект со сложностью O (n log (n)) (если только массив не является маленьким или объем памяти не является основным ограничением). Для помощи в решении этой проблемы Google — ваш друг.
Если вы просто пытаетесь найти минимальное количество необходимых свопов, не сортируя его по-настоящему, вы смотрите на некоторую модификацию сортировки выбора. Для этого нужно найти самое низкое значение, поменять местами с первым индексом, найти второе по младшему, поменять местами со вторым индексом и т. Д.
Но, как я уже сказал, поиск минимального количества свопов не оптимизирует сортировку. Например, сортировка выбора может иметь меньше свопов, чем быстрая сортировка, но для сортировки выбора требуется больше времени, чтобы определить, какие индексы следует заменить. Временная сложность сортировки выбора O (n ^ 2).
Разница между O (n ^ 2) и O (n log (n)), между прочим, не так тривиальна, как кажется. Если число составляет около 1 000 000, это может быть разница между 20 000 000 и 1 000 000 000 000.
Другие решения
Других решений пока нет …