# Find the minimum number of swap operations Mary must perform to order all n items by decreasing popularity rating.?

#1

John is a famous shopkeeper who sells n items in her shop. She assigns each item a unique popularity rating in the inclusive range from 1 to n.

The shop only has one shelf, so the items are displayed array-style in a single row spanning from left to right in a random order. He wants to rearrange the items on the shelf by decreasing popularity rating such that the rating for the i item is always greater than the popularity rating of the (i + 1) item. Mary can swap any two items, i and j, in a single operation.

Specification
minimumSwaps(ratings)

Parameters

ratings: Array<Number> - an array of numbers indicating the popularity rating of each item on the shelf.

Return Value

Number - denotes the minimum number of swap operations Mary must perform to order all `n` items by decreasing popularity rating.

Constraints

`n` = number of items in ratings array

each rating value ( `arri` ) will be unique

`1 â‰¤ n â‰¤ 2 Ă— 105`

`1 â‰¤ arri â‰¤ n`

// Here is my solution to the problem above but it does not pass the tests

``````function minimumSwaps (ratings) {
var swaps = 0;
var n = 1;
for (var i = 1; i < i.length; i++) {
for (var j = i + 1; j < i.length; j++) {
if (ratings[i] == ratings[j]) {
n = n + 1;
} else {
swaps = swaps + 1;
}
}
}
return n;
}

console.log(minimumSwaps([3, 1, 2]));
``````
0 Likes

#2

Anyone with a better solution to the above task as my code here is not passing the tests?

Am using javascript

function minimumSwaps (ratings) {
var swaps = 0;
var n = 1;
for (var i = 1; i < i.length; i++) {
for (var j = i + 1; j < i.length; j++) {
if (ratings[i] == ratings[j]) {
n = n + 1;
} else {
swaps = swaps + 1;
}
}
}
return n;
}

console.log(minimumSwaps([3, 1, 2]));

0 Likes

#3

Well just for starters your outer loop loops one too many times.

Itâ€™s also important to note that the goal as stated is not to minimize your own codeâ€™s complexity; itâ€™s to return the right number.

0 Likes

#4

Hi m_hutley;
It would be great if you can paste a code or improve my code.

0 Likes

#5

Given input of [4,3,2,1], how many swaps do I need to make to order this array?

0 Likes

#6

2 swaps

0 Likes

#7

and when you put it through your code, you get an answer ofâ€¦

0 Likes

#8

1 swap

0 Likes

#9

Well youâ€™ve just told me it requires 2. So obviously, your code hasnâ€™t gotten my example correct.

Time to start debugging, yes?

0 Likes

#10

You donâ€™t actually need to sort the list to find out the minimum number of swaps. In fact, you are almost guaranteed to use a much larger number of swaps than the minimum.

Instead of ordering the list, graph theory is used to find the minimum number of swaps.

This sounds a lot like a job interview question, to test whether you know about such things.

0 Likes

#11

Any suggestion in terms of a code here will be of my help m_hutley
Thanks for your positive response

0 Likes

#12

(Ironically, Paul, you actually do need to sort the listâ€¦ but only insofar as to determine the proper end state to generate a graph from)

0 Likes

#13

Steps:

1. Figure out the different cycles that are involved
2. Calculate the size of each cycle
3. The number of swaps is one less than the size of each cycle.
1 Like

#14

thanks for your positive reply Paul though a code here would sound much easier for me

0 Likes

#15

For example, with [3, 1, 2]

[Edited to account for the reverse order thatâ€™s required by the question]

The 3 is in the right place, which is one cycle with a size of 1. The 1 belongs where the 2 is, and the 2 belongs where the 1 is, so thatâ€™s a second cycle of size 2.

The size of the two cycles is 1 and 2.

The number of swaps is 1. (first with 0, then second with 1).

With a different array, such as [1, 3, 2], the first cycle is 1 to the last position, the 2 in last position to the middle, and the 3 in the middle to the front. Thatâ€™s a cycle of size 3, and one less than those is 3 -1 for a total of 2 swaps.

Thatâ€™s the theory thatâ€™s involved.

0 Likes

#16

Hi Paul, any code suggestion will be much easier for me .
Thanks Paul

// Here is my trial code

``````function minimumSwaps (ratings) {
var swaps = 0;
var n = 1;
for (var i = 1; i < i.length; i++) {
for (var j = i + 1; j < i.length; j++) {
if (ratings[i] == ratings[j]) {
n = n + 1;
} else {
swaps = swaps + 1;
}
}
}
return n;
}

console.log(minimumSwaps([3, 1, 2]));
``````
0 Likes

#17

Sorry mate, but I donâ€™t think that its appropriate for me to craft up code for what looks to be your own job interview.

Other similar code though is found at https://www.includehelp.com/java-programs/minimum-swaps-required-to-sort-an-array.aspx

0 Likes

#18

Okay ! Thanks Paul, i will have a look at that link .

Thanks

0 Likes

#19

Zero swaps are needed, based on the requirements.

``````rearrange the items on the shelf by decreasing popularity rating such that
the rating for the i item is always greater than the popularity rating
of the (i + 1) item
``````
1 Like

#20

Shh Paul, donâ€™t do silly things like actually read the problem

1 Like