Для каждого элемента массива вычислим номер позиции, где он должен стоять в отсортированном массиве.
Далее составим ориентированный граф с вершинами 1..N, где из каждой вершины будет выходить ровно одно ребро:
Если k-й элемент массива должен стоять на j-м месте в отсортированном массиве - то из вершины k идет ребро в вершину j. (Если k-й елемент массива стоит на своем месте, то будет петля - из k в k).
Далее разбиваем полученный граф на компоненты связности. Пусть N1, N2, ...Ns - количество вершин в полученных компонентах связности.
Тогда ответ задачи: (N1-1)+(N2-1)+...+(Ns-1)
(Каждая компонента связности представляет собой "кольцо" из Ni елементов, чтоб их отсортировать надо Ni-1 перестановок.
Елементы, что стоят на своих местах дают каждый отдельную компонету связности с одним элементом.
Те, что не на своих местах - в лучшем случае "перепутаны парами" - тогда каждая компонента связности будет состоять из 2х вершин - N/2 перестановок. В худшем - все выстроятся в одно кольцо: N-1 перестановок).
Ну, как мог - объяснил.
-~{}~ 13.07.07 03:50:
Занятся нечем, нарисую пример для наглядности:
Исходный массив: ( 3, 5, 6, 4, 2, 1).
1-й элемент должен стоять на 3-м месте - из "1" ребро в "3". 3-й элемент - на 6-м месте - из "3" ребро в "6". 6-й элемент должен стоять на 1-м месте - из "6" ребро в "1". Вот 1-я компонента связности:
1 => 3 => 6 => 1
2-я:
2 => 5 => 2
3-я:
4 => 4
Перестановки: 1-й элемент меняем с 3-м, 3-й с шестым. 2-й с 5-м.
Из примера становится понятно, что весь хитроумный алгоритм с компонентами связности на самом деле - простая перестановка влоб: берем 1-й элемент, ставим на свое место. Если элемент, что стоял на его месте при этом попал на свое - хорошо, берем следующий, если нет - его ставим на свое место и т.д. И нет способа сделать это с меньшим числом перестановок.
