# Sorting algorithms with Python project

I wrote my first project in Python and I would like to know if this is correct. I prepared some guidelines I want to ask. (I know that I don't have any documentation yet). In the future I want to extend my project about new algorithms such as search, crypto, machine learning, hashes, graphs and so on. Also, I would like to add some data structures. For easier review I can share my files if needed.

1. Is my code compatible with PEP8?
2. Is my code compatible with ZenOfPython?
3. Is my code compatible with OOP?
4. Is my code easy to expand? (Extended with new algorithms and classes)
6. Are my subclasses easy to build for testcases?
7. Are my unit tests correct (don't really know what I should ask about)?
8. Should I use some design patterns in such a project?

initiate.py

from dsal.algorithm_list import algorithms

class Initiate:
def __init__(self, algorithm_name, **kwargs):
self.algorithm_name = algorithm_name
self.result = {}
self.args = kwargs

@staticmethod
def get_algorithm(name):
algorithm = None
for key, alg in algorithms.items():
if name in key:
algorithm = alg
break
if algorithm is None:
raise TypeError('Algorithm not defined !')
return algorithm

def set_params(self, name):
algorithm, params = Initiate.get_algorithm(name), dict()
for k, v in algorithm.check_params(self).items():
val = self.args.get(k, None)
if val is not None and v(val):
params[k] = val

return algorithm(**params)

def run(self):
algorithm = self.set_params(self.algorithm_name)
return algorithm.run()

def run_time(self):
algorithm = self.set_params(self.algorithm_name)


algorithm_list.py

from dsal.algorithms.sorting.simple_sort.bubble_sort import bubble_sort

algorithms = {"BubbleSortV1": bubble_sort.BubbleSortV1,
"BubbleSortV2": bubble_sort.BubbleSortV2}


allgorithms\sorting\simple_sort\bubble_sort\bubble_sort.py

from dsal.core.algorithms.sorting.simple_sort import SimpleSort

class BubbleSortV1(SimpleSort):

# setting up variables
length = len(self.container)
changed = True
while changed:
changed = False
for i in range(length - 1):
if self.container[i] > self.container[i + 1]:
self.container[i], self.container[i + 1] = self.container[i + 1], self.container[i]
changed = True
length -= 1
return self.container

class BubbleSortV2(SimpleSort):

# setting up variables
length = len(self.container)

while length >= 1:
changed_times = 0
for i in range(1, length):
if self.container[i - 1] > self.container[i]:
self.container[i - 1], self.container[i] = self.container[i], self.container[i - 1]
changed_times = i
length = changed_times
return self.container


core\algorithms\algorithm.py

import time

class Algorithm:
def __init__(self, **kwargs):
self.set_params(**kwargs)

def set_params(self, **kwargs):
pass

def check_params(self, **kwargs):
pass

return None

t1 = time.time()
t2 = time.time()
return (t2 - t1) * 1000

def run(self):


core\algorithms\simple_sort\simple_sort.py

from dsal.core.algorithms.algorithm import Algorithm

class SimpleSort(Algorithm):

def set_params(self, **kwargs):
self.container = kwargs["container"]

def check_params(self):
return {
'container': lambda x: isinstance(x, list)
}

return None


tests\run_tests.py

import unittest

if __name__ == '__main__':
for test in testsuite:
unittest.TextTestRunner(verbosity=3).run(test)


tests\algorithms\test.py

from unittest import TestCase

from dsal.core.algorithms.algorithm import Algorithm

class AlgorithmBaseTestCase(TestCase):
def setUp(self):
self.algorithm = Algorithm()

def test_run(self):
self.assertEqual(self.algorithm.run(), None)

def test_set_params(self):
self.assertEqual(self.algorithm.set_params(), None)
self.assertEqual(self.algorithm.set_params(container=[1, 2, 3, 4]), None)

def test_check_params(self):
self.assertEqual(self.algorithm.set_params(), None)
self.assertEqual(self.algorithm.set_params(container=[1, 2, 3, 4]), None)

class AlgorithmTestCase(TestCase):

def algorithm_run_test(self, algorithm):
return algorithm.run()


tests\algorithm\sorting\test.py

from tests.algorithms.test import AlgorithmTestCase

class SortTestCase(AlgorithmTestCase):

def setUp(self):
super(AlgorithmTestCase, self).setUp()

def _test_sort_single_func(self, input_list, **kwargs):
expected_list = sorted(input_list)
result = AlgorithmTestCase.algorithm_run_test(self, self.function_name(**kwargs))
self.assertEqual(result, expected_list)


tests\algorithms\sorting\simple_sort\tests.py

from dsal.algorithms.sorting.simple_sort.bubble_sort.bubble_sort import BubbleSortV1
from tests.algorithms.sorting.test import SortTestCase

class SimpleSortTestCase(SortTestCase):

def setUp(self):
self.function_name = BubbleSortV1
super(SortTestCase, self).setUp()

def test_sort_empty_list(self):
input_list = []
self._test_sort_single_func(input_list, container = sorted(input_list))

def test_sort_one_element(self):
input_list = [0]
self.container = input_list
self._test_sort_single_func(input_list, container = sorted(input_list))

def test_sort_same_numbers(self):
input_list = [1, 1, 1, 1]
self.container = input_list
self._test_sort_single_func(input_list, container = sorted(input_list))

input_list = [1, 2, 3, 4]
self.container = input_list
self._test_sort_single_func(input_list, container = sorted(input_list))

def test_sort_reversed(self):
input_list = [4, 3, 2, 1]
self.container = input_list
self._test_sort_single_func(input_list, container = sorted(input_list))

def test_sort_disorder_with_repetitions(self):
input_list = [3, 5, 3, 2, 4, 2, 1, 1]
self.container = input_list
self._test_sort_single_func(input_list, container = sorted(input_list))


tests\algorithms\sorting\simple_sort\bubble_sort

from dsal.algorithms.sorting.simple_sort.bubble_sort.bubble_sort import BubbleSortV1, BubbleSortV2
from tests.algorithms.sorting.simple_sort.test import SimpleSortTestCase

class BubbleSortV1TestCase(SimpleSortTestCase):

def test_bubble_sort_v1(self):
self.function_name = BubbleSortV1
super(SimpleSortTestCase, self).setUp()

class BubbleSortV2TestCase(SimpleSortTestCase):

def test_bubble_sort_v2(self):
self.function_name = BubbleSortV2
super(SimpleSortTestCase, self).setUp()


### 1. Stop writing frameworks!

This code seems very "enterprisey" to me — by which I mean that there is a big framework of classes that don't do anything except add complexity. If you come from a Java background you might be used to writing this kind of framework, but the sheer volume of code is a maintenance burden that you should not take on unless you are sure that the returns will justify the costs.

In Python, we can nearly always avoid this kind of framework, or at least postpone writing it until it becomes worthwhile.

Let's take the elements of the framework in turn:

1. Initiate is a class which provides the features: (i) looking up an algorithm by name; (ii) running an algorithm; (iii) timing how long an algorithm takes. Instead of (i) you could use globals; instead of (ii) you could just call the function; and instead of (iii) you could use the timeit module. But the code doesn't use the Initiate class anywhere, so you could delete it.

2. Algorithm is a class which provides the features: (i) calling a function with some keyword arguments; (ii) timing how long the function takes. Instead of (i) you could just call the function, and instead of (ii) you could use the timeit module. So you could delete this class and use functions instead.

3. algorithm_list.py provides a table mapping algorithm name to algorithm class. But this is only needed by Initiate.get_algorithm, and that isn't used anywhere, so you could delete this file. In Python, if you really need to look up a function by name, you can use the globals built-in. But this is rarely necessary.

4. SimpleSort is a subclass of Algorithm providing specialized features for sorting algorithms. This class isn't needed (for the same reasons that Algorithm isn't needed) and you could delete this class.

5. BubbleSortV1 and BubbleSortV2 are subclasses of SimpleSort that implement the bubble sort algorithm. These classes aren't needed (for the same reasons that Algorithm isn't needed). All you need to keep is the sort function.

6. AlgorithmBaseTestCase is a class of unit tests for the Algorithm class. But if you deleted the Algorithm class, then you wouldn't need to test it, and so you could delete AlgorithmBaseTestCase too.

7. SortTestCase checks that an algorithm sorts a sequence correctly. This is fine!

8. SimpleSortTestCase provides tests of a sorting algorithm on various input lists. This is fine, except that the tests are very repetitive. It would be better to refactor the code so that it is table driven. See the test_cases method below for how to do this.

9. run_tests.py runs unittest test discovery. But you can do this using the unittest command-line interface without having to write any code: python -m unittest discover -s algorithms. So you could delete this file.

1. The argument to the sorting algorithms needs to be a sequence (so that you can index it), not any old container. So sequence would be a better name.

2. The sorting algorithms are destructive — they modify the input sequence, like the list.sort method. In Python it is conventional for destructive functions and methods to return None. This makes it harder to accidentally confuse them with non-destructive equivalents like sorted, which return a fresh result but leave the original data unchanged.

3. The tests are not very thorough. This is a case where you have a test oracle in the form of the built-in function sorted, making this suitable for random testing. See the test_random method below.

### 3. Revised code

def bubble_sort_v1(seq):
length = len(seq)
changed = True
while changed:
changed = False
for i in range(length - 1):
if seq[i] > seq[i + 1]:
seq[i], seq[i + 1] = seq[i + 1], seq[i]
changed = True
length -= 1

def bubble_sort_v2(seq):
length = len(seq)
while length >= 1:
changed_times = 0
for i in range(1, length):
if seq[i - 1] > seq[i]:
seq[i - 1], seq[i] = seq[i], seq[i - 1]
changed_times = i
length = changed_times

import random
from unittest import TestCase

class TestSort:
def check(self, seq):
expected = sorted(seq)
found = list(seq) # take a copy since self.function is destructive
self.function(found)
self.assertEqual(expected, found)

CASES = [
(), # empty
(0,), # one element
(1, 1, 1, 1), # same numbers
(1, 2, 3, 4), # already sorted
(4, 3, 2, 1), # reversed
(3, 5, 3, 2, 4, 2, 1, 1), # disorder with repetitions
]

def test_cases(self):
for case in self.CASES:
self.check(case)

def test_random(self):
for k in range(100):
self.check(random.choices(range(k), k=k))

class TestBubbleSortV1(TestSort, TestCase):
function = staticmethod(bubble_sort_v1)

class TestBubbleSortV2(TestSort, TestCase):
function = staticmethod(bubble_sort_v2)


Notes

1. The reason that TestSort does not inherit from unittest.TestCase is so that it is not run by unittest test discovery: it won't work because it doesn't have a function attribute.

2. The reason for using staticmethod is that we need self.function to be a plain function, not an instance method.

3. I made the test cases tuples so that they can't be modified by accident. TestSort.check makes a copy in the form of a list so that it can be modified by the function under test.

• Ok, so i have one more question probably. When i will add let's say 10 sorting algorithms, 10 searching algorithms, hashes, graphs, data structures and so on i should stay with one file with functions and one file with tests ? – user186999 Dec 14 '18 at 19:26
• You can organize the files in whatever way is most convenient. It's easy to move stuff around, so start with a small number of files and then add more as you need them. You don't have to plan everything in advance. – Gareth Rees Dec 14 '18 at 23:29
• So, in my own case, I should take a position from general to specific? Not from general to specific. Should not i at first plan 'classes', functions and so on and then start writing them? – user186999 Dec 15 '18 at 1:15
• From specific to general, you mean? If so, that's what I would recommend. By trying to plan a big framework of abstractions in advance, you give up one of the key advantages of software, namely that it's soft (cheap to modify). Better to start with concrete stuff you need right away, and then add abstractions when you are sure you'll benefit from them. – Gareth Rees Dec 15 '18 at 8:36
    algorithm = None
for key, alg in algorithms.items():
if name in key:
algorithm = alg
break
if algorithm is None:
raise TypeError('Algorithm not defined !')
return algorithm


A few things, here. First of all, are you sure you want to be doing substring searching through the keys of a dictionary? Shouldn't you just do regular key lookup on algorithm name?

Don't name your key "key". If it's an algorithm name, call it "alg_name" or something.

Also, you can simplify your return logic. Something like:

try:
return algorithms[name]
except KeyError:
raise TypeError('Algorithm not defined !')


For this line:

val = self.args.get(k, None)


None is the default anyway, so you can simply write val = self.args.get(k).

For this:

for k, v in algorithm.check_params(self).items():


Apparently v is callable, but you wouldn't know by looking at it. Give it a meaningful name. validate?

if val is not None and v(val):


My best guess is that this runs validation on the parameter, and if the validation fails, the parameter is silently dropped. This is bad. You want to know if your validation fails, and probably abort execution of the algorithm.

This path:

allgorithms\sorting\simple_sort\bubble_sort\bubble_sort.py


has a typo in it. It's "algorithms", not "allgorithms" (unless you intended a portmanteau of "all algorithms").

def time_task(self):
t1 = time.time()

This is fragile. Consider calling timeit instead.
• allgorithms\sorting\simple_sort\bubble_sort\bubble_sort.py this is a typo. I edited the time_task function so function contains only return timeit.timeit(stmt="self.run_task()",globals={'self' : self}). Fallowing your advices i changed the searching function for algorithm. Yes its simpler now. Let's talk about if val is not None and v(val): if the **kwargs don't contains the keyword and value it's returning an error. As you can see in simple_sort.py. – user186999 Dec 14 '18 at 16:52
• Even if kwargs missing an arg returns an error from the algorithm itself, that's not good enough - you should fail earlier, as soon as validation fails. That's the whole purpose of validation. – Reinderien Dec 14 '18 at 16:58