Basically, in Computer Science, when you're sorting something you want to do it as fast as possible, however this is assuming that "swapping" to items doesn't matter. Now, the challenge of this assignment is\was to make a sorting algorithm with the smallest cost possible. In this case, the cost is simple to find. Just add the values of the two items swapped together and voila! So, when you sort, you've got to add the costs up, and your goal is to sort it with the lowest cost possible.

EXAMPLE:

8 1 2 4 (cost for swapping goes here)

1 8 2 4 (9)

1 2 8 4 (10)

1 2 4 8 (12)

Total cost: 31

Now, how would you go about sorting something in the least cost possible? In the given case, let's set it as established that the minimum is 17, alright? How would you do that? Well...

8 1 2 4

8 2 1 4 (3)

8 2 4 1 (5)

1 2 4 8 (9)

Total cost: 17

Okay, so you can see that it was done, but what does it mean? Well, notice that the method was actually pretty simple...find the smallest, find what should be in the place it is, and swap them! This is the core idea behind my solution, although it isn't complete. Let me show:

1 8 9 7 6

Well, now what do we do? The smallest is already in place, right? Well, maybe if we switch the smallest one with the smallest one that's out of place (in this case, the 6) and proceed as normal...

1 8 9 7 6

6 8 9 7 1 (7)

6 8 1 7 9 (10)

6 8 7 1 9 (8)

6 1 7 8 9 (9)

1 6 7 8 9 (7)

Total cost: 31

In this case, 31 is the smallest, so this looks like the solution to our problem, right? But wait! What if I had the same ordering that the previous one did, but I used smaller numbers?

1 4 5 3 2

2 4 5 3 1 (3)

2 4 1 3 5 (6)

2 4 3 1 5 (4)

2 1 3 4 5 (5)

1 2 3 4 5 (3)

Total cost: 21

But, what if I told you that this is not the minimum...that the minimum is actually 18? Well then, there's obviously another case to consider. In fact, the minimum for that one is actually done by using the smallest element that's out of place. What does this mean? Well, if you think about it, how are using the two different? Obviously, all the other elements don't matter since they'll be swapped anyways, so maybe there's a way to mathematically determine which one would be more efficient to use? Well, i found there is a way to roughly determine, however it's possible it could fail...hehehe.

Notice how if you use the 2 (the smallest out of place in the above example) then what will happen is the 2 will be swapped with 3 elements. Well, there are 4 elements out of place, so the expected cost for using the 2 would be...

2 * (4 - 1) = 6

or rather...

(smallest piece out of order) * (unsorted elements - 1) = cost #1

something similar would happen if we switched the 1 with the 2, though. First, we observer that the 1 would be swapped with those same 3 elements, but it will be swapped with the smallest out-of-order one twice! So, the cost for doing that would actually be the sum of those two...

(1 + 2) * 2 + 1 * (4 - 1) = 6 + 3 = 9

or rather...

(smallest + smallest out of order) * 2 + (smallest) * (unsorted elements - 1) = cost #2

Well, now it's a simple matter of choosing the smaller of the two!

So, pretty much this narrows down most cases. There might still exist cases that slip by this method, though. There's one that can slip by if programmed oddly. Take this example:

2 5 3 3 4

Well, notice that there are two 3s. Also notice that one of them is already in place. It'd be very easy to accidently move around that one that's already in place, but that'd be silly to do! It'll result in unneccessary moves! Basically, the way I got around that is that I calculate in advanced where everything is supposed to go and I make sure that the specific 3 is identified as "in place." Then, instead of looking for the smallest out-of-order item by the value in the spot, i can search based upon the previously calculated index! It works.

Alrighty, now I'm done. I hope this psyche poke wasn't too painful.