Help to find number of swap operation need to sort data
Moderator: Board moderators

 New poster
 Posts: 8
 Joined: Mon Nov 10, 2003 10:54 am
 Location: Bangladesh
 Contact:
Help to find number of swap operation need to sort data
Someone please help me to find the number of swap operation need to sort a set of data. For example if data set is 4 2 3 1 then only one swap opration is enough to sort in increasing order. Here we just swap 4 and 1.
ThankYou Very Much
ThankYou Very Much

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
Hello!
I think that nahidshahin means to find the least possible number of exchanges. Sorting won't give you the right answer. The only way I know is to count the cycles in the permutation defined by the given sequence.
Let's take for example your data 4 2 3 1. It can be rewriten this way (14)(2)(3). Here we see one cycle of length 2 and two of length 1. The key idea is that: to sort a cycle optimally we need (length1) operations. So here we need (21)+(11)+(11) swaps.
Another example 2 3 1. Its cycle representation is (123)  one cycle of length 3  so we need 2 swaps to sort it.
I don't know whether such approach is the fastest or not, but it is correct  I used it in some problems and got AC. In fact I think it is the fastest  it can be realized in O(n) complexity.
Good luck!
Andrey.
I think that nahidshahin means to find the least possible number of exchanges. Sorting won't give you the right answer. The only way I know is to count the cycles in the permutation defined by the given sequence.
Let's take for example your data 4 2 3 1. It can be rewriten this way (14)(2)(3). Here we see one cycle of length 2 and two of length 1. The key idea is that: to sort a cycle optimally we need (length1) operations. So here we need (21)+(11)+(11) swaps.
Another example 2 3 1. Its cycle representation is (123)  one cycle of length 3  so we need 2 swaps to sort it.
I don't know whether such approach is the fastest or not, but it is correct  I used it in some problems and got AC. In fact I think it is the fastest  it can be realized in O(n) complexity.
Good luck!
Andrey.

 New poster
 Posts: 8
 Joined: Mon Nov 10, 2003 10:54 am
 Location: Bangladesh
 Contact:
Thanks Andrey
You are right, i want to find the least possible number of exchanges.
Your method is first, but I can't understand the term "cycle".
Why 4 2 3 1 is written (14)(2)(3) why not (14)(23).
and how 4 2 3 1 => (14)(2)(3).
do we make a left shift then place 1 at first or not?
I can't understand.
Please help me
ThankYou again.
Nahid[/b]
You are right, i want to find the least possible number of exchanges.
Your method is first, but I can't understand the term "cycle".
Why 4 2 3 1 is written (14)(2)(3) why not (14)(23).
and how 4 2 3 1 => (14)(2)(3).
do we make a left shift then place 1 at first or not?
I can't understand.
Please help me
ThankYou again.
Nahid[/b]
Just do the obvious thing.
1. Find the position that each element should be at.
2. Find an element that's out of place and swap it with the one that is in its spot
3. repeat until you're done
The notation (x y z) is a cyclic permutation in which y replaces x; z replaces y; x replaces z.
Any cyclic permutation can be done with n1
swaps, where n is the length of the cycle.
Any permutation can be expressed as the
composition of cyclic permutations, which are
independent.
1. Find the position that each element should be at.
2. Find an element that's out of place and swap it with the one that is in its spot
3. repeat until you're done
The notation (x y z) is a cyclic permutation in which y replaces x; z replaces y; x replaces z.
Any cyclic permutation can be done with n1
swaps, where n is the length of the cycle.
Any permutation can be expressed as the
composition of cyclic permutations, which are
independent.

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut

 New poster
 Posts: 5
 Joined: Wed Dec 17, 2003 6:18 pm
 Location: Poland

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut