CODEWITHSUNDEEP
c++algorithm
altair1000
altair1000

Reputation: 59

Permutation cost

I am given a permutation of the set {1,2,...,n}. I have to sort this permutation only by swapping numbers situated on succesive positions with a minimum total cost. The cost of swapping the elements x,y, situated on succesive position is min(x,y).

For example if I have the permutation 3,1,2,4 the total minimum cost is 3. Because I do these steps ( (x,y) means swapping x with y):

Total cost is 3.

I tried brute force, by swapping the minimum cost unsorted pair, until there are no unsorted pairs, but this method is obviously not fast enough.

My question is, how do I find the minimum cost of sorting given my conditions?

Upvotes: 1

Views: 1007

Answers (2)

Aligus
Aligus

Reputation: 1605

This algoritm sounds like insertion sort. Insertion sort based on eliminating inversions in the permutation. And you task is to eliminate inversions as in insertion sort. As you've already known sorted array hasn't any inversions.

The time complexity of insertion sort algorithm is O(n+d), where n is the number of elements and d - is the number of inversions.

The maximum number of inversions in permutation is n*(n-1)/2, and the minimum is 0.

You can use modificated merge sort to find number of inversions in array in O(n*lg n).

Upvotes: 1

konjac
konjac

Reputation: 787

The number of succesive-number swaps to sort a sequence is equal to the number of pairs in reversed order.

For example

6 1 3 2 4 5

Pairs in reversed order are listed below:

(6,1) (6,3) (6,2) (6,4) (6,5) (3,2)

so

the operations to sort the sequence are:

swap(6,1) 1 6 3 2 4 5
swap(6,3) 1 3 6 2 4 5
swap(6,2) 1 3 2 6 4 5
swap(6,4) 1 3 2 4 6 5
swap(6,5) 1 3 2 4 5 6
swap(3,2) 1 2 3 4 5 6

So the operation is determinate(unless you do some useless operations).

You only need to count all pairs (x,y) in reversed order, and sum up min(x,y).

Upvotes: 5

Related Questions