Sort array in ascending order while minimizing "cost"

Question

I'm taking comp 2210 (Data Structures) next semester and I've been doing the homework for the summer semester that is posted online. Until now, I've had no problems doing the assignments. Take a look at assignment 4 below, and see if you can give me a hint as to how to approach it. Please don't provide a complete algorithm, just an approach. Thanks!

A “costed sort” is an algorithm in which a sequence of values must be arranged in ascending order. The sort is carried out by interchanging the position of two values one at a time until the sequence is in the proper order. Each interchange incurs a cost, which is calculated as the sum of the two values involved in the interchange. The total cost of the sort is the sum of the cost of the interchanges.

For example, suppose the starting sequence were {3, 2, 1}. One possible series of interchanges is

Interchange 1: {3, 1, 2} interchange cost = 0 
Interchange 2: {1, 3, 2} interchange cost = 4 
Interchange 3: {1, 2, 3} interchange cost = 5, 
given a total cost of 9

You are to write a program that determines the minimal cost to arrange a specific sequence of numbers.

Edit: The professor does not allow brute forcing.

Answer 1

If you want to surprise your professor, you could use Simulated Annealing. Then again, if you manage that, you can probably skip a few courses :). Note that this algorithm will only give an approximate answer.

Otherwise: try a Backtracking algorithm, or Branch and Bound. These will both find the optimal answer.

Answer 2

Have you learned trees? You could create a tree with all possible changes leading to the desired result. The trick, of course, is to avoid creating the whole tree -- particularly when a part of it is obviously not the best solution, right?

Answer 3

Try different sorting algorithms on the same input data and print the minimum.

Answer 4

I think the appropriate approach is to think hard about what defining properties a minimal "cost" sort has. Then figure out the cost by simulating this ideal sort. The key element here is you don't have to implement a general minimal cost sorting algorithm.

For example, let's say the defining property of a minimal cost sort is that every exchange puts at least one of the exchanged element in it's sorted position (I don't know if this is true). Every exchange based sort would love to be able to have this property, but it's not easy(possible?) in the general case. However You can easily create a program that takes an unsorted array, takes the sorted version (which itself can be generated by an unoptimal algorithm), and then using this information decides the minimum cost to achieve the sorted array from the unsorted array.

Answer 5

What do you mean "brute forcing?" Do you mean "try all possible combinations and select the cheapest?" Just checking.

I think "branch and bound" is what you're looking for - check any source on algorithms. It is "like" brute force, except as you try a sequence of moves, as soon as that sequence of moves is less optimal than any other sequence of moves tried so far, you can abandon the sequence that got you to that point - the cost. This is one flavor of the "backtracking" mentioned above.

My preferred language for doing this would be Prolog but I'm weird.

Simulated Annealing is a PROBABLISTIC algorithm - if the solution space has local minima, then you may be trapped in one and get what you think is the right answer but isn't. There are ways around that and the literature all about that can be found but I don't agree that it's the tool you want.

You could try the related genetic algorithms too if that's the way you want to go.

Answer 6

Description

I think the cheapest way to do this is to swap the cheapest misplaced item with the item that belongs in its spot. I believe this reduces cost by moving the most expensive things just once. If there are n-elements that are out of place, then there will be at most n-1 swaps to put them in place, at a cost of n-1 * cost of least item + cost of all other out of place.

If the globally cheapest element is not misplaced and the spread between this cheapest one and the cheapest misplaced one is great enough, it can be cheaper to swap the cheapest one in its correct place with the cheapest misplaced one. The cost then is n-1 * cheapest + cost of all out of place + cost of cheapest out of place.

Example

For [4,1,2,3], this algorithm exchanges (1,2) to produce:

[4,2,1,3]

and then swaps (3,1) to produce:

[4,2,3,1]

and then swaps (4,1) to produce:

[1,2,3,4]

Notice that each misplaced item in [2,3,4] is moved only once and is swapped with the lowest cost item.

Code

Ooops: "Please don't provide a complete algorithm, just an approach." Removed my code.

Answer 7

In an effort to only get you going on it this may not make complete sense.

Determine all possible moves, and the cost for each move and store those somehow, perform the least expensive move, then determine the moves that can be performed from this variation, storing those with the rest of your stored moves, perform the least expensive etc until the array is sorted.

I love solving things like this.