Learning Common Algorithms with Python

• This lesson covers fundamental algorithms implemented in Python. Understanding these concepts is crucial for building efficient software. We will explore searching, sorting, and recursion.

• Linear Search: This is the simplest search algorithm. It sequentially checks each element of the list until a match is found or the whole list has been searched. Its time complexity is O(n).

def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i  # Return the index of the found element
    return -1 # Return -1 if the element is not found

# Example
my_list = [4, 2, 7, 1, 9, 5]
print(f"Linear Search: Element 7 found at index {linear_search(my_list, 7)}")

• Binary Search: A much more efficient search algorithm, but it requires the list to be sorted first. It works by repeatedly dividing the search interval in half. Its time complexity is O(log n).

def binary_search(sorted_data, target):
    low = 0
    high = len(sorted_data) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if sorted_data[mid] < target:
            low = mid + 1
        elif sorted_data[mid] > target:
            high = mid - 1
        else:
            return mid # Element found
    return -1 # Element not found

# Example
my_sorted_list = [1, 2, 4, 5, 7, 9]
print(f"Binary Search: Element 7 found at index {binary_search(my_sorted_list, 7)}")

• Bubble Sort: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The process is repeated until the list is sorted. Its time complexity is O(n^2).

def bubble_sort(data):
    n = len(data)
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n-i-1):
            if data[j] > data[j+1]:
                # Swap the elements
                data[j], data[j+1] = data[j+1], data[j]
    return data

# Example
my_list_to_sort = [4, 2, 7, 1, 9, 5]
print(f"Bubble Sort: Sorted list is {bubble_sort(my_list_to_sort)}")

• Recursion (Factorial): Recursion is a method where a function calls itself to solve a problem. A classic example is calculating the factorial of a number (n!). It must have a base case to stop the recursion.

def factorial(n):
    # Base case: if n is 1 or 0, factorial is 1
    if n == 0 or n == 1:
        return 1
    # Recursive step: n * factorial of (n-1)
    else:
        return n * factorial(n - 1)

# Example
num = 5
print(f"Recursion: Factorial of {num} is {factorial(num)}")

#Python #Algorithms #DataStructures #Coding #Programming #LearnToCode

━━━━━━━━━━━━━━━
By: @DataScience4 ✨