Top 10 Python Algorithms with Time Complexity ✔

1 year ago 23.1k views

Discover the top 10 Python algorithms every programmer should know, including Binary Search, Merge Sort, Quick Sort, and more. Explore each algorithm's time complexity and gain insights into their applications and implementations in Python. Whether you're preparing for technical interviews or seeking to deepen your understanding of algorithms, this comprehensive guide will equip you with essential knowledge and insights.

Top 10 Python Algorithms with Time Complexity

Python is a popular programming language used for various purposes such as web development, data analysis, artificial intelligence, and more. It offers a wide range of libraries and frameworks that make it easy to implement various algorithms. However, the efficiency of an algorithm is crucial, and it is measured using time complexity. In this article, we will explore the top 10 Python algorithms with their time complexity.

1. Bubble Sort

Bubble sort is a simple sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. The algorithm continues to iterate through the list until no more swaps are needed, indicating that the list is sorted.

Time Complexity: O(n^2)

Example Code:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        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

2. Selection Sort

Selection sort is another simple sorting algorithm that works by selecting the smallest element from the unsorted portion of the list and moving it to the sorted portion.

Time Complexity: O(n^2)

Example Code:

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

3. Insertion Sort

Insertion sort is a simple sorting algorithm that works by dividing the list into a sorted and an unsorted region. Each element from the unsorted region is inserted into the sorted region in its correct position.

Time Complexity: O(n^2)

Example Code:

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

4. Merge Sort

Merge sort is a divide-and-conquer algorithm that works by dividing the list into smaller sublists, sorting each sublist, and then merging the sorted sublists into a single sorted list.

Time Complexity: O(n log n)

Example Code:

def merge_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    mid = n // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right) 
                      
def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

5. Quick Sort

Quick sort is another divide-and-conquer algorithm that works by selecting a pivot element, partitioning the list around the pivot, and recursively sorting the sublists.

Time Complexity: O(n log n) on average, O(n^2) in the worst case

Example Code:

def quick_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

6. Binary Search

Binary search is a searching algorithm that works by finding the middle element of the list and comparing it with the target value. If the target value is less than the middle element, the search continues in the left half of the list, otherwise in the right half.

Time Complexity: O(log n)

Example Code:

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

7. Depth-First Search (DFS)

Depth-First Search is a graph traversal algorithm that works by exploring as far as possible along each branch before backtracking. It uses a stack to keep track of the nodes to visit.

Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges

Example Code:

def dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

8. Breadth-First Search (BFS)

Breadth-First Search is a graph traversal algorithm that works by exploring all the nodes at the current level before moving to the next level. It uses a queue to keep track of the nodes to visit.

Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges

Example Code:

def bfs(graph, start):
    visited = set()
    queue = [start]
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
    return visited

9. Dijkstra's Algorithm

Dijkstra's algorithm is a shortest path algorithm that works by maintaining a priority queue of nodes to visit, where the priority is the distance from the start node.

Time Complexity: O(n log n + m), where n is the number of nodes and m is the number of edges

Example Code:

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]
    while queue:
        distance, node = heapq.heappop(queue)
        for neighbor in graph[node]:
            alt_distance = distance + graph[node][neighbor]
            if alt_distance < distances[neighbor]:
                distances[neighbor] = alt_distance
                heapq.heappush(queue, (alt_distance, neighbor))
    return distances

10. Topological Sort

Topological sort is an algorithm that orders the nodes of a directed acyclic graph (DAG) such that for every edge (u, v), node u comes before node v in the ordering.

Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges

Example Code:

def topological_sort(graph):
    visited = set()
    ordering = []
    def visit(node):
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                visit(neighbor)
            ordering.append(node)
    for node in graph:
        visit(node)
    return ordering