Some swapping with bsort?
> Bill is a real clever boy. Yesterday, something unsuspected happened,
> though - he was given a homework he cannot solve. What's even worse -
> it's a puzzle he loves to solve so much!
> 
> The teacher wrote two sequences of lowercase latin alphabet letters.
> They're both the same length and have the same amount of given types
> of letters (the first has an equal number of t's as the second and so
> on). The pupils are to find how many swaps (by "swap" we mean changing
> the order of two neighboring letters) are there needed at least to
> transform the first sequence into the second. He told his pupils they
> can safely assume every two sequences he writes CAN be transoformed
> into each other. Bill could do this brute-force but the sequences the
> teacher wrote are quite long - help him!
> 
> INPUT: the length of the sequences (at least 2, at most 999999) and
> then two sequences the teacher wrote on the blackboard.
> 
> OUTPUT: an integer meaning the number of swaps needed for the
> sequences to become the same.
> 
> EXAMPLE: {5, aaaaa, aaaaa} should output {0}, {4, abcd, acdb} should
> output {2}.

So the first thing that came to my mind was bubblesort. We can simply bubblesort the sequence counting each swap. The problem is: a) it's O(n^2) worst-case b) I'm not convinced it would give me the smallest number for every case... Even the optimized bubblesort doesn't seem to be doing the trick. We could implement the cocktail sort which would solve the problem with turtles - but will it give me the best performance? Or maybe there's something simpler/faster?
Some swapping with bsort?
===

> Bill is a real clever boy. Yesterday, something unsuspected happened,
> though - he was given a homework he cannot solve. What's even worse -
> it's a puzzle he loves to solve so much!
> 
> The teacher wrote two sequences of lowercase latin alphabet letters.
> They're both the same length and have the same amount of given types
> of letters (the first has an equal number of t's as the second and so
> on). The pupils are to find how many swaps (by "swap" we mean changing
> the order of two neighboring letters) are there needed at least to
> transform the first sequence into the second. He told his pupils they
> can safely assume every two sequences he writes CAN be transoformed
> into each other. Bill could do this brute-force but the sequences the
> teacher wrote are quite long - help him!
> 
> INPUT: the length of the sequences (at least 2, at most 999999) and
> then two sequences the teacher wrote on the blackboard.
> 
> OUTPUT: an integer meaning the number of swaps needed for the
> sequences to become the same.
> 
> EXAMPLE: {5, aaaaa, aaaaa} should output {0}, {4, abcd, acdb} should
> output {2}.

So the first thing that came to my mind was bubblesort. We can simply bubblesort the sequence counting each swap. The problem is: a) it's O(n^2) worst-case b) I'm not convinced it would give me the smallest number for every case... Even the optimized bubblesort doesn't seem to be doing the trick. We could implement the cocktail sort which would solve the problem with turtles - but will it give me the best performance? Or maybe there's something simpler/faster?