Recently I found myself revisiting my knowledge of data structures and algorithms. I was also trying to improve my skills in Python, so I decided to give it a try at implementing some sorting algorithms from scratch. Here is how I did it.
Sorting Algorithms
First of all, we need to define what a sorting algorithm is. For me, it is a way to "sort" a set of items (integers, strings, objects...) according to some comparison criteria.
For example, we could sort an array of integers from lowest to highest. In this case, the integers are our set of items, and the "lowest to highest" sentence tells us that the comparison criteria demand that smaller integers should come first once the items are sorted.
Notice that right now we are not making emphasis on what exact algorithm we are going to use to sort the items but on the prerequisites of a sorting algorithm.
Abstract Classes
Now that we have somehow defined what a sorting algorithm is, we can try to express this kind of "behavior" by using a class. Since we don't care at the moment about the specific implementation of the sorting algorithm, we can start by defining its "interface" by using an abstract class.
We can think of abstract classes as a template definition of methods and variables of a class. At least one of the methods of an abstract class also needs to be "abstract", which means that it is not needed to provide a specific implementation.
Abstract classes cannot be instantiated, but they can be subclassed. As a result, subclasses need to implement the "abstract" methods.
Returning to our case of use, an abstract class representing our Sort "interface" could have the following attributes and methods:
The attribute
items
represent the items to be sorted.The attribute
comp_func
represents how to compare two elements in theitems
collection.The
sort
method returns the sorted version of theitems
collection when sorted using thecomp_func
criteria.
This "sort" method is only responsible for returning the sorted items, but it does not care about the "how". To handle this, we need to add an extra method:
- A
_sort
method. We will not implement this abstract method in the abstract class but in the subclasses. This way we can have a "Bubble Sort" implementation as well as a "Merge Sort" implementation. We can have any sorting method that we want!
A possible implementation using Python would be like this:
"""Module with the base implementation of a Sort class."""
from abc import ABC, abstractmethod
class Sort(ABC):
"""Base class for sorting."""
def __init__ (self, func, items):
self._comp_func = func
self._items = items
def sort(self):
"""Returns the sorted version of the elements contained
in the `_items` property.
Returns:
List: The sorted elements.
"""
return self._sort(self._items)
@abstractmethod
def _sort(self, items):
pass
Inheritance
Now is the time when we need to care about what specific sorting algorithm we are going to use. Let's see how we can make use of inheritance to implement two of the classic sorting algorithms out there: "Bubble Sort" and "Merge Sort".
For the "Bubble Sort" algorithm, a simple implementation would look something like this:
"""Module with the implementation of the BubbleSort algorithm."""
from .sort import Sort
class BubbleSort(Sort):
"""Class that represents a BubbleSort implementation."""
def _sort(self, items):
size = len(items)
swapped = True
while swapped:
swapped = False
for i in range(1, size):
if not self._comp_func(items[i - 1], items[i]):
items[i - 1], items[i] = items[i], items[i - 1]
swapped = True
size -= 1
return items
Things to notice here:
We are creating the "BubbleSort" class as a subclass of the "Sort" class.
We don't need to redefine the
__init__
andsort
methods. These are inherited from the "Sort" class.We redefine the
_sort
method to make a classicO(n^2)
implementation of the "Bubble Sort" algorithm.We are making use of the
_comp_func
attribute set in the__init__
method of the "Sort" class.
For the "Merge Sort" implementation we can do the following:
"""Module with the implementation of the MergeSort algorithm."""
from .sort import Sort
class MergeSort(Sort):
"""Class that represents a MergeSort implementation."""
def _sort(self, items):
if len(items) <= 1:
return items
left = items[0 : len(items) // 2]
right = items[len(items) // 2 : len(items)]
left = self._sort(left)
right = self._sort(right)
sorted_items = self._merge(left, right)
return sorted_items
def _merge(self, left, right):
merged = []
left_idx = 0
right_idx = 0
while left_idx < len(left) and right_idx < len(right):
if self._comp_func(left[left_idx], right[right_idx]):
merged.append(left[left_idx])
left_idx += 1
else:
merged.append(right[right_idx])
right_idx += 1
while left_idx < len(left):
merged.append(left[left_idx])
left_idx += 1
while right_idx < len(right):
merged.append(right[right_idx])
right_idx += 1
return merged
Things to notice here:
Same elements as above. The only difference is that in this case the running time of the algorithm is
O(n log n)
.We are implementing a
_merge
method even if it is not enforced by the "Sort" class. This is ok, we need to implement the "abstract" methods but that doesn't mean we cannot create new methods.
Following this pattern, we can create more sorting algorithm implementations such as "Heap Sort" and "Insertion Sort".
Next Steps
I will be looking into creating unit tests for these implementations in the future. Maybe by taking advantage of Object-Oriented Programming and some concepts such as parametrization it is possible to create reliable and maintainable tests.
If you would like to take a closer look at these implementations you can do it here:
If you want to take a look at the current status of the unit tests I'm creating you can do it here:
Unit tests for Sorting Implementations
Also, if you want to contribute to this open-source project to learn about Data Structures, Algorithms, and Python, you can check it out here:
Data Structures and Algorithms in Python
We are waiting for your contributions. Any help will be appreciated.
👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.
🧡 If you liked this article, consider sharing it.
Top comments (0)