Abstract Classes, Inheritance, and Sorting Algorithms in Python

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 the items collection.

• The sort method returns the sorted version of the items collection when sorted using the comp_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__ and sort methods. These are inherited from the "Sort" class.

• We redefine the _sort method to make a classic O(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:

Sorting Implementations

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.

🔗 All links | Twitter | LinkedIn