INOI 2009 #1

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?

Read more…(161 words)

About the author:

YG

Yasharyan Gaikwad

Loading…

Join the discussion. Add a reply…

Post

About the author

YG

Yasharyan Gaikwad

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.