Sorting an array in minimum cost

Question

I have an array A[] with 4 element A={ 8 1 2 4 }. How to sort it with minimized cost. Criteria is defined as follows-

a. It is possible to swap any 2 element.

b. The cost of any swap is sum of the element value , Like if i swap 8 and 4 the cost is 12 an resultant array is look like A={4 1 2 8}, which is still unsorted so more swap needed.

c. Need to find a way to sort the array with minimum cost.

From my observation greedy will not work, like in each step place any element to its sorted position in array with minimum cost. So a DP solution needed. Can any one help??

Answer 1

Swap 2 and 1, and then 1 and 4, and then 1 and 8? Or is it a general question?

For a more general approach you could try:

1. Swapping every pair of 2 elements (with the highest sum) if they are perfect swaps (i.e. swapping them will put them both at their right spot). Th

2. Use the lowest element as a pivot for swaps (by swapping the element whose spot it occupies), until it reaches its final spot

3. Then, you have two possibilities:

   1. Repeat step 2: use the lowest element not in its final spot as a pivot until it reaches its final spot, then go back to step 3

   2. Or swap the lowest element not in its final spot (l2) with the lowest element (l1), repeat step 2 until l1 reaches the final spot of l2. Then:

      1. Either swap l1 and l2 again, go to step 3.1
      2. Or go to step 3.2 again, with the next lowest element not in its final spot being used.

When all this is done, if some opposite swaps are performed one next to another (for example it could happen from going to step 2. to step 3.2.), remove them.

There are still some things to watch out for, but this is already a pretty good approximation. Step one and two should always work though, step three would be the one to improve in some borderline cases.

Example of the algorithm being used:

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

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

• Array is now {2, 4, 5, 3, 7, 8}

• Choice 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 is the better result

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

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

• You're beginning at step three already

• Choice 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)

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

Answer 2

This smells like homework. What you need to do is sort the array but doing so while minimizing cost of swaps. So, it's a optimization problem rather than a sorting problem.

A greedy algorithm would despite this work, all you do is that you fix the solution by swapping the cheapest first (figuring out where in the list it belongs). This is however, not necessarily optimal.

As long as you never swap the same element twice a greedy algorithm should be optimal though.

Anyway, back to the dynamic programming stuff, just build your solution tree using recursion and then prune the tree as you find a more optimal solutions. This is pretty basic recursion.

If you a more complicated sorting algorithm you'll have a lot more difficulty puzzling that together with the dynamic programming so I suggest you start out with a simple, slow O(n^2) sort. And build on top of this.

Rather than to provide you with a solution, I'd like to explain how dynamic programming works in my own words.

• The first thing you need to do, is to figure out an algorithm that will explore all possible solutions (this can be a really stupid brute force algorithm).
• You then implement this using recursion because dynamic programming is based around being able to figure out overlapping sub problems quickly, ergo recursion.
• At each recursive call you look up where you are in your solution and check where you've computed this part of the solution tree before, if you have done this, you can test whether the current solution is more optimal, if it is then you continue, otherwise you're done with this branch of the problem.
• When you arrive at the final solution you will have solved the problem.

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

This what I recommend you do:

1. Write a recursive sort algorithm
2. Add a parameter to your recursive function that maintains the cost of this execution path, as you sort the array, add to this cost. For every possible swap at any given point do another recursive call (this will branch your solution tree)
3. Whenever you realize that the cost of the solution you are currently exploring exceeds what you already have somewhere else, abort (just return).

To be able to answer the last question you need to maintain shared memory area in which you can index depending on where you are in you're recursive algorithm. If there's a precomputed cost there you just return that value and don't continue processing (this is the pruning, which makes it fast).

Using this method you can even base your solution on a permutation brute force algorithm, it will probably be very slow or memory intensive because it is stupid when it comes to when you branch or prune but you don't really need a specific sort algorithm to make this work, it will just be more efficient to go about it that way.

Good luck!