minimalna liczba zamian podczas sortowania

Mamy dany ciąg liczb, który mamy posortować rosnąco.
Sortujemy, pojedynczo zamieniając 2 dowolne elementy miejscami.
Liczby są parami różne .
Mamy wypisać minimalna liczbę zmian.
Ma ktoś jakiś pomysł ?
1<=n<=10^6
n - długość ciągu

zamieniając 2 dowolne elementy miejscami

To jest sortowanie "stochastyczne" :-)

coś wiecej ?
:)

to sortowanie nie ma nazwy.
Zadanie mówi "wypisać minimalna liczbę zmian". Czyli masz założyć, że to stochastyczne sortowanie, trafia na najbardziej optymistyczny ciąg par do zamiany.
Czyli ile najmniej zamian trzeba wykonać by tablicę posortować. Nie ma takiego ogólnego algorytmu sortowania, który by to zapewniał, więc twoje pytanie "Jakie to sortowaie" nie ma odpowiedzi.

Jeśli pytanie brzmi "jaka jest minimalna liczba zmian" to odpowiedź też jest prosta: 0
Przy posortowanym wejściu.

Ciąg nie jest posortowany

Jak kogoś to interesuje problem został rozwiązany :) .

wczytuje( n )
wczytuje( tab )
kopiuje tab do tablicy pom
sort(pom,pom+n)
for i=0 do n-1 {
     while( tab[i]!=pom[i] ){
           wyszukuje binarnie tab[i] w tablicy pom (index)
           swap( tab[i] , tab[index])
           counts++
     }
}
wypisz( counts )

Czas działanie : O(n lg n)

Niby O(nlogn) ale przy założeniu że masz już posortowana tablicę, co nie bardzo ma sens.

Kod do zadania :

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int tab[1000005];
int a[1000005];
int counts=0;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",&tab[i]);
        a[i]=tab[i];
    }
    sort(tab,tab+n);
    int wynik=0;
    for(int i=0;i<n;++i){
        while(a[i]!=tab[i]){
            int poczatek=0,koniec=n-1,srodek;
            int index=0;
            while(poczatek<=koniec){
                srodek=(poczatek+koniec)/2;
                if(tab[srodek]==a[i]){
                    index=srodek;
                    break;
                }
                else if(tab[srodek]>a[i]){
                    koniec=srodek-1;
                }
                else poczatek=srodek+1;
            }
            swap(a[i],a[index]);
            counts++;
        }
    }
    printf("%d",counts);
    return 0;
}