This is CodeEval problem #232, and here I giving a Python 3 solution to it.
The given samples, here converted in python test cases, give a better idea of what we should implement:
def test_provided_1(self):
    self.assertEqual('3 4 2 1', solution('4 3 2 1 | 1'))
def test_provided_2(self):
    self.assertEqual('4 3 5 2 1', solution('5 4 3 2 1 | 2'))
Once split the input line to get a list of int, data, and the number of iterations to be applyed to them, steps, the code to write is pretty strighforward:
for i in range(steps):
    for j in range(1, len(data)):
        if data[j] < data[j-1]:
            data[j-1], data[j] = data[j], data[j-1]
            break
return ' '.join(str(c) for c in data)
The internal for loop represents the sorting implementation. Notice how the full scan of the list is performed each time. When is detected an element out of order, a swap is performed, in a very pythonic way, and the next iteration starts.The full sort takes Big-Oh n squared time, however CodeEval can't complain about this solution, and gives full marks to it. I pushed test cases and python script to GitHub.
 
No comments:
Post a Comment