Now we come to a programming assignment,
which is just to classify a given permutation.
So, how it looks on the programmer's viewpoint.
Permutation can be instead of letters,
it's easier to deal with numbers.
So immediately, we have n numbers--1, 2, 3,
4, n--and they are in some array in arbitrary order. They are permuted.
And the question is whether this permutation's even or
odd and you should try in 0 and 1 for example.
Zero is an even number so it's more neutral to use
even permutations. How will you do this?
One of the possible approaches,
not actually the most effective one,
but still easy and rather effective.
Probably you have taken a programming course,
and maybe you have seen
a problem when the permutation was obtained by a sequence of transposition.
Do you remember something like this?
Sorting is the answer.
So when you want to sort an array,
initially the array is in some random order and we need to bring it to the normal order,
and many sorting algorithm use permutation for that.
Not all, there are some more advanced algorithm like node-sort
or whatever but many of them use transpositions,
exchanges, where at each step you exchange two elements of the array.
If the sorting algorithm use exchanges,
it can be used to find better permutations algorithm,
just count the number exchanges to see whether it's odd or even.
And we even have a piece of code.
But let me tell you that there is an intentional error.
So you should be careful to understand
where the error is but let me explain what has happening.
So this is the array given to us.
We want to sort it,
and this is an additional variable which is not in the original sorting algorithm.
It's just a number of those position with 0 or 1.
It flips back and forth.
So that is a simple algorithm of sorting.
We put first elements in the right place from left to right.
So we put first the minimal element in the first place,
and the second element on the second place and so on.
So here's how you write this algorithm.
So there some variable S,
which counts how many elements are at the right place,
and usually there are none of them.
And at the end,
we want to have n elements.
So while S is less than n we continue doing things.
So we can even show S elements are already okay.
And this is the rest.
So you start with S + 1,
you put u here and also t here.
And now a of t is minimal element among the rest- not among the rest,
but among this part between s + 1 and u because it's only one element.
And then the idea is you move u, you increase u,
and always you keep a of t minimal among this element.
So you increase u,
and there is a new element.
The last one, which is not checked.
And if this last one is smaller than the current minimum,
then we need to move the current minimum in a different place.
And after u is equal to n,
here u is equal to n,
so a of t is minimal among all the rest.
And then, what remains to do is to exchange this minimal element somewhere.
Here is the minimal element t and you exchange it with
u and get one more element in the right place.
Here is additional operation.
We keep track of whether we'll making even or odd number of exchanges.
So it looks very convincing but do you see the error? There isn't.
Now, maybe there are some unintentional error but there is
one intentional error in this program.
Can you see it?
Okay, you can try it for some examples and then you will see the problem.
Actually, you will see that the answer doesn't depend on the error for some reason.
And then you can think what is the reason and how to correct the thing.
What is wrong with this code?
You should find and you should find out how to correct it.
