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.
- Is it possible to write tests more succinctly?
- Should i make a docummentation with tests? ( or the specific name of the function is enough )
- Is the code compatible with PEP8 and Zen of Python?
- Is the code compatible with Python-style coding?
- What should i change to avoid future problems with my code?
- Should i add more options to functions for example: reverse, default options, exceptions? ( or its unnecessary in algorithms )
- Should i add comparator? Should it be a class then? Can you give some advice?
- Is my directory layout correct?
- 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.
