Cracking the Code of Sorting and Searching: 11 Algorithms for Enhanced Efficiency

Unravel the secrets of sorting and searching algorithms in this comprehensive post. Discover eleven algorithms that will equip you with the tools to sort and search data efficiently. Elevate your data structure and algorithms expertise with this invaluable resource. In this post, we will learn about sorting algorithms in Python. Let’s dive in! You can run this post in Google Colab using this link:

1. Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted.

def bubble_sort(array):
    n = len(array)
    for i in range(n-1):
        for j in range(n-i-1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

Explanation:

The bubble sort algorithm starts with the outer loop that iterates over the array to perform multiple passes. In each pass, the inner loop compares adjacent elements and swaps them if they are in the wrong order. By the end of each pass, the largest element “bubbles” up to its correct position at the end of the array.

• The outer loop (i) runs from 0 to n-2 (inclusive) because after n-1 passes, the largest element is already in its correct position.
• The inner loop (j) runs from 0 to n-i-2 (inclusive) because the largest i elements are already sorted at the end of the array after each pass.
• If the current element array[j] is greater than the next element array[j+1], a swap is performed.
• The process continues until the entire array is sorted, and no more swaps are needed.

Time and Space Complexity:

The bubble sort algorithm has a worst-case time complexity of O(n^2), where n is the size of the input array. It involves nested loops, and in the worst case, it requires comparisons and swaps for every pair of elements in the array. The space complexity is O(1) since the algorithm uses a constant amount of additional space to perform the sorting. It does not depend on the size of the input array.

Test:

arr = [5, 3, 8, 2, 1]
print(f"Input: arr = {arr}")
print("Output:", bubble_sort(arr))  # Output: [1, 2, 3, 5, 8]

arr = [1, 2, 3, 4, 5]
print(f"Input: arr = {arr}")
print("Output:", bubble_sort(arr))  # Output: [1, 2, 3, 4, 5]

arr = [10, 5, 2, 8, 3]
print(f"Input: arr = {arr}")
print("Output:", bubble_sort(arr))  # Output: [2, 3, 5, 8, 10]

arr = [9, 7, 5, 3, 1]
print(f"Input: arr = {arr}")
print("Output:", bubble_sort(arr))  # Output: [1, 3, 5, 7, 9]

Input: arr = [5, 3, 8, 2, 1]
Output: [1, 2, 3, 5, 8]
Input: arr = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]
Input: arr = [10, 5, 2, 8, 3]
Output: [2, 3, 5, 8, 10]
Input: arr = [9, 7, 5, 3, 1]
Output: [1, 3, 5, 7, 9]

2. Insertion Sort

Insertion Sort is a simple comparison-based sorting algorithm. It builds the final sorted array one item at a time by iteratively inserting each element into its proper position within the already sorted part of the array.

def insertion_sort(array):
    for i in range(1, len(array)):
        j = i

        while j > 0 and array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
            j -= 1

    return array

Explanation:

The insertion sort algorithm starts with the outer loop that iterates from the second element to the last element of the array. It considers the current element (array[i]) and moves it to its correct position within the sorted part of the array on each iteration.

• The inner loop (while loop) starts from the current element index (j = i) and continues moving towards the beginning of the array (j > 0) as long as the current element is smaller than its adjacent element (array[j] < array[j-1]).
• In each iteration of the inner loop, if the condition is satisfied, a swap is performed to move the current element back one position.
• The process continues until the current element is at its correct sorted position, and then the outer loop moves to the next element.

Time and space complexity:

The insertion sort algorithm has a worst-case time complexity of O(n^2), where n is the size of the input array. In the worst case, for each element, it may have to traverse the entire sorted portion of the array. The space complexity is O(1) since the algorithm uses a constant amount of additional space to perform the sorting. It does not depend on the size of the input array.

Test:

arr = [5, 3, 8, 2, 1]
print(f"Input: arr = {arr}")
print("Output:", insertion_sort(arr))  # Output: [1, 2, 3, 5, 8]

arr = [1, 2, 3, 4, 5]
print(f"Input: arr = {arr}")
print("Output:", insertion_sort(arr))  # Output: [1, 2, 3, 4, 5]

arr = [10, 5, 2, 8, 3]
print(f"Input: arr = {arr}")
print("Output:", insertion_sort(arr))  # Output: [2, 3, 5, 8, 10]

arr = [9, 7, 5, 3, 1]
print(f"Input: arr = {arr}")
print("Output:", insertion_sort(arr))  # Output: [1, 3, 5, 7, 9]

Input: arr = [5, 3, 8, 2, 1]
Output: [1, 2, 3, 5, 8]
Input: arr = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]
Input: arr = [10, 5, 2, 8, 3]
Output: [2, 3, 5, 8, 10]
Input: arr = [9, 7, 5, 3, 1]
Output: [1, 3, 5, 7, 9]

3. selection sort

Selection Sort is a simple comparison-based sorting algorithm. It divides the input array into two parts: the sorted part at the beginning and the unsorted part at the end. It repeatedly selects the smallest (or largest) element from the unsorted part and swaps it with the first element of the unsorted part.

def selection_sort(array):
    current_idx = 0
    while current_idx < len(array) - 1:
        smallest_idx = current_idx
        for i in range(current_idx + 1, len(array)):
            if array[i] < array[smallest_idx]:
                smallest_idx = i

        array[current_idx], array[smallest_idx] = array[smallest_idx], array[current_idx]
        current_idx += 1

    return array

Explanation:

The selection sort algorithm starts with the outer loop that represents the boundary between the sorted and unsorted parts of the array. In each iteration, it finds the smallest element in the unsorted part and swaps it with the element at the current index.

• The variable current_idx keeps track of the current index that separates the sorted and unsorted parts.
• The variable smallest_idx is initialized to the current_idx, representing the index of the smallest element found so far.
• The inner loop (for loop) starts from current_idx + 1 and iterates over the remaining unsorted part of the array. It compares each element with the element at smallest_idx and updates smallest_idx if a smaller element is found.
• After finding the smallest element, a swap is performed between the element at current_idx and the element at smallest_idx.
• The current_idx is incremented, and the process continues until the entire array is sorted.

Time and space complexity:

The selection sort algorithm has a worst-case time complexity of O(n^2), where n is the size of the input array. It involves nested loops, and in the worst case, it requires comparisons and swaps for every pair of elements in the array. The space complexity is O(1) since the algorithm uses a constant amount of additional space to perform the sorting. It does not depend on the size of the input array.

Test:

arr = [5, 3, 8, 2, 1]
print(f"Input: arr = {arr}")
print("Output:", selection_sort(arr))  # Output: [1, 2, 3, 5, 8]

arr = [1, 2, 3, 4, 5]
print(f"Input: arr = {arr}")
print("Output:", selection_sort(arr))  # Output: [1, 2, 3, 4, 5]

arr = [10, 5, 2, 8, 3]
print(f"Input: arr = {arr}")
print("Output:", selection_sort(arr))  # Output: [2, 3, 5, 8, 10]

arr = [9, 7, 5, 3, 1]
print(f"Input: arr = {arr}")
print("Output:", selection_sort(arr))  # Output: [1, 3, 5, 7, 9]

Input: arr = [5, 3, 8, 2, 1]
Output: [1, 2, 3, 5, 8]
Input: arr = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]
Input: arr = [10, 5, 2, 8, 3]
Output: [2, 3, 5, 8, 10]
Input: arr = [9, 7, 5, 3, 1]
Output: [1, 3, 5, 7, 9]

4. Merge Sort

Merge Sort is a divide-and-conquer sorting algorithm that recursively divides the input array into two halves, sorts them individually, and then merges them back into a single sorted array.

Think of it as a recursive algorithm continuously splits the array in half until it cannot be further divided. This means that if the array becomes empty or has only one element left, the dividing will stop, i.e. it is the base case to stop the recursion. If the array has multiple elements, split the array into halves and recursively invoke the merge sort on each of the halves. Finally, when both halves are sorted, the merge operation is applied. Merge operation is the process of taking two smaller sorted arrays and combining them to eventually make a larger one.

def merge_sort(array):
    if len(array) <= 1:
        return array

    mid = len(array) // 2
    left_arr = array[:mid]
    right_arr = array[mid:]

    return merge_sorted_arrays(merge_sort(left_arr), merge_sort(right_arr))


def merge_sorted_arrays(left_arr, right_arr):
    sorted_arr = []
    i = j = 0

    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            sorted_arr.append(left_arr[i])
            i += 1
        else:
            sorted_arr.append(right_arr[j])
            j += 1

    sorted_arr.extend(left_arr[i:])
    sorted_arr.extend(right_arr[j:])

    return sorted_arr

Explanation:

The merge sort algorithm follows a recursive divide-and-conquer approach:

• The merge_sort function is recursively called on the left and right halves of the input array until the base case is reached (when the array has only one element).
• The array is divided into two halves by finding the middle index (mid), and the left and right subarrays are created.
• The merge_sorted_arrays function is responsible for merging the sorted left and right arrays into a single sorted array.
• The merging process occurs by comparing the elements from both arrays (left_arr and right_arr) and adding the smaller element to the sorted_arr.
• After exhausting one of the arrays, any remaining elements in the other array are appended to the sorted_arr.
• Finally, the sorted array is returned.

Time and space complexity:

The merge sort algorithm has a worst-case time complexity of O(n log(n)), where n is the size of the input array. It divides the array into halves recursively and performs merging operations that take linear time. The log(n) factor arises from the recursive division, and the n factor arises from the merging step.

The space complexity is O(n log(n)) due to the additional space required for the recursive function calls and the merging process. In each recursive call, additional space is used for the left and right subarrays. However, the space usage is not cumulative since only one recursive call is active at a time.

Test:

arr = [5, 3, 8, 2, 1]
print(f"Input: arr = {arr}")
print("Output:", merge_sort(arr))  # Output: [1, 2, 3, 5, 8]

arr = [1, 2, 3, 4, 5]
print(f"Input: arr = {arr}")
print("Output:", merge_sort(arr))  # Output: [1, 2, 3, 4, 5]

arr = [10, 5, 2, 8, 3]
print(f"Input: arr = {arr}")
print("Output:", merge_sort(arr))  # Output: [2, 3, 5, 8, 10]

arr = [9, 7, 5, 3, 1]
print(f"Input: arr = {arr}")
print("Output:", merge_sort(arr))  # Output [1, 3, 5, 7, 9]

Input: arr = [5, 3, 8, 2, 1]
Output: [1, 2, 3, 5, 8]
Input: arr = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]
Input: arr = [10, 5, 2, 8, 3]
Output: [2, 3, 5, 8, 10]
Input: arr = [9, 7, 5, 3, 1]
Output: [1, 3, 5, 7, 9]

5. Quick Sort

Like Merge Sort, Quick Sort is a divide-and-conquer sorting algorithm that selects a pivot element and partitions the array around the pivot. It recursively sorts the subarrays on either side of the pivot until the entire array is sorted.

def quick_sort(array):
    quick_sort_helper(array, 0, len(array) - 1)
    return array


def quick_sort_helper(array, start, end):
    # Base case: subarray has 0 or 1 element
    if start >= end:
        return

    # Choose the first element as the pivot
    pivot = start
    left = start + 1
    right = end

    while right >= left:
        # Swap elements if they are on the wrong side of the pivot
        if array[left] > array[pivot] and array[right] < array[pivot]:
            array[left], array[right] = array[right], array[left]

        if array[left] <= array[pivot]:
            left += 1

        if array[right] >= array[pivot]:
            right -= 1

    # Move the pivot to its sorted position
    array[pivot], array[right] = array[right], array[pivot]

    # Recursively sort the subarrays
    is_left_subarray_smaller = right - 1 - start < end - (right + 1)

    if is_left_subarray_smaller:
        quick_sort_helper(array, start, right - 1)
        quick_sort_helper(array, right + 1, end)
    else:
        quick_sort_helper(array, right + 1, end)
        quick_sort_helper(array, start, right - 1)

Explanation:

The quick sort algorithm follows a recursive divide-and-conquer approach:

• The quick_sort function calls the quick_sort_helper function to perform the sorting.
• The quick_sort_helper function takes the start and end indices of the subarray to be sorted.
• In each recursive call, the function selects a pivot element (in this case, the first element) and partitions the array around the pivot.
• The partitioning process is performed using two pointers, left and right, that move towards each other until they cross.
• The elements are compared with the pivot, and if they are on the wrong side, they are swapped.
• After the partitioning process, the pivot element is in its sorted position, and the subarray is divided into two parts.
• Depending on the size of the subarrays, the function makes recursive calls to sort the smaller subarray first to minimize the stack space used for recursion.
• The process continues until the base case is reached (subarray with 0 or 1 element).

Time and space complexity:

The quick sort algorithm has an average-case time complexity of O(n log(n)), where n is the size of the input array. However, in the worst case, the time complexity can be O(n^2) when the pivot selection is unfavorable. The partitioning step takes linear time, and the recursive calls are made on smaller subarrays.

The space complexity is O(log(n)) on average, representing the stack space used for the recursive calls. In the worst case, it can be O(n) when the recursive calls are made on subarrays of size close to n.

Test:

arr = [5, 3, 8, 2, 1]
print(f"Input: arr = {arr}")
print("Output:", quick_sort(arr))  # Output: [1, 2, 3, 5, 8]

arr = [1, 2, 3, 4, 5]
print(f"Input: arr = {arr}")
print("Output:", quick_sort(arr))  # Output: [1, 2, 3, 4, 5]

arr = [10, 5, 2, 8, 3]
print(f"Input: arr = {arr}")
print("Output:", quick_sort(arr))  # Output: [2, 3, 5, 8, 10]

arr = [9, 7, 5, 3, 1]
print(f"Input: arr = {arr}")
print("Output:", quick_sort(arr))  # Output [1, 3, 5, 7, 9]

Input: arr = [5, 3, 8, 2, 1]
Output: [1, 2, 3, 5, 8]
Input: arr = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]
Input: arr = [10, 5, 2, 8, 3]
Output: [2, 3, 5, 8, 10]
Input: arr = [9, 7, 5, 3, 1]
Output: [1, 3, 5, 7, 9]

6. Heap Sort (Binary Heap)

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It first builds a max heap from the input array and then repeatedly extracts the maximum element from the heap, swapping it with the last element of the heap and reducing the heap size. This process continues until the entire array is sorted.

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heap_sort(array):
    n = len(array)

    # Build a max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(array, n, i)

    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        array[i], array[0] = array[0], array[i]
        heapify(array, i, 0)

    return array

Explanation:

The heap sort algorithm can be divided into two main steps:

• The heapify function is responsible for creating a max heap from an unsorted array. It takes three parameters: the array, the size of the heap (n), and the index of the current element (i) being considered. It compares the element at index i with its left and right child (if they exist) and swaps it with the larger child if necessary. This process is repeated recursively to ensure that the heap property is maintained.
• The heap_sort function first builds a max heap from the input array by calling heapify on all non-leaf nodes starting from the last non-leaf node up to the root. After building the max heap, it repeatedly extracts the maximum element from the heap by swapping it with the last element and reducing the heap size. This step is performed in reverse order to sort the array in ascending order.
• The final sorted array is returned.

Time and space complexity:

The heap sort algorithm has a worst-case time complexity of O(n log(n)), where n is the size of the input array. Both the build heap step and the extract max step take O(log(n)) time, and they are performed n times. The space complexity is O(1) since the sorting is done in place, without using any additional data structures.

Test:

arr = [5, 3, 8, 2, 1]
print(f"Input: arr = {arr}")
print("Output:", heap_sort(arr))  # Output: [1, 2, 3, 5, 8]

arr = [1, 2, 3, 4, 5]
print(f"Input: arr = {arr}")
print("Output:", heap_sort(arr))  # Output: [1, 2, 3, 4, 5]

arr = [10, 5, 2, 8, 3]
print(f"Input: arr = {arr}")
print("Output:", heap_sort(arr))  # Output: [2, 3, 5, 8, 10]

arr = [9, 7, 5, 3, 1]
print(f"Input: arr = {arr}")
print("Output:", heap_sort(arr))  # Output [1, 3, 5, 7, 9]

Input: arr = [5, 3, 8, 2, 1]
Output: [1, 2, 3, 5, 8]
Input: arr = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]
Input: arr = [10, 5, 2, 8, 3]
Output: [2, 3, 5, 8, 10]
Input: arr = [9, 7, 5, 3, 1]
Output: [1, 3, 5, 7, 9]

7. Topological Sort

Academic definition:

Topological Sort is an algorithm used to order the nodes in a directed acyclic graph (DAG) such that for every directed edge (u, v), node u comes before node v in the ordering. It is commonly used in tasks that have dependencies, such as task scheduling or determining the order of courses to take in a curriculum.

def topological_sort(jobs, deps):
    graph = create_job_graph(jobs, deps)
    return get_ordered_jobs(graph)


def create_job_graph(jobs, deps):
    graph = JobGraph(jobs)
    for prereq, job in deps:
        graph.add_prereq(job, prereq)
    return graph


def get_ordered_jobs(graph):
    ordered_jobs = []
    nodes = graph.nodes
    while nodes:
        node = nodes.pop()
        contains_cycle = depth_first_traverse(node, ordered_jobs)
        if contains_cycle:
            return []
    return ordered_jobs


def depth_first_traverse(node, ordered_jobs):
    if node.visited:
        return False
    if node.visiting:
        return True
    node.visiting = True
    for prereq_node in node.prereqs:
        contains_cycle = depth_first_traverse(prereq_node, ordered_jobs)
        if contains_cycle:
            return True
    node.visited = True
    node.visiting = False
    ordered_jobs.append(node.job)
    return False


class JobGraph:
    def __init__(self, jobs):
        self.nodes = []
        self.graph = {}
        for job in jobs:
            self.add_node(job)

    def add_prereq(self, job, prereq):
        job_node = self.get_node(job)
        prereq_node = self.get_node(prereq)
        job_node.prereqs.append(prereq_node)

    def add_node(self, job):
        self.graph[job] = JobNode(job)
        self.nodes.append(self.graph[job])

    def get_node(self, job):
        if job not in self.graph:
            self.add_node(job)
        return self.graph[job]


class JobNode:
    def __init__(self, job):
        self.job = job
        self.prereqs = []
        self.visited = False
        self.visiting = False

Explanation:

The topological sort algorithm uses depth-first search (DFS) to traverse the graph and find a valid ordering of the jobs. The code can be summarized as follows:

• The topological_sort function is the entry point of the algorithm. It takes a list of jobs and their dependencies and returns the ordered jobs.
• The create_job_graph function creates a directed graph using a JobGraph object. It adds nodes for each job and their dependencies as edges.
• The get_ordered_jobs function performs the topological sort by calling depth_first_traverse on each node in the graph. It starts with the last node and explores its dependencies recursively.
• The depth_first_traverse function checks for cycles by maintaining two flags: visited and visiting. It returns True if a cycle is detected and False otherwise. It adds the jobs to the ordered_jobs list in the correct order.
• The JobGraph class represents the graph and provides methods to add nodes and edges. It uses a hash table (graph) to map job names to their corresponding nodes (JobNode).
• The JobNode class represents a job node in the graph. It contains the job name, a list of prerequisite nodes, and flags to represent the node’s status during traversal.

Time and space complexity:

The time complexity of the topological sort algorithm is O(j + d), where j is the number of jobs and d is the number of dependencies. The algorithm traverses each job and its dependencies once, resulting in a linear time complexity. The space complexity is also O(j + d) since the algorithm constructs a graph representation of the jobs and their dependencies. The space is used to store the nodes, edges, and additional data structures for traversal.

test:

jobs = [1, 2, 3, 4]
deps = [(1, 2), (1, 3), (3, 2), (4, 2), (4, 3)]
print(f"Input: jobs = {jobs}, deps = {deps}")
print("Output:", topological_sort(jobs, deps))  # Output: [4, 1, 3, 2]

jobs = [1, 2, 3, 4, 5]
deps = [(1, 2), (2, 3), (3, 4), (4, 5)]
print(f"Input: jobs = {jobs}, deps = {deps}")
print("Output:", topological_sort(jobs, deps))  # Output: [1, 2, 3, 4, 5]

jobs = [1, 2, 3, 4]
deps = [(1, 2), (2, 3), (3, 4), (4, 2)]
print(f"Input: jobs = {jobs}, deps = {deps}")
print("Output:", topological_sort(jobs, deps))  # Output: []

jobs = [1, 2, 3]
deps = [(1, 2), (2, 3), (3, 1)]
print(f"Input: jobs = {jobs}, deps = {deps}")
print("Output:", topological_sort(jobs, deps))  # Output: []

Input: jobs = [1, 2, 3, 4], deps = [(1, 2), (1, 3), (3, 2), (4, 2), (4, 3)]
Output: [4, 1, 3, 2]
Input: jobs = [1, 2, 3, 4, 5], deps = [(1, 2), (2, 3), (3, 4), (4, 5)]
Output: [1, 2, 3, 4, 5]
Input: jobs = [1, 2, 3, 4], deps = [(1, 2), (2, 3), (3, 4), (4, 2)]
Output: []
Input: jobs = [1, 2, 3], deps = [(1, 2), (2, 3), (3, 1)]
Output: []

8. Radix Sort

Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. It starts by sorting the numbers based on the least significant digit and gradually moves towards the most significant digit. The algorithm repeatedly uses a stable sorting algorithm, such as Counting Sort, to sort the numbers based on each digit.

def radix_sort(array):
    if len(array) == 0:
        return array

    max_number = max(array)
    num_digits = len(str(max_number))

    for digit in range(num_digits):
        counting_sort(array, digit)

    return array


def counting_sort(array, digit):
    sorted_array = [0] * len(array)
    count_array = [0] * 10

    for num in array:
        count_index = (num // (10 ** digit)) % 10
        count_array[count_index] += 1

    for idx in range(1, 10):
        count_array[idx] += count_array[idx - 1]

    for idx in range(len(array) - 1, -1, -1):
        count_index = (array[idx] // (10 ** digit)) % 10
        count_array[count_index] -= 1
        sorted_index = count_array[count_index]
        sorted_array[sorted_index] = array[idx]

    for idx in range(len(array)):
        array[idx] = sorted_array[idx]

Explanation:

The radix sort algorithm processes the digits of the numbers from the least significant digit to the most significant digit. The code can be summarized as follows:

• The radix_sort function is the entry point of the algorithm. It checks if the input array is empty and finds the maximum number to determine the number of - digits in the largest number. It then performs radix sort by calling counting_sort for each digit position.
• The counting_sort function is used as a subroutine to sort the numbers based on the current digit. It creates a count array to count the occurrences of each digit value (0 to 9) in the current digit position.
• The count array is modified to store the positions where each digit value should be placed in the sorted array.
• The sorted array is constructed by iterating over the input array in reverse order and placing each element at the correct position based on the count array.
• Finally, the original array is updated with the sorted elements.

Time and space complexity:

The time complexity of radix sort is O(d * (n + k)), where n is the number of elements in the array, d is the number of digits in the maximum number, and k is the range of the digit values (typically 10 for decimal digits). The algorithm performs counting sort for each digit position, which takes O(n + k) time.

The space complexity is O(n + k) since additional space is required for the sorted array, count array, and other variables. The space complexity increases with the range of digit values.

Test:

array = [170, 45, 75, 90, 802, 24, 2, 66]
print(f"Input: {array}")
radix_sort(array)
print("Output:", array)  # Output: [2, 24, 45, 66, 75, 90, 170, 802]

array = [321, 56, 789, 12, 456, 234, 901]
print(f"Input: {array}")
radix_sort(array)
print("Output:", array)  # Output: [12, 56, 234, 321, 456, 789, 901]

array = [9, 8, 7, 6, 5, 4, 3, 2, 1]
print(f"Input: {array}")
radix_sort(array)
print("Output:", array)  # Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

array = [1000, 100, 10, 1, 10000, 100000]
print(f"Input: {array}")
radix_sort(array)
print("Output:", array)  # Output: [1, 10, 100, 1000, 10000, 100000]

Input: [170, 45, 75, 90, 802, 24, 2, 66]
Output: [2, 24, 45, 66, 75, 90, 170, 802]
Input: [321, 56, 789, 12, 456, 234, 901]
Output: [12, 56, 234, 321, 456, 789, 901]
Input: [9, 8, 7, 6, 5, 4, 3, 2, 1]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Input: [1000, 100, 10, 1, 10000, 100000]
Output: [1, 10, 100, 1000, 10000, 100000]

9. Binary Search

Binary search is an efficient algorithm used to find a specific target value within a sorted array. It works by repeatedly dividing the search interval in half until the target value is found or the interval becomes empty.

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if target == arr[mid]:
            return mid
        elif target < arr[mid]:
            right = mid - 1
        else:
            left = mid + 1

    return -1

Explanation:

The binary search algorithm starts with an initial left index and right index representing the boundaries of the search interval. It then calculates the middle index and compares the target value (target) with the value at the middle index of the array (arr[mid]).

• If the target value is found, it returns the index (mid).
• If the target value is less than the middle element, it updates the right index to be mid - 1 to search in the left half of the interval.
• If the target value is greater than the middle element, it updates the left index to be mid + 1 to search in the right half of the interval.
• The process continues until the target value is found or the interval becomes empty (left index surpasses the right index).
• If the target value is not found, the function returns -1.

Time and Space Complexity:

The binary search algorithm has a time complexity of O(log n), where n is the size of the input array. It performs a halving of the search interval in each iteration, resulting in a logarithmic time complexity. The space complexity is O(1) since the algorithm uses a fixed amount of additional space to store the left, right, and mid indices. It does not depend on the size of the input array.

Test:

arr = [1, 2, 3, 4, 5]
x = 3
print(f"Input: arr = {arr}, x = {x}")
print("Output:", binary_search(arr, x))  # Output: 2

arr = [1, 2, 3, 4, 5]
x = 6
print(f"Input: arr = {arr}, x = {x}")
print("Output:", binary_search(arr, x))  # Output: -1

arr = [10, 20, 30, 40, 50, 60]
x = 40
print(f"Input: arr = {arr}, x = {x}")
print("Output:", binary_search(arr, x))  # Output: 3

arr = [10, 20, 30, 40, 50, 60]
x = 25
print(f"Input: arr = {arr}, x = {x}")
print("Output:", binary_search(arr, x))  # Output: -1

Input: arr = [1, 2, 3, 4, 5], x = 3
Output: 2
Input: arr = [1, 2, 3, 4, 5], x = 6
Output: -1
Input: arr = [10, 20, 30, 40, 50, 60], x = 40
Output: 3
Input: arr = [10, 20, 30, 40, 50, 60], x = 25
Output: -1

10. Find Kth Smallest/Largest Element In Unsorted Array

• Method 1: Sorting Algorithm and Select Kth

  • Time Complexity: O(nlog(n))
  • Explanation: This method involves sorting the array using a sorting algorithm with a time complexity of O(nlog(n)). Once the array is sorted, the kth smallest or largest element can be easily identified by accessing the corresponding index.
  • Code Explanation: This method is not explicitly provided in the given code. However, it involves sorting the array using a sorting algorithm (e.g., merge sort, quicksort) and then returning the kth element.

• Method 2: Using Heap

  • Time Complexity: O(nlog(k))
  • Explanation: This method utilizes a min-heap to efficiently find the kth smallest element in the unsorted array. It maintains a heap of size k, where the smallest k elements are stored. For each element in the array, if the heap size is less than k, the element is added to the heap. If the heap size reaches k, the smallest element is replaced if the current element is larger, ensuring the heap always contains the k smallest elements. The smallest element in the heap will be the kth smallest element in the array.

import heapq

def kth_smallest(arr, k):
    # Initialize a min-heap
    heap = []

    # Iterate over each element in the array
    for value in arr:
        # Push the negative value onto the heap
        # to simulate a max-heap behavior
        if len(heap) < k:
            heapq.heappush(heap, -value)
        else:
            # If the heap size reaches k, push the current
            # element and simultaneously pop the smallest element
            heapq.heappushpop(heap, -value)

    # Return the negation of the top element in the heap
    # to retrieve the kth smallest element
    return -heap[0]

Explanation:

• The function kth_smallest takes an array arr and an integer k as input.
• A min-heap, represented by the heap list, is initialized to store the k smallest elements encountered so far.
• The function iterates over each element value in the array.
• If the size of the heap is less than k, the negative value of the current element is pushed onto the heap using heapq.heappush, simulating a max-heap behavior.
• If the heap size reaches k, the current element is pushed onto the heap using heapq.heappushpop, which simultaneously pushes the element and pops the smallest element. This ensures that the heap always contains the k smallest elements encountered so far.
• After iterating through all the elements, the kth smallest element will be present at the top of the heap.
• The negation of the top element is returned as the final result, giving us the kth smallest element from the original array.

Test:

arr = [7, 2, 1, 6, 8, 5]
k = 3
print(f"Array: {arr}")
print(f"kth Smallest Element ({k}): {kth_smallest(arr, k)}")
# Output: kth Smallest Element (3): 5

arr = [9, 4, 2, 7, 1, 5]
k = 2
print(f"Array: {arr}")
print(f"kth Smallest Element ({k}): {kth_smallest(arr, k)}")
# Output: kth Smallest Element (2): 2

arr = [3, 9, 1, 6, 2, 8]
k = 4
print(f"Array: {arr}")
print(f"kth Smallest Element ({k}): {kth_smallest(arr, k)}")
# Output: kth Smallest Element (4): 6

Array: [7, 2, 1, 6, 8, 5]
kth Smallest Element (3): 5
Array: [9, 4, 2, 7, 1, 5]
kth Smallest Element (2): 2
Array: [3, 9, 1, 6, 2, 8]
kth Smallest Element (4): 6

• Method 3: Using Pivot and Partitioning Concept (Similar to Quick Sort)

  • Time Complexity: O(n) on average, O(n^2) in the worst case
  • Explanation: This method is based on the partitioning concept used in quicksort. It selects a pivot element and partitions the array such that elements smaller than the pivot are on the left and elements larger than the pivot are on the right. By comparing the pivot’s position with k, we can determine whether the kth smallest element lies in the left or right subarray. This process is recursively applied to the corresponding subarray until the kth element is found.

def kth_smallest(arr, k):
    left = 0
    right = len(arr) - 1
    return kth_smallest_helper(arr, left, right, k)

def kth_smallest_helper(arr, left, right, k):
    if k > 0 and k <= right - left + 1:
        # Partition the array around the last element and get the position of the pivot element in the sorted array
        pos = partition(arr, left, right)

        # If the position is the same as k, the pivot element is the kth smallest element
        if pos - left == k - 1:
            return arr[pos]

        # If the position is greater than k, recur for the left subarray
        if pos - left > k - 1:
            return kth_smallest_helper(arr, left, pos - 1, k)

        # Else, recur for the right subarray
        return kth_smallest_helper(arr, pos + 1, right, k - pos + left - 1)

    # If k is greater than the number of elements in the array, return -1
    return -1

def partition(arr, left, right):
    pivot = arr[right]  # Choose the last element as the pivot
    i = left

    for j in range(left, right):
        if arr[j] <= pivot:
            # Swap arr[i] and arr[j] to place elements smaller than the pivot on the left side
            arr[i], arr[j] = arr[j], arr[i]
            i += 1

    # Swap arr[i] and arr[right] to place the pivot element in its correct position
    arr[i], arr[right] = arr[right], arr[i]

    return i

Explanation:

• The function kth_smallest takes an array arr and an integer k as input.
• The function kth_smallest_helper is a recursive helper function that performs the actual calculation.
• If k is within the valid range (greater than 0 and less than or equal to the number of elements in the array), the function proceeds.
• The array is partitioned around the last element (arr[right]) as the pivot using the partition function.
• The partition function rearranges the elements such that all elements smaller than the pivot are placed on the left side, and all elements greater than the pivot are placed on the right side.
• The position of the pivot element in the sorted array is obtained.
• If the position of the pivot element is equal to k - 1, it means that the pivot element is the kth smallest element, and it is returned.
• If the position of the pivot element is greater than k - 1, it means that the kth smallest element lies in the left subarray, and the function recursively calls kthSmallest_helper on the left subarray.
• If the position of the pivot element is less than k - 1, it means that the kth smallest element lies in the right subarray, and the function recursively calls kth_smallest_helper on the right subarray, adjusting the value of k accordingly.
• If k is outside the valid range, indicating that there are fewer elements in the array than k, the function returns -1.
• The partition function follows the traditional partitioning process of QuickSort. It chooses the last element as the pivot. It initializes the index i to the leftmost element (left) and iterates from left to right-1 using the variable j. If the element at index j is less than or equal to the pivot, it swaps the elements at indices i and j, and increments i. This process ensures that all elements smaller than the pivot are placed to the left of i. Finally, it swaps the pivot element (arr[right]) with the element at index i to put the pivot in its correct sorted position. The function then returns the index i, which represents the position of the pivot in the rearranged array.

Test:

arr = [7, 2, 1, 6, 8, 5]
k = 3
print(f"Array: {arr}")
print(f"kth Smallest Element ({k}): {kth_smallest(arr, k)}")
# Output: kth Smallest Element (3): 5

arr = [9, 4, 2, 7, 1, 5]
k = 2
print(f"Array: {arr}")
print(f"kth Smallest Element ({k}): {kth_smallest(arr, k)}")
# Output: kth Smallest Element (2): 2

arr = [3, 9, 1, 6, 2, 8]
k = 4
print(f"Array: {arr}")
print(f"kth Smallest Element ({k}): {kth_smallest(arr, k)}")
# Output: kth Smallest Element (4): 6

Array: [7, 2, 1, 6, 8, 5]
kth Smallest Element (3): 5
Array: [9, 4, 2, 7, 1, 5]
kth Smallest Element (2): 2
Array: [3, 9, 1, 6, 2, 8]
kth Smallest Element (4): 6

11. Interpolation Search

Interpolation search is an algorithm used to search for a target element in a sorted array. It improves on the performance of binary search by using a formula to estimate the likely position of the target within the array. This algorithm works best on uniformly distributed arrays.

def interpolation_search(arr, target):
    left = 0
    right = len(arr) - 1
    return interpolation_search_helper(arr, left, right, target)

def interpolation_search_helper(arr, left, right, target):
    if left <= right and target >= arr[left] and target <= arr[right]:
        pos = left + ((right - left) // (arr[right] - arr[left])) * (target - arr[left])

        if arr[pos] == target:
            return pos

        if arr[pos] < target:
            return interpolation_search_helper(arr, pos + 1, right, target)

        if arr[pos] > target:
            return interpolation_search_helper(arr, left, pos - 1, target)

    return -1

Explanation:

The interpolation_search function takes an array (arr) and a target value (target) as input. It initializes the left pointer to the beginning of the array and the right pointer to the end of the array. It then calls the interpolation_search_helper function with these parameters.

The interpolation_search_helper function checks if the target value is within the range defined by the left and right pointers and if it’s within the range of values in the array. If so, it calculates the estimated position (pos) of the target using the interpolation formula.

The interpolation formula calculates the position by considering the proportion of the target value’s difference from the left element to the difference between the left and right elements. This formula assumes a uniform distribution of values in the array.

If the value at the estimated position (arr[pos]) matches the target value, it returns the position. If the estimated value is smaller than the target value, it recursively calls the interpolation_search_helper function with an updated left pointer (pos + 1) and the same right pointer. If the estimated value is larger than the target value, it recursively calls the interpolation_search_helper function with an updated right pointer (pos - 1) and the same left pointer.

If the target value is not found within the given range or if the left pointer exceeds the right pointer, the function returns -1 to indicate that the target value was not found in the array.

Time and space complexity:

The time complexity of interpolation search is O(log(log n)) in the average case, where n is the size of the input array. However, in the worst case, when the data is not uniformly distributed, the time complexity can be O(n). The space complexity of the algorithm is O(1) as it does not require any additional data structures.

Test:

arr = [2, 4, 6, 8, 10]
target = 6
print("Input: arr =", arr, "target =", target)
print("Output:", interpolation_search(arr, target))  # Expected output: 2

arr = [1, 3, 5, 7, 9]
target = 10
print("Input: arr =", arr, "target =", target)
print("Output:", interpolation_search(arr, target))  # Expected output: -1


arr = [1, 2, 3, 4, 5]
target = 1
print("Input: arr =", arr, "target =", target)
print("Output:", interpolation_search(arr, target))  # Expected output: 0

Input: arr = [2, 4, 6, 8, 10] target = 6
Output: 2
Input: arr = [1, 3, 5, 7, 9] target = 10
Output: -1
Input: arr = [1, 2, 3, 4, 5] target = 1
Output: 0