**Course Title:** Modern Python Programming: Best Practices and Trends **Section Title:** Data Structures and Basic Algorithms **Topic:** Basic algorithms: Sorting, searching, and common patterns. **Introduction** In this topic, we will explore the fundamental algorithms that are essential for any programmer to know. We will cover sorting, searching, and common patterns, along with their implementation in Python. Understanding these concepts will help you write efficient and effective code, and prepare you for more advanced topics in programming. **Sorting Algorithms** Sorting is a fundamental operation in computer science, and Python provides several built-in sorting algorithms. Here, we will cover three common sorting algorithms: Bubble Sort, Selection Sort, and Insertion Sort. ### Bubble Sort Bubble sort is a simple sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. ```python 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 # Example arr = [64, 34, 25, 12, 22, 11, 90] print(bubble_sort(arr)) # Output: [11, 12, 22, 25, 34, 64, 90] ``` However, Bubble Sort is not suitable for large data sets as its time complexity is of Ο(n^2). ### Selection Sort Selection sort is a sorting algorithm that works by selecting the smallest element from the unsorted portion of the array and swapping it with the first element of the unsorted portion. ```python 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 # Example arr = [64, 34, 25, 12, 22, 11, 90] print(selection_sort(arr)) # Output: [11, 12, 22, 25, 34, 64, 90] ``` Like Bubble Sort, Selection Sort is not efficient for large data sets as its time complexity is also Ο(n^2). ### Insertion Sort Insertion sort is a sorting algorithm that works by dividing the input into a sorted and an unsorted region. Each subsequent element from the unsorted region is inserted into the sorted region in its correct position. ```python def insertion_sort(arr): n = len(arr) for i in range(1, n): key = arr[i] j = i-1 while j >= 0 and arr[j] > key: arr[j+1] = arr[j] j -= 1 arr[j+1] = key return arr # Example arr = [64, 34, 25, 12, 22, 11, 90] print(insertion_sort(arr)) # Output: [11, 12, 22, 25, 34, 64, 90] ``` Insertion Sort has a time complexity of Ο(n^2), but it is more efficient than Bubble Sort and Selection Sort. **Python Built-in Sorting Algorithms** Python provides two built-in sorting algorithms: `sorted()` and `list.sort()`. * `sorted()`: Returns a new sorted list from the elements of any sequence. * `list.sort()`: Sorts the list in-place and returns `None`. ```python # sorted() arr = [64, 34, 25, 12, 22, 11, 90] print(sorted(arr)) # Output: [11, 12, 22, 25, 34, 64, 90] # list.sort() arr = [64, 34, 25, 12, 22, 11, 90] arr.sort() print(arr) # Output: [11, 12, 22, 25, 34, 64, 90] ``` **Searching Algorithms** Searching is a fundamental operation in computer science, and Python provides several built-in searching algorithms. Here, we will cover two common searching algorithms: Linear Search and Binary Search. ### Linear Search Linear search is a simple searching algorithm that works by iterating through the list until the target element is found. ```python def linear_search(arr, target): for i, element in enumerate(arr): if element == target: return i return -1 # Example arr = [11, 12, 22, 25, 34, 64, 90] target = 25 print(linear_search(arr, target)) # Output: 3 ``` However, Linear Search is not efficient for large data sets as its time complexity is Ο(n). ### Binary Search Binary search is a fast searching algorithm that works by dividing the list in half and searching for the target element in one of the two halves. ```python def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # Example arr = [11, 12, 22, 25, 34, 64, 90] target = 25 print(binary_search(arr, target)) # Output: 3 ``` Binary Search has a time complexity of Ο(log n), making it more efficient than Linear Search for large data sets. **Common Patterns** Here are some common patterns that you should be aware of when working with algorithms: * **Divide and Conquer**: Breaking down a problem into smaller sub-problems and solving each sub-problem recursively. * **Dynamic Programming**: Breaking down a problem into smaller sub-problems, solving each sub-problem only once, and storing the results to avoid redundant computation. **Conclusion** In this topic, we covered the basic algorithms for sorting and searching, including Bubble Sort, Selection Sort, Insertion Sort, Linear Search, and Binary Search. We also discussed the Python built-in sorting algorithms and common patterns used in algorithms. Understanding these concepts is essential for any programmer, and will help you write efficient and effective code. **External Resources** * [GeeksforGeeks - Sorting Algorithms](https://www.geeksforgeeks.org/sorting-algorithms/) * [GeeksforGeeks - Searching Algorithms](https://www.geeksforgeeks.org/searching-algorithms/) * [Wikipedia - Sorting Algorithm](https://en.wikipedia.org/wiki/Sorting_algorithm) * [Wikipedia - Searching Algorithm](https://en.wikipedia.org/wiki/Searching_algorithm) **What's Next?** In the next topic, we will cover functions in Python, including defining and using functions, function arguments, return values, and scope. **Leave a Comment or Ask for Help** If you have any questions or need help with any of the topics covered in this section, please leave a comment below.

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

# Example
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))  # Output: [11, 12, 22, 25, 34, 64, 90]

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

# Example
arr = [64, 34, 25, 12, 22, 11, 90]
print(selection_sort(arr))  # Output: [11, 12, 22, 25, 34, 64, 90]

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

# Example
arr = [64, 34, 25, 12, 22, 11, 90]
print(insertion_sort(arr))  # Output: [11, 12, 22, 25, 34, 64, 90]

# sorted()
arr = [64, 34, 25, 12, 22, 11, 90]
print(sorted(arr))  # Output: [11, 12, 22, 25, 34, 64, 90]

# list.sort()
arr = [64, 34, 25, 12, 22, 11, 90]
arr.sort()
print(arr)  # Output: [11, 12, 22, 25, 34, 64, 90]

def linear_search(arr, target):
    for i, element in enumerate(arr):
        if element == target:
            return i
    return -1

# Example
arr = [11, 12, 22, 25, 34, 64, 90]
target = 25
print(linear_search(arr, target))  # Output: 3

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

# Example
arr = [11, 12, 22, 25, 34, 64, 90]
target = 25
print(binary_search(arr, target))  # Output: 3