Cell bubble sort

January 4, 2026

A first pass at doing something with the code at https://github.com/Zhangtaining/cell_research/, specifically its Cell.py module.

This is related to the note at Simple algorithms.

The Cell/CellTissue structure used in the code is an example of a doubly-linked list. Each node (Cell) has pointers in both directions (prev and next).

from typing import Sequence, Union
import random

random.seed(1)


class Cell:
    def __init__(self, value: float):
        self.value: float = value
        self.prev: Cell | None = None
        self.next: Cell | None = None

    def should_swap_next(self) -> bool:
        if not self.next:
            return False
        return self.value > self.next.value

    def swap_with_next(self) -> bool:
        if not self.next:
            return False

        # Cell to be swapped with
        next_to_self = self.next

        # outer neighbors: Cells whose prev or next is affected by the swap
        next_to_next = next_to_self.next
        prev_to_self = self.prev

        # update prev/next of outer neighbors
        if prev_to_self:
            prev_to_self.next = next_to_self
        if next_to_next:
            next_to_next.prev = self

        # update next
        next_to_self.prev = prev_to_self
        next_to_self.next = self

        # update self
        self.prev = next_to_self
        self.next = next_to_next

        return True


class CellTissue:
    def __init__(self, values: Sequence[Union[int, float]]):
        cells: list[Cell] = [Cell(val) for val in values]

        for i in range(len(cells)):
            if i > 0:
                cells[i].prev = cells[i - 1]
            if i < len(cells) - 1:
                cells[i].next = cells[i + 1]

        self.head = cells[0]
        self.size = len(cells)

    def get_cell_at(self, index: int) -> Cell | None:
        """Return the cell at a given distance from the linked-list's head."""

        current = self.head
        for _ in range(index):
            if not current:
                return None
            current = current.next

        return current

    def to_list(self) -> Sequence[Union[int, float]]:
        """Convert the linked-list to a list of values."""

        result = []
        current = self.head
        while current:
            result.append(current.value)
            current = current.next

        return result

    def sort_step(self) -> bool:
        """Execute one pass of bubble sort."""
        swapped = False
        current = self.head

        while current and current.next:
            if current.should_swap_next():
                if current == self.head:
                    self.head = current.next
                current.swap_with_next()
                swapped = True
                # don't update current here, current.next has been updated to
                # point to the next node in swap_with_next()
            else:
                current = current.next  # didn't swap, so update current.next

        return swapped

    def sort(self, max_iterations: int | None = None, verbose: bool = False) -> int:
        if not max_iterations:
            max_iterations = self.size**2  # upper bounds for bubble sort
        iterations = 0

        for i in range(max_iterations):
            if not self.sort_step():
                iterations = i
                if verbose:
                    print(f"Final: {self.to_list()}")
                    print(f"Sorted in {iterations} iterations")
                    break

            if verbose:
                print(f"Step {i}: {self.to_list()}")

            iterations = i + 1
        else:  # Python for/else (executed if for loop never hits the break statement)
            if verbose:
                print(f"Reached max iterations ({max_iterations})")
        return iterations


def demo():
    values = [10, 9, 8, 7]
    print(f"Initial values: {values}")
    # values = [random.randint(1, 100) for _ in range(12)]
    tissue = CellTissue(values)
    tissue.sort(verbose=True)


if __name__ == "__main__":
    demo()

Confirming that Cell swapping works as expected

The swapping code is the kind of thing I get confused by. (Edit: I found and fixed a bug by manually stepping through the code.) Let’s say we’ve got a CellTissue linked list instance that can be represented by the nodes:

a (head, value=3) -> b (value=1) <-> c (value=12) <- d (value=9)

The link list’s head is a.

When sort_step is called on the CellTissue instance from the CellTissue.sort() method:

current will be set to a
the while current and current.next block will be entered:
- current.should_swap_next() will return True
- current == self.head, so self.head is updated to current.next
- current.swap_with_next() is called:
  - next_to_self is set to b
  - next_to_next is set to b.next (c)
  - prev_to_self is set to self.prev, (a.prev which is None)
  - the if prev_to_self block isn’t executed
  - the if next_to_next block sets next_to_next.prev to self (a)
  - next_to_self.prev is set to prev_to_self (None)
  - next_to_self.next is set to self (a)
  - self.prev is set to next_to_self (b)
  - self.next is set to next_to_next (c)
- current is not updated to current.next (That’s the bug I found. If current = current.next is called after current.swap_with_next() the algorithm will skip over what’s actually the next node in the linked list. It still works, but takes more iterations in some cases.)

The current cell (a) has now been swapped with the next cell (b):

b (head, value=1) -> a (value=3) <-> c (value=12) <- d (value=9)

The current cell/node is still a, but a.prev is now b instead of None, and a.next is now c instead of b. This means we’re still in the while current and current.next block:

current.should_swap_with_next() is called for a:
- a.value is 3; a.next.value (c.value) is 12, so False is returned and the else block is executed
- current is updated to current.next (c) in the else block
current.should_swap_with_next() is called for c and returns True:
- current_swap_with_next() is called:
  - next_to_self is set to d
  - next_to_next is set to None
  - prev_to_self is set to a
  - the if prev_to_self block is executed and sets a.next to d
  - the if next_to_next block isn’t executed
  - next_to_self.prev (d.prev) is set to a
  - next_to_self.next (d.next) is set to c
  - self.prev is set to d
  - self.next is set to None
- current is not updated, it is still c

b (head, value=1) -> a (value=3) <-> d (value=9) <- c (value=12)

current.next (c.next) is now None, so the while current and current.next block is exited.

The CellTissue.sort for i in range(max_iterations) block is then executed for the second time. It’s if not self.sort_step() condition will evaluate to False and we’ll break out of the loop.

Tags: