Cracking the Code of Sorting and Searching: 11 Algorithms for Enhanced Efficiency
Published:
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 ton-2
(inclusive) because aftern-1
passes, the largest element is already in its correct position. - The inner loop (
j
) runs from 0 ton-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 elementarray[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 thecurrent_idx
, representing the index of the smallest element found so far. - The inner loop (
for
loop) starts fromcurrent_idx + 1
and iterates over the remaining unsorted part of the array. It compares each element with the element atsmallest_idx
and updatessmallest_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 atsmallest_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
andright_arr
) and adding the smaller element to thesorted_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 thequick_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
andright
, 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 callingheapify
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
andvisiting
. It returns True if a cycle is detected and False otherwise. It adds the jobs to theordered_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 callingcounting_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.
- Time Complexity:
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.
- Time Complexity:
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 arrayarr
and an integerk
as input. - A min-heap, represented by the
heap
list, is initialized to store thek
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.
- Time Complexity:
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 arrayarr
and an integerk
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 thepartition
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 callskth_smallest_helper
on the right subarray, adjusting the value ofk
accordingly. - If
k
is outside the valid range, indicating that there are fewer elements in the array thank,
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 indexi
to the leftmost element (left) and iterates from left toright-1
using the variablej
. If the element at indexj
is less than or equal to the pivot, it swaps the elements at indicesi
andj
, and incrementsi
. This process ensures that all elements smaller than the pivot are placed to the left ofi
. Finally, it swaps the pivot element (arr[right]
) with the element at indexi
to put the pivot in its correct sorted position. The function then returns the indexi
, 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