Ako ti kvadratno vreme nije preskupo, mogu ti dati algoritam za nalazenje najmanjeg moguceg niza transpozicija kojim se niz sortira.
Pretpostavimo da ti je dat niz
9,3,2,5,4,7,8,1,6
Sortiran izgleda ovako
1,2,3,4,5,6,7,8,9
Izaberi bilo koji element koji nije na svom mestu. Ja cu ovde primera radi uzeti 9. Na mestu na kome treba da je 9 stoji 6, a na mestu na kome treba da je 6 stoji 7, a na mestu na kome treba da je 7 stoji 8, a na mestu na kome treba da je 8 stoji 1, a na mestu na kome treba da je 1 stoji 9. Vratili smo se do 9 i belezimo ovaj ciklus:
(9,6,7,8,1)
Sada izaberimo bilo koji broj koji nije na svom mestu i koji nije u navedenom ciklusu. Ja cu uzeti broj 3. Na mestu na kome treba da je 3 stoji 2, a na mestu na kome treba da je 2 stoji 3. Vratili smo se do 3 i belezimo ovaj ciklus.
(3,2)
Broj 5 nije na svom mestu i nije u navedenim ciklusima. Na mesti na kome treba da je 5 stoji 4, a na mestu na kome treba da je 4 stoji 5. Vratili smo se do 5. Bezelimo ovaj ciklus:
(5,4)
Konacno, niz transpozicija je:
9,3,2,5,4,7,8,1,6 pocetno stanje
6,3,2,5,4,7,8,1,9 9 i 6 su zamenili mesta
7,3,2,5,4,6,8,1,9 6 i 7 su zamenili mesta
8,3,2,5,4,6,7,1,9 7 i 8 su zamenili mesta
1,3,2,5,4,6,7,8,9 8 i 1 su zamenili mesta
1,2,3,5,4,6,7,8,9 3 i 2 su zamenili mesta
1,2,3,4,5,6,7,8,9 4 i 5 su zamenili mesta
Dakle, broj transpozicija je zbir duzina ciklusaumanjenih za po 1, tj. zbir duzina svih ciklusa umanjen za ukupan broj ciklusa (u nasem slucaju (5-1)+(2-1)+(2-1)=(5+2+2)-3=6). Dati niz je nemoguce sortirati sa manjim brojem transpozicija.
Ovo je bio slucaj kada u nizu nema ponavljanja. U suprotnom, postupak je slican , samo sto sa vredosti treba preci na pozicije. Problem je u tome sto isti element moze biti na razlicitim pozicijama, pa treba naci ono resenje koje ima najveci broj ciklusa. Dakle, ciklusi treba da budu sto kraci.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.