Sortare crescatoare de cost minim?!

[•vlad19alex]

Am dat de o problema in care mi se da un sir de numere si eu trebuie sa le ordonez crescator in asa fel in cat costul sa fie minim! COSTUL= suma numerelor pe care la interschimb.
ex se da sirul 3 2 1 costul minim e 4. se interschimba 3 cu 1 costul fiind suma acestora
ex2:  8 1 2 4 costul minim e 17 ..
Nu am nici cea mai vaga idee:|
 

[•repp4radu]

Au voie sa se repete numere?

In cazul in care nu au voie, ai putea sa consideri vectorul normalizat ca o permutare, sa identifici ciclii in aceasta permutare, iar pentru rezolvarea pozitiilor care nu corespund sa folosesti ca pivot cel mai mic element din ciclu.

[•vlad19alex]

nu este mentionat faptul ca nu pot sa se repete dar dupa cerinta s-ar putea deduce ca nu pot sa se repete numerele..

[•vlad19alex]

am inteles ideea ta la ceva asemanator ma gandeam si eu acu sa vad cum reusesc sa o implementez Respect!

[•repp4radu]

In cazul in care se repeta, va trebui sa fi atent sa nu interschimbi elemente cu valori egale, dar cred ca ideea de baza va ramane aceeasi.

Bafta!  

[•vlad19alex]

Cred ca problema este in momentul in care pivotul(elementul minim ajunge pe pozitia lui finala) nu va mai functiona
ex 8 4 5 3 2 7 si costul minim stiu ca trebuie sa fie 34 
interschimbarile vor fi asa:
8 4 5 3 7 2(cost 9)
2 4 5 3 7 8(cost 10)
2 3 5 4 7 8 (cost 7)
2 3 4 5 7 8 (cost 9)
costul fiind 35

[•repp4radu]

Eu nu am reusit sa ajung la costul 34, dar oricum este posibil sa apara cazul in care este necesar sa strici un ciclu pentru a rezolva un altul.

Ce am scris mai sus a fost o idee, data fara o analiza minutioasa a cazurilor ce pot aparea

[•vlad19alex]

ma poate ajuta careva sa fac o sortare cu un pivot care va fi elementul minim din sir si va ajunge pe pozitia lui finala dupa ce s-au epuizat toate interschimbarile
ex
de la 2 4 1 3 sa ajung la 1 2 3 4 prin interschimbarile
2 4 3 1->2 1 3 4 ->1 2 3 4
iar daca pivotul ajunge in pozitia lui finala si inca nu este sortat sirul se ia ca pivot urmator elemen ca valoare minima

[•vlad19alex]

cred ca se face cu programare dinamica nu stiu 
as mai aveea o idee dar care tot asa nu cred ca e buna sa pun toate costurile intr-o matrice .. si sa incerc sa ordonez asa dar nici asta nu ma condus la nici un rezultat pana acuma