Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sort array in ascending order while minimizing "cost"

Tags:

algorithm

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.

like image 895
dacman Avatar asked Jul 24 '09 15:07

dacman


People also ask

How do you sort an array in ascending order?

Example: Sort an Array in Java in Ascending Order Then, you should use the Arrays. sort() method to sort it. That's how you can sort an array in Java in ascending order using the Arrays. sort() method.

What is the most efficient way of sorting an array?

Quicksort. Quicksort is generally thought of as the most efficient 'general' sorting algorithm, where nothing is known about the inputs to the array, and it's more efficient than insertion sort on large lists.

How do you sort an array by smallest to largest?

Selection sort performs the following steps to sort an array from smallest to largest: Starting at array index 0, search the entire array to find the smallest value. Swap the smallest value found in the array with the value at index 0. Repeat steps 1 & 2 starting from the next index.

What is the minimum number of operations required to sort the array in ascending order?

Therefore, the minimum moves required is 2.


2 Answers

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.

like image 106
jqno Avatar answered Oct 19 '22 23:10

jqno


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.

like image 24
user143506 Avatar answered Oct 19 '22 23:10

user143506