1. Bubble Sort --------------------- def bubble_sort(data): size = len(data) # Determine the size of the input array for iteration in range(size): # Traverse through all elements for position in range(0, size-iteration-1): # From start to the last unsorted element if data[position] > data[position+1]: # If current element is greater than the next data[position], data[position+1] = data[position+1], data[position] # Swap elements return data # Return the sorted array numbers = [64, 34, 25, 12, 22, 11, 90] print(bubble_sort(numbers)) Algorithm Explanation: Bubble sort is a straightforward sorting technique that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Each pass through the list places the next largest element in its correct position at the end of the unsorted portion. ### 2. Selection Sort def selection_sort(items): for current_index in range(len(items)): # Traverse through all array elements min_index = current_index # Assume current position has the minimum value for comparison_index in range(current_index+1, len(items)): # Check remaining elements if items[comparison_index] < items[min_index]: # If a smaller element is found min_index = comparison_index # Update the minimum element's index items[current_index], items[min_index] = items[min_index], items[current_index] # Swap the found minimum element with the current element return items # Return the sorted array data_set = [64, 25, 12, 22, 11] print(selection_sort(data_set)) Algorithm Explanation: Selection sort divides the input list into a sorted and an unsorted region. It repeatedly selects the smallest element from the unsorted region and moves it to the end of the sorted region. This process continues until the entire list is sorted. ### 3. Insertion Sort def insertion_sort(collection): for i in range(1, len(collection)): # Start from the second element key = collection[i] # Current element to be positioned j = i-1 # Start comparing with the previous element while j >= 0 and key < collection[j]: # Shift elements greater than key to the right collection[j + 1] = collection[j] # Move element one position ahead j -= 1 # Move to the previous element collection[j + 1] = key # Place the key in its correct position return collection # Return the sorted array values = [12, 11, 13, 5, 6] print(insertion_sort(values)) Algorithm Explanation: Insertion sort builds the final sorted array one item at a time. It takes each element from the input and inserts it into its correct position in the already sorted portion of the array. This process is efficient for small datasets and partially sorted arrays. ### 4. Merge Sort def merge_sort(input_list): if len(input_list) > 1: # If the list has more than one element mid = len(input_list) // 2 # Find the midpoint of the list left_half = input_list[:mid] # Divide the list into left half right_half = input_list[mid:] # Divide the list into right half merge_sort(left_half) # Recursively sort the left half merge_sort(right_half) # Recursively sort the right half left_index = right_index = main_index = 0 # Initialize pointers for merging # Merge the sorted halves back into the original list while left_index < len(left_half) and right_index < len(right_half): if left_half[left_index] < right_half[right_index]: input_list[main_index] = left_half[left_index] left_index += 1 else: input_list[main_index] = right_half[right_index] right_index += 1 main_index += 1 # Copy any remaining elements from the left half while left_index < len(left_half): input_list[main_index] = left_half[left_index] left_index += 1 main_index += 1 # Copy any remaining elements from the right half while right_index < len(right_half): input_list[main_index] = right_half[right_index] right_index += 1 main_index += 1 return input_list # Return the sorted list arr = [12, 11, 13, 5, 6, 7] print(merge_sort(arr)) Algorithm Explanation: Merge sort follows the divide-and-conquer approach. It splits the array into two halves, recursively sorts each half, and then merges the sorted halves back together. This process continues until subarrays of size 1 are reached, which are inherently sorted. ### 5. Quick Sort def quick_sort(array): if len(array) <= 1: # Base case: arrays with 0 or 1 element are already sorted return array else: pivot = array[len(array) // 2] # Choose middle element as pivot less_than_pivot = [x for x in array if x < pivot] # Elements smaller than pivot equal_to_pivot = [x for x in array if x == pivot] # Elements equal to pivot greater_than_pivot = [x for x in array if x > pivot] # Elements greater than pivot return quick_sort(less_than_pivot) + equal_to_pivot + quick_sort(greater_than_pivot) # Combine sorted subarrays data = [3, 6, 8, 10, 1, 2, 1] print(quick_sort(data)) Algorithm Explanation: Quick sort operates by selecting a 'pivot' element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. ### 6. Binary Search def binary_search(target_list, value): low = 0 # Initialize the lower bound high = len(target_list) - 1 # Initialize the upper bound while low <= high: # Continue until the bounds cross mid = low + (high - low) // 2 # Calculate the middle index if target_list[mid] == value: # If the middle element is the target return mid # Return the position of the target elif target_list[mid] < value: # If the middle element is less than the target low = mid + 1 # Adjust the lower bound else: # If the middle element is greater than the target high = mid - 1 # Adjust the upper bound return -1 # Return -1 if the target is not found list_of_numbers = [2, 3, 4, 10, 40] search_value = 10 print(binary_search(list_of_numbers, search_value)) Algorithm Explanation: Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one. ### 7. Fibonacci Sequence def fibonacci_sequence(length): if length <= 0: # Handle non-positive length return [] elif length == 1: # Handle single element case return [0] elif length == 2: # Handle two elements case return [0, 1] # Initialize the sequence with the first two numbers sequence = [0, 1] for i in range(2, length): # Generate subsequent numbers next_number = sequence[i-1] + sequence[i-2] # Each number is the sum of the previous two sequence.append(next_number) # Add the new number to the sequence return sequence # Return the generated sequence sequence_length = 10 print(fibonacci_sequence(sequence_length)) Algorithm Explanation: The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. This implementation generates the sequence iteratively, which is efficient and avoids the potential stack overflow issues of a recursive approach. ### 8. Euclidean Algorithm for GCD def greatest_common_divisor(num1, num2): while num2 != 0: # Continue until the second number becomes 0 num1, num2 = num2, num1 % num2 # Replace first number with second, and second with remainder return num1 # The first number is now the GCD a = 60 b = 48 print(greatest_common_divisor(a, b)) Algorithm Explanation: The Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD) of two numbers. It is based on the principle that the GCD of two numbers also divides their difference. ### 9. Depth-First Search (DFS) def depth_first_search(graph, start_node, visited=None): if visited is None: # Initialize visited set if not provided visited = set() visited.add(start_node) # Mark the current node as visited print(start_node) # Process the current node # Recursively visit all unvisited neighbors for neighbor in graph[start_node] - visited: depth_first_search(graph, neighbor, visited) return visited # Return the set of visited nodes adjacency_list = { 'A': {'B', 'C'}, 'B': {'A', 'D', 'E'}, 'C': {'A', 'F'}, 'D': {'B'}, 'E': {'B', 'F'}, 'F': {'C', 'E'} } depth_first_search(adjacency_list, 'A') Algorithm Explanation: Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking. It's useful for solving problems like maze puzzles and detecting cycles in graphs. ### 10. Breadth-First Search (BFS) from collections import deque def breadth_first_search(graph, start_node): visited = set() # Keep track of visited nodes queue = deque([start_node]) # Initialize queue with start node visited.add(start_node) # Mark start node as visited while queue: # Continue until queue is empty current_node = queue.popleft() # Dequeue the next node print(current_node) # Process the current node # Enqueue all unvisited neighbors for neighbor in graph[current_node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return visited # Return the set of visited nodes graph = { 'A': {'B', 'C'}, 'B': {'A', 'D', 'E'}, 'C': {'A', 'F'}, 'D': {'B'}, 'E': {'B', 'F'}, 'F': {'C', 'E'} } breadth_first_search(graph, 'A') Algorithm Explanation: Breadth-first search is another algorithm for traversing or searching tree or graph data structures. It starts at the root node and explores all neighbor nodes at the present depth before moving on to nodes at the next depth level. BFS is particularly useful for finding the shortest path in unweighted graphs.