I need some help. Question paper can be found here. For the problem 1, I have written a code which works similar to bubble sort.
Given a list <x1, x2, ..., xn>, first place x1 correctly, then x2, then x3, ..., then xn.
For example, given the list A = <34, 29, 12, 78 90> which needs to be transformed into B = <90, 29, 78, 34, 12>, start by placing 90 in it's place to get A = <90, 34, 29, 12, 78>. Total swaps as yet = 4. Now place 29 correctly to get A = <90, 29, 34, 12, 78>. Total swaps as yet = 5. Now put 78 correctly to get A = <90, 29, 78, 34, 12> which was the required list. Swaps required = 7.
This seems correct but since there is no test data available, I cannot test it. Is my algorithm correct? If it is any ideas on how to prove it?