Help to find number of swap operation need to sort data

Let's talk about algorithms!

Moderator: Board moderators

nahidshahin
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

Post by nahidshahin »

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac »

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
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov »

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac »

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

Andrey's method is correct.

nahidshahin
New poster
Posts: 8
Joined: Mon Nov 10, 2003 10:54 am
Location: Bangladesh
Contact:

Post by nahidshahin »

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac »

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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

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

-titid-
Kalo mau kaya, buat apa sekolah?

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa »

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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

how if we are allowed to swap only adjacent elements?
Kalo mau kaya, buat apa sekolah?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

titid_gede wrote:how if we are allowed to swap only adjacent elements?
That's question 299.. and the answer is bubblesort

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

Post by titid_gede »

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

thanks.
Kalo mau kaya, buat apa sekolah?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

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
New poster
Posts: 5
Joined: Wed Dec 17, 2003 6:18 pm
Location: Poland

Post by Corpse Fiend »

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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

assume sort in ascending order :)

regards,
titid
Kalo mau kaya, buat apa sekolah?

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

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).

Post Reply

Return to “Algorithms”