Skip to main content

One post tagged with "Binary Search"

View All Tags

Top 10 Programming Algorithms Every Programmer Should Know

· 7 min read
Career Credentials
Where Education meets Ambition

Algorithms form the backbone of programming, enabling computers to solve problems efficiently. Whether you're a seasoned developer or just starting your coding journey, mastering fundamental algorithms is crucial. In this blog post, we'll explore the top 10 programming algorithms that every programmer should know, accompanied by insightful explanations and optimized example code.

Binary search efficiently locates an element in a sorted array by repeatedly dividing the search interval in half. It's a go-to choice for searching in large datasets.

Python Example Code:

# Binary Search Implementation
def binary_search(array, target):
    low = 0
    high = len(array) - 1

    while low <= high:
        mid = (low + high) // 2

        if array[mid] == target:
            return mid
        elif array[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Example usage:
array = [1, 3, 5, 7, 9]
target = 5
index = binary_search(array, target)

Enroll Now: Analysis of Algorithm by Dr. Amar Panchal course for a comprehensive understanding of algorithmic efficiency.

2. Breadth-First Search (BFS):

BFS traverses a graph level by level, making it ideal for scenarios like finding the shortest path between nodes or detecting cycles.

Python Example Code:

# Breadth-First Search Implementation
def bfs(graph, start_node):
    queue = []
    visited = set()

    queue.append(start_node)

    while queue:
        node = queue.pop(0)

        if node not in visited:
            visited.add(node)

            for neighbor in graph[node]:
                queue.append(neighbor)

# Example usage:
graph = {
    0: [1, 2],
    1: [3, 4],
    2: [5, 6],
    3: [],
    4: [],
    5: [],
    6: []
}

start_node = 0
bfs(graph, start_node)

3. Depth-First Search (DFS):

DFS explores as far as possible along each branch before backtracking. It's useful for pathfinding and identifying connected components.

Python Example Code:

# Depth-First Search Implementation
def dfs(graph, start_node):
    stack = []
    visited = set()

    stack.append(start_node)

    while stack:
        node = stack.pop()

        if node not in visited:
            visited.add(node)

            for neighbor in graph[node]:
                stack.append(neighbor)

# Example usage:
graph = {
    0: [1, 2],
    1: [3, 4],
    2: [5, 6],
    3: [],
    4: [],
    5: [],
    6: []
}

start_node = 0
dfs(graph, start_node)

Check Out: 53 SQL TCS Interview QnA by Career Credentials for FREE !!

4. Merge Sort:

Merge sort divides the array into halves, sorts them recursively, and then merges them. It's efficient and stable.

Python Example Code:

# Merge Sort Implementation
def merge_sort(array):
    if len(array) <= 1:
        return array

    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])

    return merge(left, right)

5. Quicksort:

Quicksort partitions the array around a pivot element, making it faster than many other sorting algorithms.

Python Example Code:

# Quicksort Implementation
def quicksort(array):
    if len(array) <= 1:
        return array

    pivot = array[0]
    less = [x for x in array[1:] if x < pivot]
    greater = [x for x in array[1:] if x >= pivot]

    return quicksort(less) + [pivot] + quicksort(greater)

# Example usage:
array = [5, 3, 2, 1, 4]
sorted_array = quicksort(array)

6. Heapsort:

Heapsort builds a heap from the array and repeatedly extracts the maximum element, making it efficient and in-place.

Python Example Code:

# Heapsort Implementation
def heapsort(array):
    # Helper functions
    def build_max_heap(array):
        for i in range(len(array) // 2, -1, -1):
            max_heapify(array, i)

    def max_heapify(array, i):
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i

        if left < len(array) and array[left] > array[largest]:
            largest = left
        if right < len(array) and array[right] > array[largest]:
            largest = right

        if largest != i:
            array[i], array[largest] = array[largest], array[i]
            max_heapify(array, largest)

    build_max_heap(array)

    for i in range(len(array) - 1, 0, -1):
        array[i], array[0] = array[0], array[i]
        max_heapify(array, 0)

# Example usage:
array = [5, 3, 2, 1, 4]
heapsort(array)

Check Out: Microsoft Interview Preperation Questions by Career Credentials for FREE !!

7. Radix Sort:

Radix sort sorts integers by comparing digits, making it fast but not stable.

Python Example Code:

# Radix Sort Implementation
def radix_sort(array):
    # Helper function
    def counting_sort(array, digit):
        # Implementation omitted for brevity

    max_element = max(array)
    max_digits = len(str(max_element))

    for digit in range(max_digits - 1, -1, -1):
        array = counting_sort(array, digit)

# Example usage:
array = [5, 3, 2, 1, 4]
radix_sort(array)

A* search efficiently finds the shortest path in a graph using a heuristic function.

Python Example Code:

class Node:
    def __init__(self, state, parent, cost, heuristic):
        self.state = state
        self.parent = parent
        self.cost = cost
        self.heuristic = heuristic

def a_star_search(graph, start_node, goal_node, heuristic):
    open_list = [Node(start_node, None, 0, heuristic(start_node, goal_node))]
    closed_list = set()

    while open_list:
        current_node = min(open_list, key=lambda node: node.cost + node.heuristic)

        if current_node.state == goal_node:
            return current_node

        open_list.remove(current_node)
        closed_list.add(current_node.state)

        for neighbor in graph[current_node.state]:
            if neighbor not in closed_list:
                new_cost = current_node.cost + 1
                new_heuristic = heuristic(neighbor, goal_node)

                new_node = Node(neighbor, current_node, new_cost, new_heuristic)

                if neighbor in open_list:
                    if new_cost < open_list[neighbor].cost:
                        open_list[neighbor] = new_node
                else:
                    open_list.append(new_node)

    return None

# Example usage:
graph = {
    0: [1, 2],
    1: [3, 4],
    2: [5, 6],
    3: [],
    4: [],
    5: [],
    6: []
}

start_node = 0
goal_node = 6

def heuristic(node, goal_node):
    return abs(node - goal_node)

path = a_star_search(graph, start_node, goal_node, heuristic)

if path is not None:
    print("The shortest path is:", path.state)
else:
    print("There is no path to the goal node")


Enroll Now: App Building using Python by Dr. Amar Panchal and Start Building Your Own Cool Stuff !

9. Dijkstra’s Algorithm:

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a graph.

Python Example Code:

def dijkstra(graph, start_node):
    distances = {}
    visited = set()

    distances[start_node] = 0

    while distances:
        current_node = min(distances, key=distances.get)

        visited.add(current_node)

        for neighbor in graph[current_node]:
            if neighbor not in visited:
                new_distance = distances[current_node] + 1

                if neighbor not in distances or new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance

    return distances

# Example usage:
graph = {
    0: [1, 2],
    1: [3, 4],
    2: [5, 6],
    3: [],
    4: [],
    5: [],
    6: []
}

start_node = 0

distances = dijkstra(graph, start_node)

print("The shortest distances from the start node are:", distances)

10. Bellman-Ford Algorithm:

Bellman-Ford algorithm finds the shortest path from a source node to all other nodes in a graph with negative edge weights.

Python Example Code:

def bellman_ford(graph, start_node):
    distances = {}
    predecessors = {}

    for node in graph:
        distances[node] = float('inf')
        predecessors[node] = None

    distances[start_node] = 0

    for i in range(len(graph) - 1):
        for node in graph:
            for neighbor in graph[node]:
                new_distance = distances[node] + graph[node][neighbor]

                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    predecessors[neighbor] = node

    # Check for negative cycles
    for node in graph:
        for neighbor in graph[node]:
            new_distance = distances[node] + graph[node][neighbor]

            if new_distance < distances[neighbor]:
                return False

    return distances, predecessors

# Example usage:
graph = {
    0: {(1, 1), (2, 5)},
    1: {(2, 3)},
    2: {(3, 1)}
}

start_node = 0

distances, predecessors = bellman_ford(graph, start_node)

print("The shortest distances from the start node are:", distances)
print("The shortest paths from the start node are:", predecessors)


Must Read: TCS NQT 2024 – Exam Pattern, Syllabus & Preparation Guide


In conclusion, mastering these top 10 programming algorithms equips you with powerful problem-solving tools essential for any programmer. Whether you're optimizing performance or tackling complex graph problems, understanding these algorithms will elevate your coding skills to new heights. Keep exploring, learning, and applying these principles in your projects to become a more proficient programmer. Happy coding!