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