Bubble Sort

Time: O(n²) Space: O(1)

Repeatedly steps through the list, compares adjacent elements and swaps them if they're in the wrong order. Simple but inefficient for large datasets.

bubble_sort.py
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Sorting Algorithms

Bubble Sort

O(n2)

Repeatedly steps through the list, compares adjacent elements and swaps them if they're in the wrong order.

Insertion Sort

O(n2)

Builds the sorted array one item at a time by inserting each element into its correct position.

Selection Sort

O(n2)

Repeatedly finds the minimum element from the unsorted portion and places it at the beginning.

Merge Sort

O(n log n)

Divides the array into halves, recursively sorts them, and merges the sorted halves back together.

Quick Sort

O(n log n)

Selects a pivot element and partitions the array around it, recursively sorting the partitions.

Heap Sort

O(n log n)

Builds a max heap from the array, then repeatedly extracts the maximum element to build the sorted result.

Counting Sort

O(n + k)

A non-comparison sort that counts occurrences of each element and uses arithmetic to determine positions.

Maze Generation

Recursive Backtracking

O(V)

Uses depth-first search with backtracking to carve passages. Creates long, winding corridors with few dead ends. The classic maze generation algorithm.

Prim's Algorithm

O(V log V)

Starts from a random cell and grows the maze by adding random frontier cells. Creates mazes with more branching and shorter dead ends than DFS.

Kruskal's Algorithm

O(E α(V))

Uses Union-Find to randomly connect cells while avoiding cycles. Creates mazes with uniform passage lengths and even branching throughout.

Pathfinding Algorithms

Depth-First Search

O(V + E)

Explores as deep as possible before backtracking. Fast but doesn't guarantee the shortest path. Performance depends heavily on maze structure.

Breadth-First Search

O(V + E)

Explores all neighbors at current depth before moving deeper. Always finds the shortest path in unweighted graphs. Expands uniformly in all directions.

Dijkstra's Algorithm

O((V+E) log V)

Uses a priority queue to always expand the lowest-cost path. Guarantees shortest path in weighted graphs. In uniform mazes, behaves like BFS.

A* Search

O((V+E) log V)

Combines path cost with a heuristic (Manhattan distance) to guide search toward the goal. Often explores fewer cells than BFS while finding optimal paths.