Pages

CodeEval Not So Clever

Implement a silly sorting algorithm that scans an array of integers for the first element out of order, swaps it with its neighbor, and start again from beginning. Given in input a starting sequence and the number of steps we should apply, give back the resulting output.
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