Computer Science Canada Sorting |
Author: | klopyrev [ Wed Mar 07, 2007 5:59 pm ] |
Post subject: | Sorting |
Suppose you have a permutation of n elements. Here is an example of 7: 2 1 3 7 4 5 6 Here are two ways to sort it: 2 1 3 7 4 5 6 Swap 2 and 1 1 2 3 7 4 5 6 Swap 7 and 4 1 2 3 4 7 5 6 Swap 7 and 5 1 2 3 4 5 7 6 Swap 7 and 6 1 2 3 4 5 6 7 Second way: 2 1 3 7 4 5 6 Swap 2 and 1 1 2 3 7 4 5 6 Swap 6 and 7 1 2 3 6 4 5 7 Swap 4 and 5 1 2 3 6 5 4 7 Swap 4 and 6 1 2 3 4 5 6 7 In the first example, the element 7 is moved 3 times. In fact, 3 times is the maximum number of times any element is moved. In the second example, both 4 and 6 are moved 2 times. In fact, 2 times is the maximum number of times any element is moved. Provide an algorithm for minimizing the maximum of the number of times any element is moved. (0 < n < 5000) KL |
Author: | wtd [ Wed Mar 07, 2007 7:39 pm ] |
Post subject: | RE:Sorting |
In anything other than very large cases, trying to deduce a better way to sort is probably going to be more resource intensive than just using quicksort. ![]() |
Author: | rdrake [ Wed Mar 07, 2007 9:22 pm ] |
Post subject: | RE:Sorting |
Looks bubblesortyish to me. |
Author: | Martin [ Wed Mar 07, 2007 9:25 pm ] |
Post subject: | RE:Sorting |
Although in C++, the STL uses an introsort, which is a quicksort to a specific depth of recursion and then a merge sort for the rest. That aside, I'm not really sure what you're asking klopyrev. Do they want you to derive the algorithm, or for this algorithm, prove what the minimum swaps are be in relation to n? |
Author: | klopyrev [ Wed Mar 07, 2007 9:31 pm ] |
Post subject: | Re: Sorting |
I need any algorithm to do that, because I ran out of ideas ![]() KL Quote: That aside, I'm not really sure what you're asking klopyrev. Do they want you to derive the algorithm, or for this algorithm, prove what the minimum swaps are be in relation to n? Actually, the minimum number of swaps needed will always be the number of inverses there are in the sequence ( an inverse is ai > aj, i<j). However, as I showed, there are several ways to perform the minimum number of swaps. Something like bubble sort would prefer the first way I showed. Bubble sort would maximize the movement of each individual element. If the smallest element is last in the sequence, it would be involved in n-1 swaps. I need an algorithm that minimizes the movement of individual elements. For example, such an algorithm would, in the case of smallest element last, take that smallest element and put it first, resulting only in one movement of that individual element. |
Author: | haskell [ Wed Mar 07, 2007 10:30 pm ] |
Post subject: | RE:Sorting |
I get it. Basically get the upper and lower extremes of the data, place them in n.max and n.min respectively, and then remove those extremes from the data, take the extremes of the modified data and place them in n.max-1 and n.min+1 respectively, then remove those extremes from the data, and so on. Atleast thats how I see it. |
Author: | OneOffDriveByPoster [ Wed Mar 07, 2007 10:37 pm ] |
Post subject: | Re: RE:Sorting |
Is there a practical reason to minimize the number of moves for each element? Not that trying to derive an algorithm is not interesting. |
Author: | haskell [ Wed Mar 07, 2007 10:48 pm ] |
Post subject: | RE:Sorting |
Here is how I'd set up the algorithm for this: Basically get the upper and lower extremes of the data, place them in n.max and n.min respectively, and then shift the rest of the data. You can expand this by moving through the numbers from the most extreme to the median from both directions. Like with the text data 2 1 3 7 4 5 6 . 1 2 3 7 4 5 6 1 is removed and appended to the start(0), after the rest is shifted >>. 1 2 3 4 5 6 7 7 is removed and appended to the end, after 7's element is shifted <<. This could also be applied in a larger scale. 2 3 6 5 4 7 1 // Original Data 1 2 3 6 5 4 7 // Lower extreme is placed 1 2 3 6 5 4 7 // Upper extreme is placed. Skipped since it is already in place. 1 2 3 6 5 4 7 // Number closest the to lower extreme is placed. 1 2 3 5 4 6 7 // Number closest to the upper extreme is placed. 1 2 3 4 5 6 7 // Number nth closest to the lower extreme is placed. 1 2 3 4 5 6 7 // Number nth closest to the upper extreme is placed. 1 2 3 4 5 6 7 // Final Data This is done in 6 swaps, like you said it would be. Atleast this is how I see this problem. And yes, minimizing movement can be correlated to optimization. But, no, this is not extemely practical, but in all honesty, what pure theory is purely practical? |
Author: | OneOffDriveByPoster [ Wed Mar 07, 2007 11:09 pm ] |
Post subject: | Re: RE:Sorting |
haskell @ Wed Mar 07, 2007 10:48 pm wrote: 2 3 6 5 4 7 1 // Original Data
1 2 3 6 5 4 7 // Lower extreme is placed This shift operation is expensive in terms of swaps I think. |
Author: | klopyrev [ Wed Mar 07, 2007 11:19 pm ] |
Post subject: | Re: Sorting |
I think I may have explained it incorectly, so I'm just going to give you the original question for which I need a solution to (It's translated from russian): On a bazaar, there are n salesmen. Each one has a certain distinct good he can trade (that means he is the only one who has that good). Also, each salesman wants a certain good for himself. Someone else in the bazaar has that good. By chance, each salesman wants for himself a distinct good and no one wants the same one. In order to prevent cheating, trades can only happen in pairs. Also, each salesman can only make one trade per day, but the total number of trades on any day can be any. During an exchange, the two salesman give all of their good to each other. It is a complete exchange. However, each salesman understands that if it is impossible to trade for the good he wants right away, he can still get it through a complex series of trades. Your task is to write a program that finds the minimum number of days it takes for each salesman to get the good he wants. You are also to find the correct sequence of trades. Input: On the first line will be the number N, not exceeding 5000. Then, on the second line, there will be a list of n goods that each salesman needs. If at index i is the number j, that means that salesman i wants the good that initially salesman j has. Output: For each test, output the minimum number of days m on the first line. Then, on the next m lines, indicate first the number of trades that happen during a day and then all the trades that happen on that day. A trade is indicated by the number of the salesman, a dash ("-"), and the number of the other salesman. If there are several correct solutions, output any one. Sample: Input: 7 2 1 3 5 6 7 4 Output: 2 3 1-2 4-5 7-6 1 5-7 |
Author: | klopyrev [ Wed Mar 07, 2007 11:33 pm ] |
Post subject: | Re: Sorting |
Basically, what the question is asking is how to sort the sequence minimizing the amount of times each location is touched. Note that sorting the original sequence given will be attained by following the answer given backwards. Thus: To sort 2 1 3 5 6 7 4 Switch elements 1 and 2, 6 and 7, 4 and 5. 1 2 3 6 5 4 7 During that first switch, locations 1, 2, 4, 5, 6 and 7 were accessed. Then, switch elements 4 and 6. 1 2 3 4 5 6 7 During the second switch, locations 4 and 6 were accessed. Overall, locations 1, 2, 5 and 7 were each accessed once, while locations 4 and 6 were each accessed twice. The task is to minimize the maximum number of accessed of each memory location during sorting. |
Author: | bugzpodder [ Thu Mar 08, 2007 7:40 am ] |
Post subject: | Re: Sorting |
2 1 3 7 4 5 6 cycles: 2 1 --> 1 2 3 --> 3 4 5 6 7 -> 7 4 5 6 the answer is ceil(n/2) where n is the longest cycle. n/2 is a bit greedy, not entirely sure if it works. if it doesnt some memo/dp approach is needed. |
Author: | bugzpodder [ Thu Mar 08, 2007 8:19 am ] | ||
Post subject: | Re: Sorting | ||
I think here is a very simple algorithm that realizes n/2 swaps where n is the longest cycle. is your brother gonna use it as an interview question? ![]()
|
Author: | rdrake [ Thu Mar 08, 2007 9:41 am ] | ||
Post subject: | RE:Sorting | ||
One of the few things I enjoyed writing in C++.
|
Author: | bugzpodder [ Thu Mar 08, 2007 9:59 am ] |
Post subject: | RE:Sorting |
but we are trying to minimize the max number of swaps involving each element, no? |
Author: | klopyrev [ Thu Mar 08, 2007 10:27 am ] |
Post subject: | Re: Sorting |
Yes. Minimize the number of swaps that involve each memory location or index of the array. KL |
Author: | bugzpodder [ Thu Mar 08, 2007 10:48 am ] |
Post subject: | RE:Sorting |
yes, I have done that already. |
Author: | klopyrev [ Thu Mar 08, 2007 5:46 pm ] |
Post subject: | Re: Sorting |
I tried your solution, bugz, but even though it works for some of the test cases, it doesn't work for all of them. I don't actually know the test cases, so I don't know what's wrong with it. KL |
Author: | bugzpodder [ Thu Mar 08, 2007 6:55 pm ] |
Post subject: | RE:Sorting |
you are suppose to come up with your own solution. and i think i found a bug. I was trying to be minimalist. I shouldn't be swapping arr[i] twice in my code. just do a boolean array to see if arr[i] is swapped in the same day and if it is, dont swap it. again i am not sure if it fixes the problem since i havent tested it yet, but i am reasonably sure my general algorithm works. at least the first one i described: find the longest cycle n, then just return n/2. which approach did you try? |
Author: | klopyrev [ Thu Mar 08, 2007 7:02 pm ] |
Post subject: | Re: Sorting |
yeah, I noticed the bug too. I actually submitted one solution with the bug, which didn't work. Then I noticed the bug and just when I was going to submit it, the site went down ![]() KL EDIT: Still doesn't work. You are missing a key part of the problem, though. You have to actually specify how you would do it in the minimum number of days. |
Author: | bugzpodder [ Thu Mar 08, 2007 7:58 pm ] |
Post subject: | RE:Sorting |
I can't say what is wrong without knowing what you submitted. perhaps if you post your source I could spot for bugs. |
Author: | klopyrev [ Thu Mar 08, 2007 8:43 pm ] | ||
Post subject: | Re: Sorting | ||
Here it is! Do you like Java?
|
Author: | Brightguy [ Fri Mar 09, 2007 12:06 am ] |
Post subject: | Re: RE:Sorting |
wtd @ Wed Mar 07, 2007 7:39 pm wrote: In anything other than very large cases, trying to deduce a better way to sort is probably going to be more resource intensive than just using quicksort.
![]() Heh, you shamelessly open that can of worms! Just don't say that in an algorithms class or you'll get kicked out on the spot. ![]() It looks like bugz essentially has it, though I don't know where he got the n/2 thing from. The minimum number transpositions needed to represent any permutation of n elements is n - r, where r is the number of distinct cycles. Since there is always at least 1 cycle, in the worst case n-1 swaps will be the minimum number of swaps needed. |
Author: | bugzpodder [ Fri Mar 09, 2007 1:20 am ] | ||
Post subject: | RE:Sorting | ||
I can't find a bug in the code. but something may be of interest to you, you could cut the length of your code by half by just printing the swaps in the middle of the loop instead of creating those linked lists and have a new swap class. either attach them to a string or if its too slow, some kind of buffered writer. Here are some theoretical proof that doesnt exactly proof my claims, but it does prove something. 1. every permutation can be divided into disjoint cycles. By a bijection we can assume each cycle is in the form:
Thus let f(n) be the number of days needed to get the trades done in a cycle of length n. Notice we can greedily only trade between members in the cycle, since there is no point in involving traders in another cycle. Now I show my algorithm is correct (well there is a flaw somewhere, either in the algorithm or in its implementation) In a cycle, we can make at most floor (n/2) trades in a day. However what we are doing is placing exactly floor(n/2) traders with the item they desire, so this is the best we can do ever. In a single trade in a cycle of n>2, we can never match the request for two traders simultaneously, since it would mean that they form a cycle of 2. |
Author: | klopyrev [ Fri Mar 09, 2007 2:15 am ] |
Post subject: | Re: Sorting |
Cutting down in size by printing inside the actual loop will not work, because I have to print all the days backwards, since the starting point is 1 2 3 4 5 6 7 and you have to get 2 1 3 5 6 7 4. Otherwise, I really don't understand why its wrong either. Take a look at the translation of the original problem I posted and perhaps you can help me think of cases that will break my code. Thanks for the input. I'm going to take a look at the sorting chapter in Art of Computer Programming now to see if I can find something to help me out. KL |
Author: | bugzpodder [ Fri Mar 09, 2007 2:21 am ] |
Post subject: | RE:Sorting |
i figured out what the fuck was wrong (i think) consider this case: 1 7 8 2 .. 7 8 2 3 .. the point is 8 would skipped. I want to switch adjacent elements in a cycle, but the way I did it it was breaking the cycle which is bad. btw you owe me an hour of sleep ![]() |
Author: | klopyrev [ Fri Mar 09, 2007 2:31 am ] |
Post subject: | Re: Sorting |
I don't completely understand what you mean. KL |
Author: | bugzpodder [ Fri Mar 09, 2007 9:50 am ] |
Post subject: | RE:Sorting |
you have to follow through a cycle. if the cycle are in the order 1 7 8 2 5 4 you must swap 1,7 8,2 5,4 if you swap in order, you might swap 1,7 2,5 |
Author: | klopyrev [ Fri Mar 09, 2007 3:11 pm ] |
Post subject: | Re: Sorting |
I still don't understand how that applies to this problem ![]() |
Author: | bugzpodder [ Fri Mar 09, 2007 4:10 pm ] |
Post subject: | Re: Sorting |
that means you can't swap arr[i] with arr[arr[i]] because you'll end up with things like 1,7 2,5 which skips an element in the middle (which is bad if you skip several single elements in a chain) |
Author: | klopyrev [ Fri Mar 09, 2007 4:39 pm ] |
Post subject: | Re: Sorting |
But if you skip the element, you then get it during the next day? Can you give me a complete example of the algorithm not working. I'm kind of slow ![]() |
Author: | bugzpodder [ Fri Mar 09, 2007 10:45 pm ] |
Post subject: | RE:Sorting |
but we want to get as many trades in as possible in a single day right? hmm lets see... its difficult to construct 1 2 3 4 5 6 7 8 4 6 1 5 2 7 8 3 that is my starting point 1 2 3 4 5 6 7 8 5 7 1 4 2 6 3 8 1 2 3 4 5 6 7 8 2 3 1 4 5 6 7 8 1 2 3 4 5 6 7 8 3 2 1 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 so this is 4 days. 1 4 5 2 6 7 8 3 4 5 2 6 7 8 3 1 1 4 5 2 6 7 8 3 5 4 6 2 8 7 1 3 1 4 5 2 6 7 8 3 6 4 5 2 1 7 8 3 1 4 5 2 6 7 8 3 1 4 5 2 6 7 8 3 three steps |
Author: | Brightguy [ Sat Mar 10, 2007 7:45 am ] | ||||
Post subject: | Re: Sorting | ||||
Oh, I see now the problem was modified to minimize days, but n/2 still isn't right. For a cycle of length n you can do a maximum of floor(n/2) swaps per day, but you still have a cycle of ceil(n/2) left over... so if n is the length of the longest of the cycles, then ceil(lg(n)) is the minimum number of days. (lg is base 2) Here's the algorithm to solve your original problem in a minimum number of steps:
Better than quicksort, no? ![]() ![]() However, if you also want to minimize the number of days, you have to find a better way to split up the cycles. As bugz noted, for every cycle of length n the maximum number of swaps we can do every day is floor(n/2), and we don't want to skip elements in the middle of a cycle. So, after swapping the values of A[i] and A[A[i]] we want to swap the values of A[A[A[i]]] and A[A[A[A[i]]]]. We can do this by keeping track of which element we want to swap, and have it advance after the swap has been completed:
In cycle notation, for a cycle (abcdefgh), the first algorithm will use transpositions (ah)(gh)(fg)(ef)(de)(cd)(bc) while the second will use (ae)(ag)(ce)(ah)(fg)(de)(bc). Notice that the first requires 8 days as there is a common good in every consecutive trade (in fact one salesman is involved in every trade), but in the second the swaps can be done in just 3 days: (ah)(fg)(de)(bc) in day 1, (ag)(ce) in day 2 and (ae) in day 3 [read right to left], with each salesman only making no more than one trade a day. I'll leave it to you to output the proper swaps. ![]() |