4
\$\begingroup\$

I am quite new in Python and I am starting my journey with sorting algorithms, PEP8 and the Zen of Python. So far i wrote a post BubbleSort and I drew conclusions and followed the advices. I implemented two methods with optimatization from Wikipedia. I would ask for information about the current code, tests and directories.

  1. Is it possible to write tests more succinctly?
  2. Should i make a docummentation with tests? ( or the specific name of the function is enough )
  3. Is the code compatible with PEP8 and Zen of Python?
  4. Is the code compatible with Python-style coding?
  5. What should i change to avoid future problems with my code?
  6. Should i add more options to functions for example: reverse, default options, exceptions? ( or its unnecessary in algorithms )
  7. Should i add comparator? Should it be a class then? Can you give some advice?
  8. Is my directory layout correct?
  9. If you found something else in the text, try to give me this information.

My directory looks like:

Python:.
│
├───algorithms
│   └───sorting
│           bubble_sort.py
│           __init__.py
│
└───tests
    └───algorithms
        └───sorting
                bubble_sort_test.py
                __init__.py

bubble_sort.py

import copy


def bubble_sort_v_one(container: object) -> object:
    """
        Bubble sort with first optimization.

        Description
        ----------
        From wikipedia: inner loop can avoid looking
        at the last (length − 1) items when running for the n-th time.
        Performance cases:
        Worst      : O(n^2)
        Average    : O(n^2)
        Best case  : O(n)

        Parameters
        ----------
        container : Mutable container with comparable objects and structure
                         which has implemented __len__, __getitem__ and __setitem__.

        Returns
        -------
        container : Sorted container

        Examples
        ----------
        >>> bubble_sort_v_one([7,1,2,6,4,2,3])
        [1, 2, 2, 3, 4, 6, 7]

        >>> bubble_sort_v_one(['a', 'c', 'b'])
        ['a', 'b', 'c']

    """

    # setting up variables
    container = copy.copy(container)
    length = len(container)
    changed = True

    while changed:
        changed = False
        for i in range(length - 1):
            if container[i] > container[i + 1]:
                container[i], container[i + 1] = container[i + 1], container[i]
                changed = True
        length -= 1
    return container


def bubble_sort_v_two(container: object) -> object:
    """
        Bubble sort with second optimization.

        Description
        ----------
        From wikipedia: This allows us to skip over a lot of the elements,
        resulting in about a worst case 50% improvement in comparison count.
        Performance cases:
        Worst      : O(n^2) - 50%
        Average    : O(n^2)
        Best case  : O(n)

        Parameters
        ----------
        container : Mutable container with comparable objects and structure
                         which has implemented __len__, __getitem__ and __setitem__.

        Returns
        -------
        container : Sorted container

        Examples
        ----------
        >>> bubble_sort_v_two([7,1,2,6,4,2,3])
        [1, 2, 2, 3, 4, 6, 7]

        >>> bubble_sort_v_two(['a', 'c', 'b'])
        ['a', 'b', 'c']

    """

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

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

bubble_sort_test.py

import unittest

from Algorithms.Sorting.bubble_sort import bubble_sort_v_one as bubble_one
from Algorithms.Sorting.bubble_sort import bubble_sort_v_two as bubble_two


class TestBubbleSortVOneAlgorithm(unittest.TestCase):

    def test_bubble_sort_with_positive_numbers(self):
        self.assertEqual(bubble_one([5, 5, 7, 8, 2, 4, 1]),
                         [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_negative_numbers_only(self):
        self.assertEqual(bubble_one([-1, -3, -5, -7, -9, -5]),
                         [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        self.assertEqual(bubble_one([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1]),
                         [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_same_numbers(self):
        self.assertEqual(bubble_one([1, 1, 1, 1]), [1, 1, 1, 1])

    def test_bubble_sort_empty_list(self):
        self.assertEqual(bubble_one([]), [])

class TestBubbleSortVTwoAlgorithm(unittest.TestCase):

    def test_bubble_sort_with_positive_numbers(self):
        self.assertEqual(bubble_two([5, 5, 7, 8, 2, 4, 1]),
                         [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_negative_numbers_only(self):
        self.assertEqual(bubble_two([-1, -3, -5, -7, -9, -5]),
                         [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        self.assertEqual(bubble_two([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1]),
                         [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_same_numbers(self):
        self.assertEqual(bubble_two([1, 1, 1, 1]), [1, 1, 1, 1])

    def test_bubble_sort_empty_list(self):
        self.assertEqual(bubble_two([]), [])


if __name__ == '__main__':
    unittest.main()

Should i add bubble_sort function so user can choose which version want to run easier?

def bubble_sort(container: object, version : int = 1) -> object:
    if version == 1:
        bubble_sort_v_one(container)
    elif version == 2:
        bubble_sort_v_two(container)
    else:
        raise ValueError

What do you think about comparator and editing the function head to:

def comparator(a: object, b: object) -> object:
    return a - b


def bubble_sort_v_one(container: object, comparator=comparator) -> object:

and for sure the line for comparating the 2 variables should like like that:

if comparator(container[i] , container[i + 1]) > 0:

Of course, the questions are not only about this code. I would like to know if this methodology in the future will help me write correct and clean code and will increase its functionality.

So my bubble_sort.py will look like:

import copy


def comparator(a, b):
    return a - b


def bubble_sort(container, version: int = 1, cmp=comparator):
    if version == 1:
        return bubble_sort_v_one(container, cmp)
    elif version == 2:
        return bubble_sort_v_two(container, cmp)
    else:
        raise ValueError


def bubble_sort_v_one(container, cmp):
    """
        Bubble sort with first optimization.

        Description
        ----------
        From wikipedia : inner loop can avoid looking
        at the last (length − 1) items when running for the n-th time.
        Performance cases:
        Worst      : O(n^2)
        Average    : O(n^2)
        Best       : O(n)

        Parameters
        ----------
        container : Mutable container with comparable objects and structure
                         which has implemented __len__, __getitem__ and __setitem__.
        cmp : Comparator default a - b > 0

        Returns
        -------
        container : New sorted container,

        Examples
        ----------
        >>> bubble_sort_v_one([7,1,2,6,4,2,3])
        [1, 2, 2, 3, 4, 6, 7]

        >>> bubble_sort_v_one(['a', 'c', 'b'])
        ['a', 'b', 'c']

    """

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


def bubble_sort_v_two(container, cmp):
    """
        Bubble sort with second optimization.

        Description
        ----------
        From wikipedia: This allows us to skip over a lot of the elements,
        resulting in about a worst case 50% improvement in comparison count.
        Performance cases:
        Worst      : O(n^2) - 50%
        Average    : O(n^2)
        Best       : O(n)

        Parameters
        ----------
        container : Mutable container with comparable objects and structure
                         which has implemented __len__, __getitem__ and __setitem__.
        cmp : Comparator default a - b > 0

        Returns
        -------
        container : New sorted container,

        Examples
        ----------
        >>> bubble_sort_v_two([7,1,2,6,4,2,3])
        [1, 2, 2, 3, 4, 6, 7]

        >>> bubble_sort_v_two(['a', 'c', 'b'])
        ['a', 'b', 'c']

    """

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

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

and bubble_sort_test.py

import unittest

from Algorithms.Sorting.bubble_sort import bubble_sort


class TestBubbleSortVOneAlgorithm(unittest.TestCase):

    def test_bubble_sort_with_positive_numbers(self):
        self.assertEqual(bubble_sort([5, 5, 7, 8, 2, 4, 1]),
                         [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_negative_numbers_only(self):
        self.assertEqual(bubble_sort([-1, -3, -5, -7, -9, -5]),
                         [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        self.assertEqual(bubble_sort([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1]),
                         [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_with_positive_numbers_reverse(self):
        self.assertEqual(bubble_sort([5, 5, 7, 8, 2, 4, 1],
                                     cmp=lambda x, y: y - x),
                         [8, 7, 5, 5, 4, 2, 1])

    def test_bubble_sort_negative_numbers_only_reverse(self):
        self.assertEqual(bubble_sort([-1, -3, -5, -7, -9, -5],
                                     cmp=lambda x, y: y - x),
                         [-1, -3, -5, -5, -7, -9])

    def test_bubble_sort_with_negative_and_positive_numbers_reverse(self):
        self.assertEqual(bubble_sort([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1],
                                     cmp=lambda x, y: y - x),
                         [8, 7, 5, 5, 4, 2, 1, 0, -4, -5, -6])

    def test_bubble_sort_same_numbers(self):
        self.assertEqual(bubble_sort([1, 1, 1, 1]), [1, 1, 1, 1])

    def test_bubble_sort_empty_list(self):
        self.assertEqual(bubble_sort([]), [])


class TestBubbleSortVTwoAlgorithm(unittest.TestCase):

    def test_bubble_sort_with_positive_numbers(self):
        self.assertEqual(bubble_sort([5, 5, 7, 8, 2, 4, 1], version=2),
                         [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_negative_numbers_only(self):
        self.assertEqual(bubble_sort([-1, -3, -5, -7, -9, -5], version=2),
                         [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        self.assertEqual(bubble_sort([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1], version=2),
                         [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_with_positive_numbers_reverse(self):
        self.assertEqual(bubble_sort([5, 5, 7, 8, 2, 4, 1], version=2,
                                     cmp=lambda x, y: y - x),
                         [8, 7, 5, 5, 4, 2, 1])

    def test_bubble_sort_negative_numbers_only_reverse(self):
        self.assertEqual(bubble_sort([-1, -3, -5, -7, -9, -5], version=2,
                                     cmp=lambda x, y: y - x),
                         [-1, -3, -5, -5, -7, -9])

    def test_bubble_sort_with_negative_and_positive_numbers_reverse(self):
        self.assertEqual(bubble_sort([-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1],
                                     version=2, cmp=lambda x, y: y - x),
                         [8, 7, 5, 5, 4, 2, 1, 0, -4, -5, -6])

    def test_bubble_sort_same_numbers(self):
        self.assertEqual(bubble_sort([1, 1, 1, 1], version=2), [1, 1, 1, 1])

    def test_bubble_sort_empty_list(self):
        self.assertEqual(bubble_sort([], version=2), [])


if __name__ == '__main__':
    unittest.main()

Which one is better and why? Of course I will accept all the imperfections on the chest.

\$\endgroup\$
0
\$\begingroup\$

Various things with no precise order:

Function names

Numbers are accepted in identifier such as function names. Instead of having my_func_v_one, you could go for my_func_v1.

Less verbose tests

These comments are to be taken with a pinch of salt: some prefer their unit test to be as simple as possible, some prefer to consider them as code and apply the usual principles such as Don't repeat yourself.

In order to make the tests more concise and easier to write, you could consider adding an helper method.

Also, you could have a single class like this:

class TestBubbleSortAlgorithm(unittest.TestCase):

    def _test_sort(self, sorting_func, input_list, expected_list):
        self.assertEqual(sorting_func(input_list), expected_list)

    def test_bubble_sort_v1_with_positive_numbers(self):
        self._test_sort(bubble_sort_v1, [5, 5, 7, 8, 2, 4, 1], [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_v1_negative_numbers_only(self):
        self._test_sort(bubble_sort_v1, [-1, -3, -5, -7, -9, -5], [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_v1_with_negative_and_positive_numbers(self):
        self._test_sort(bubble_sort_v1, [-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1], [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_v1_same_numbers(self):
        self._test_sort(bubble_sort_v1, [1, 1, 1, 1], [1, 1, 1, 1])

    def test_bubble_sort_v1_empty_list(self):
        self._test_sort(bubble_sort_v1, [], [])

    def test_bubble_sort_v2_with_positive_numbers(self):
        self._test_sort(bubble_sort_v2, [5, 5, 7, 8, 2, 4, 1], [1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_v2_negative_numbers_only(self):
        self._test_sort(bubble_sort_v2, [-1, -3, -5, -7, -9, -5], [-9, -7, -5, -5, -3, -1])

    def test_bubble_sort_v2_with_negative_and_positive_numbers(self):
        self._test_sort(bubble_sort_v2, [-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1], [-6, -5, -4, 0, 1, 2, 4, 5, 5, 7, 8])

    def test_bubble_sort_v2_same_numbers(self):
        self._test_sort(bubble_sort_v2, [1, 1, 1, 1], [1, 1, 1, 1])

    def test_bubble_sort_v2_empty_list(self):
        self._test_sort(bubble_sort_v2, [], [])

Then you can use the fact that we have a sorting function we can trust to use it as a Test Oracle.

Then you can write something like:

class TestBubbleSortAlgorithm(unittest.TestCase):

    def _test_sort(self, sorting_func, input_list):
        expected_list = sorted(input_list)
        self.assertEqual(sorting_func(input_list), expected_list)

    def test_bubble_sort_with_positive_numbers(self):
        input_list = [5, 5, 7, 8, 2, 4, 1]
        self._test_sort(bubble_sort_v1, input_list)
        self._test_sort(bubble_sort_v2, input_list)

    def test_bubble_sort_negative_numbers_only(self):
        input_list = [-1, -3, -5, -7, -9, -5]
        self._test_sort(bubble_sort_v1, input_list)
        self._test_sort(bubble_sort_v2, input_list)

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        input_list = [-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1]
        self._test_sort(bubble_sort_v1, input_list)
        self._test_sort(bubble_sort_v2, input_list)

    def test_bubble_sort_same_numbers(self):
        input_list = [1, 1, 1, 1]
        self._test_sort(bubble_sort_v1, input_list)
        self._test_sort(bubble_sort_v2, input_list)

    def test_bubble_sort_empty_list(self):
        input_list = []
        self._test_sort(bubble_sort_v1, input_list)
        self._test_sort(bubble_sort_v2, input_list)

Or even:

class TestBubbleSortAlgorithm(unittest.TestCase):

    def _test_sort_single_func(self, sorting_func, input_list):
        expected_list = sorted(input_list)
        self.assertEqual(sorting_func(input_list), expected_list)

    def _test_sort_all_funcs(self, input_list):
        self._test_sort_single_func(bubble_sort_v1, input_list)
        self._test_sort_single_func(bubble_sort_v2, input_list)

    def test_bubble_sort_with_positive_numbers(self):
        input_list = [5, 5, 7, 8, 2, 4, 1]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_negative_numbers_only(self):
        input_list = [-1, -3, -5, -7, -9, -5]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_with_negative_and_positive_numbers(self):
        input_list = [-6, -5, -4, 0, 5, 5, 7, 8, 2, 4, 1]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_same_numbers(self):
        input_list = [1, 1, 1, 1]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_empty_list(self):
        input_list = []
        self._test_sort_all_funcs(input_list)

Also, as for the tests themselves, I wouldn't base my tests on type of numbers you have (positive, negative, etc) other criteria. For instance, I'd write the following tests:

class TestBubbleSortAlgorithm(unittest.TestCase):

    def _test_sort_single_func(self, sorting_func, input_list):
        expected_list = sorted(input_list)
        self.assertEqual(sorting_func(input_list), expected_list)

    def _test_sort_all_funcs(self, input_list):
        self._test_sort_single_func(bubble_sort_v1, input_list)
        self._test_sort_single_func(bubble_sort_v2, input_list)

    def test_bubble_sort_empty_list(self):
        input_list = []
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_one_element(self):
        input_list = [0]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_same_numbers(self):
        input_list = [1, 1, 1, 1]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_already_sorted(self):
        input_list = [1, 2, 3, 4]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_reversed(self):
        input_list = [4, 3, 2, 1]
        self._test_sort_all_funcs(input_list)

    def test_bubble_sort_disorder_with_repetitions(self):
        input_list = [3, 5, 3, 2, 4, 2, 1, 1]
        self._test_sort_all_funcs(input_list)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.