Skip to content

Instantly share code, notes, and snippets.

@phalbert
Last active April 14, 2019 00:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save phalbert/745d4abbb2976dcfc6521113577a9fd7 to your computer and use it in GitHub Desktop.
Save phalbert/745d4abbb2976dcfc6521113577a9fd7 to your computer and use it in GitHub Desktop.
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.
"""
Question:
Mary can perform the following minimal sequence of swap operations to
successfully sort all 3 items by decreasing popularity rating: [3, 1, 2] → [3, 2, 1].
Solution:
1. The swap always compares the last element in the array with
the least element in the remaining list e.g.
in the case of [3, 1, 2, 4]...we compare 4 with the minimum value in [3,1,2]
and swap the two if the minimum value is less
2. Repeat 1 until the the list is sorted in descending order
3. Do the above while counting the swaps"""
def minimum_swaps(ratings):
if sorted(ratings, reverse=True) == ratings:
return 0
swaps = 1
while sorted(ratings, reverse=True) != sorter(ratings):
swaps += 1
return swaps
def sorter(array):
for i in sorted(range(len(array)), reverse=True):
comp = array[:i]
if len(comp) > 0:
mini = min(comp)
if mini < array[i]:
index = array.index(mini)
array[i], array[index] = array[index], array[i]
return array
return array
import unittest
from minimum_swaps import minimum_swaps
class Test(unittest.TestCase):
def test_cases(self):
self.assertEqual(minimum_swaps([3, 2, 1]), 0)
self.assertEqual(minimum_swaps([3, 1, 2]), 1)
self.assertEqual(minimum_swaps([3, 1, 2, 4]), 2)
if __name__ == '__main__':
unittest.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment