Help to find number of swap operation need to sort data

nahidshahin · Post by **nahidshahin** » Thu Dec 11, 2003 1:57 am

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

gvcormac · Post by **gvcormac** » Sat Dec 13, 2003 5:24 am

The simple approach is to do a bubble sort and count the number of swaps. If you want a more efficient algorithm, you can build it on top of a quicker sort, like quicksort or merge sort.

Andrey Mokhov · Post by **Andrey Mokhov** » Sat Dec 13, 2003 7:34 am

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 (length-1) operations. So here we need (2-1)+(1-1)+(1-1) 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.

gvcormac · Post by **gvcormac** » Sat Dec 13, 2003 11:31 am

Sorry, I misread the original question. (My method was to count the number
of swaps of adjacent elements.)

Andrey's method is correct.

nahidshahin · Post by **nahidshahin** » Tue Dec 16, 2003 4:01 am

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]

gvcormac · Post by **gvcormac** » Tue Dec 16, 2003 4:10 am

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 n-1
swaps, where n is the length of the cycle.
Any permutation can be expressed as the
composition of cyclic permutations, which are
independent.

titid_gede · Post by **titid_gede** » Fri Dec 19, 2003 6:49 am

how's about 5 4 3 2 1?
what is cyclic representation?
is it (2 1 4 5) (3) or what?

-titid-

CDiMa · Post by **CDiMa** » Fri Dec 19, 2003 11:29 am

titid_gede wrote:how's about 5 4 3 2 1?
what is cyclic representation?
is it (2 1 4 5) (3) or what?

(1 5) (2 4) (3)

Ciao!!!

Claudio

titid_gede · Post by **titid_gede** » Fri Jan 09, 2004 5:14 am

how if we are allowed to swap only adjacent elements?

junbin · Post by **junbin** » Fri Jan 09, 2004 6:13 am

titid_gede wrote:how if we are allowed to swap only adjacent elements?

That's question 299.. and the answer is bubblesort

titid_gede · Post by **titid_gede** » Fri Jan 09, 2004 7:06 am

ups, i forgot to say something. The array is circular, (like 10570 meeting the aliens). but we can only swap adjacent element. how?

thanks.

junbin · Post by **junbin** » Fri Jan 09, 2004 11:52 am

titid_gede wrote:ups, i forgot to say something. The array is circular, (like 10570 meeting the aliens). but we can only swap adjacent element. how?

thanks.

same algorithm, brute force.

Corpse Fiend · Post by **Corpse Fiend** » Thu Jan 15, 2004 5:24 pm

CDiMa wrote:
titid_gede wrote:how's about 5 4 3 2 1?
what is cyclic representation?
is it (2 1 4 5) (3) or what?
(1 5) (2 4) (3)

Is it good way to solve it?
(2-1)+(2-1)+(1-1)=2
...but the correct answer should be 0, right?

titid_gede · Post by **titid_gede** » Thu Jan 15, 2004 6:13 pm

assume sort in ascending order

regards,
titid

UFP2161 · Post by **UFP2161** » Thu Jan 15, 2004 6:14 pm

If you want to convert 5 4 3 2 1 to 5 4 3 2 1, the answer is obviously zero. However, if you wanted to convert 5 4 3 2 1 to 1 2 3 4 5, then the answer is 2, with the cylic representation given as (1 5) (2 4) (3).