Sorting

[klopyrev]

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

[wtd]

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.

[rdrake]

Looks bubblesortyish to me.

[Martin]

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?

[klopyrev]

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.

[haskell]

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.

[OneOffDriveByPoster]

Is there a practical reason to minimize the number of moves for each element? Not that trying to derive an algorithm is not interesting.

[haskell]

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?

[OneOffDriveByPoster]

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.

[klopyrev]

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

[klopyrev]

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.

[bugzpodder]

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.

[bugzpodder]

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? Havent tried to compile the code yet so no idea if it works or not.

code:

flag = true; while (1) {     flag = false;     for (int i=0;i<N;i++)         if (arr[i]!=arr[arr[i]])         {              flag = true;              swap(arr[i],arr[arr[i]]);         }     if (flag) days++; }

[rdrake]

One of the few things I enjoyed writing in C++.

code:

void bubbleSort(int list[], int size) {      // Added and initialized the count variable.      int i, count = 0, j;      bool done;            done = FALSE;      while(!done) {              done = TRUE;              for(i=0; i<size-1; i++) {                       // Changed the operator.                       if(list[i] < list[i+1]) {                                  swap(list[i],list[i+1]);                                  done = FALSE;                                  count++;                       }                   j++;                 }                    print(list,size);      }            cout << "Counted " << j << " iterations and " << count << " swaps made." << endl; }

Something like Bugz wrote up above, this one's tested though.

[bugzpodder]

but we are trying to minimize the max number of swaps involving each element, no?