Sorting an array at the lowest cost

Question

I have an array A [] with 4 elements A = {8 1 2 4}. How to sort it with minimal cost. The criteria are defined as follows:

a. You can change any item 2.

b. The value of any swap is the sum of the value of the element. For example, if I exchange 8 and 4, the cost is 12, the resulting array looks like A = {4 1 2 8}, which is still not sorted, so more swap is required.

from. You need to find a way to sort the array at minimal cost.

From my observation, greedy will not work, as at every step put any element in its sorted position in the array with minimal cost. Therefore, a DP solution is needed. Can anyone help?

Answer 1

Translate 2 and 1 and then 1 and 4 and then 1 and 8? Or is this a general question?

For a more general approach, you can try:

• Switching each pair of two elements (with the largest sum) if they are perfect swaps (i.e. replacing them will bring them to their right place). Th

• Use the bottom element as a swap vault (by replacing the element it takes its place) until it reaches its final place

• Then you have two options:

  • Repeat step 2: use the bottom element not in its final spot as a rotation until it reaches its final spot, and then return to step 3

  • Or replace the bottom element not in its last place (l2) with the smallest element (l1), repeat step 2 until l1 reaches the final spot l2. Then:

    • Change l1 and l2 again, go to step 3.1
    • Or go to step 3.2 and the next lower item will not be used in the last place.

When all this is done, if some opposing swaps are executed next to each other (for example, this may occur from going to step 2. to step 3.2.), Delete them.

There is still something to which you can pay attention, but this is already a pretty good approximation. Step 1 and 2 should always work, although the third step will be improved in some borderline cases.

An example of the algorithm used:

C {8 4 5 3 2 7}: (target array {2 3 4 5 7 8})

• Step 2: 2 <> 7, 2 <> 8

• Now the array {2, 4, 5, 3, 7, 8}

• Choosing between 3.1 and 3.2:

  • 3.1 gives 3 <5, 3 <4

  • 3.2 gives 2 <3, 2 <> 5, 2 <4, 2 <3 </>

  • 3 <> 5, 3 <> 4 - the best result

Conclusion: 2 <> 7, 2 <> 8, 3 <> 5, 3 <> 4 - the best answer.

C {1 8 9 7 6} (resulting array {1 6 7 8 9})

• You are already in the third step

• Choosing between 3.1 and 3.2:

  • 3.1 gives 6 <> 9, 6 <> 7, 6 <> 8 (total: 42)

  • 3.2 gives 1 <6, 1 <> 9, 1 <7, 1 <> 8, 1 <6 (total: 41)

Thus, 1 <> 6, 1 <> 9, 1 <> 7, 1 <> 8, 1 <> 6 is the best result

Answer 2

It smells of homework. What you need to do is sort the array, but minimize the cost of swaps. So this is an optimization problem, not a sorting problem.

The greedy algorithm, despite this work, all you do is that you fix the solution by first replacing the cheapest one (finding out where in the list it belongs). This, however, is not necessarily optimal.

As long as you never change the same element twice, the greedy algorithm should be optimal.

In any case, back to the dynamic programming material, just create a decision tree using recursion, and then prune the tree when you find more optimal solutions. This is a fairly simple recursion.

If you have a more complex sorting algorithm, you will have much more problems than with dynamic programming, so I suggest you start with a simple, slow sorting of O(n^2) . And build on top of it.

Instead of providing you with a solution, I would like to explain how dynamic programming works in my own words.

• The first thing you need to do is figure out an algorithm that will investigate all possible solutions (it can be a really stupid brute force algorithm).
• Then you implement this with recursion, because dynamic programming is based on the ability to quickly find overlapping routines, ergo regression.
• With each recursive call, you look where you are in your solution and check where you have already computed this part of the decision tree, if you did, you can check if the current solution is more optimal if you continue, otherwise you finish with this branch of the problem.
• When you come to a final solution, you will solve the problem.

Think of each recursive call as a snapshot of a partial solution. It is your job to understand how each recursive call fits together in the final optimal solution.

This is what I recommend you:

• Write a recursive sorting algorithm
• Add a parameter to the recursive function that supports the cost of this execution path, add this value as you sort the array. For each possible exchange, at any given point, another recursive call is made (this will lead to branching of the decision tree).
• Whenever you realize that the cost of the solution that you are currently studying is higher than what you already have elsewhere, interrupt (just return).

To be able to answer the last question, you need to maintain a shared memory area in which you can index, depending on where you are, you are a recursive algorithm. If there is a pre-calculated value, you simply return this value and do not continue processing (this is a reduction that makes it quick).

Using this method, you can even base your decision on a permutation sorting algorithm, it will probably be very slow or intense, because it is stupid when it comes to branches or pruning, but you don’t need a specific sorting algorithm to make this work. It will be more effective to go this route.

Good luck

Answer 3

If you are sorting with a high low level, you can guarantee that the Nth largest element will not be replaced more than N times. This is a simple algorithm with a fairly simple and tempting guarantee ... Perhaps check this with a few examples and see how it can be configured. Note: this may not lead to an optimal answer ...

Answer 4

To find the absolute minimum cost, you will have to try all the exchange methods, and then find the fastest.

 def recsort(l, sort): if sorted(l2): if min>cost: cost=min bestsort=sort if(len(sort) > len(l)*len(l)): //or some other criteria return for p1 in (0,len(l)): for p2 in (0,len(l)): cost += l[p1] + l[p2] l2 = swap(l, p1,p2) if cost<min: recsort(l2, append sort (p1,p2)) 

An approach that will be very good is to recursively place the highest value at the top.