sort array of 3 keys while minimizing the total cost

i ve asked the same question 6 months ago but havent really understood how to solve this yet

suppose that we have an array of size n where n <=10 and the keys are 1,2,3

if n = 3 then

Code:

A[] = {2,1,3}

we want to find the min cost in order to sort it in an ascending order

one way would be the following

Code:

2 1 3
2 3 1
1 3 2
1 2 3

with a total cost of 3

another way would be the following

Code:

2 1 3
1 2 3

with a total cost of 1

but if we have a bigger number of n for example n = 5 the problem gets harder

Code:

A[] = {3,2,2,1,3}

etc

i ve tried many sorting algorithms, one that suits the problem is counting sort, but that hasnt helped me at all

can anyone please help me with hints? thanks

use bubble sort and count the sort.

Originally Posted by treenef

use bubble sort and count the sort.

i dont think that would work

im actually thinking of doing something like this

count the number of 1,2,3 in the sequence and then i can know how the sorted array would be

so for example we have

Code:

A[] = {2,1,3,2,2}

the sorted array would be

Code:

K[]
1
2
2
2
3

now having A and the new array K[]

Code:

A[]    K[]
2        1
1        2
3        2
2        2
2        3

its obvious that we need just 2 swaps in order to sort the array

but what if we have something that cant be put in the correct place with just a swap? for example if we have this

Code:

A[]  K[]

2     1
1     1
3     2 
2     2
1     3

we cant swap anything

hence i dont think that method would work for all cases

Try quick sort and count the sorts?

how would you do that? i really think there is a better way of doing this

and i dont think this way is the qsort algorithm, because you cant know if it does a minimum amount of rearrangements in the sequence, or you can?

in my previous reply if i find a way to solve the second problem then i think that would be the solution i will try qsort but i dont think it ll work

Originally Posted by nik2

Code:

A[]  K[]

2     1
1     1
3     2 
2     2
1     3

You've pretty much got it; it just requires two passes. First pass, check for swaps that correctly solve both elements. If you find such a swap, do it. If you don't (such as in the case above), go to the next pass. In the next pass, all you have to do is find a swap that solves one element. It's not as good as a swap that solves both elements, but it's as good as you can do from your current position.

Originally Posted by nik2

one way would be the following

Code:

2 1 3
2 3 1
1 3 2
1 2 3

But what use is starting with swapping two numbers that were already in order? If you don't limit yourself to swaps that make progress then what's to stop you from swapping the same 1 and 3 repeatedly?

now having A and the new array K[]

Code:
A[] K[]
2 1
1 2
3 2
2 2
2 3
its obvious that we need just 2 swaps in order to sort the array

Yes but you can't know that in advance. You cannot look at the situation as an oracle. To work out where each item fits into the sorted ordering requires O(n log n) comparisons in the worst case.

If you want optimal sorting for <= 10 items, simply look up optimal sorting networks. If you want one of the most efficient general purpose algorithms for sorting so few items, then look into bubble sort or insertion sort.

If that doesn't answer everything, what is your actual question, or what are you actually trying to work out?