Data Structures and Algorithms with Python

Data structures and algorithms are essential concepts for any programmer who wants to write efficient and optimized code. In this article, we will learn what data structures and algorithms are, why they are useful, and how we can use them effectively in Python.

What are Data Structures?

Data structures are ways of organizing and storing data in a computer memory. They allow us to access, manipulate, and process data in different ways according to our needs. Some examples of data structures are lists, tuples, dictionaries, sets, stacks, queues, linked lists, trees, graphs, etc.

Python provides built-in data structures such as lists, tuples, dictionaries, and sets that are easy to use and versatile. We can also create our own data structures using classes and objects. Data structures can be classified into two types: linear and nonlinear.

Linear Data Structures

Linear data structures are those that store data in a sequential manner, such that each element has a unique predecessor and successor (except for the first and last element). Some examples of linear data structures are arrays, lists, stacks, queues, etc.

Lists

Lists are ordered collections of data that can store elements of different types. Lists are mutable, meaning we can change their contents after creation. Lists are implemented using arrays internally, so they have fast random access but slow insertion and deletion at arbitrary positions. We can create lists using square brackets [] or the list() function.

Example:

# Creating a list of numbers
numbers = [1, 2, 3, 4, 5]
print(numbers)
# Creating a list of strings
fruits = ['apple', 'banana', 'orange', 'mango']
print(fruits)
# Creating a list of mixed types
mixed = [1, 'hello', 3.14, True]
print(mixed)

Output:

[1, 2, 3, 4, 5]
['apple', 'banana', 'orange', 'mango']
[1, 'hello', 3.14, True]

We can access the elements of a list using their index positions. The index starts from 0 for the first element and goes up to n-1 for the nth element. We can also use negative indices to access the elements from the end of the list. The last element has an index of -1, the second last has -2, and so on.

Example:

# Accessing elements of a list using positive indices
numbers = [1, 2, 3, 4, 5]
print(numbers[0]) # prints 1
print(numbers[2]) # prints 3
print(numbers[4]) # prints 5
# Accessing elements of a list using negative indices
fruits = ['apple', 'banana', 'orange', 'mango']
print(fruits[-1]) # prints mango
print(fruits[-3]) # prints banana
print(fruits[-4]) # prints apple

Output:

1
3
5
mango
banana
apple

We can also slice a list using the colon (:) operator. The syntax is list[start🔚step], where start is the starting index (inclusive), end is the ending index (exclusive), and step is the increment value. If any of these parameters are omitted, they take default values as follows: start = 0, end = length of list, step = 1.

Nonlinear Data Structures

Nonlinear data structures are those that store data in a non-sequential manner, such that each element can have multiple predecessors or successors. Some examples of nonlinear data structures are trees, graphs, hash maps, etc.

Stacks

Stacks are linear data structures that follow the principle of "Last-in, first-out" (LIFO). This means that the last element that was inserted into the stack is the first one that can be removed from it. Stacks are useful for implementing recursive algorithms, undo operations, backtracking, etc.

Python does not have a built-in stack data type, but we can use lists or deques to implement stacks. Lists are simple and fast, but they have a fixed size limit. Deques are more flexible and efficient, but they require importing the collections module.

Example:

# Using list as a stack
stack = []
# Pushing elements into the stack
stack.append('a')
stack.append('b')
stack.append('c')
print(stack)
# Popping elements from the stack
print(stack.pop()) # prints 'c'
print(stack.pop()) # prints 'b'
print(stack.pop()) # prints 'a'
print(stack) # prints []

Output:

['a', 'b', 'c']
c
b
a
[]

# Using deque as a stack
from collections import deque
stack = deque()
# Pushing elements into the stack
stack.append('a')
stack.append('b')
stack.append('c')
print(stack)
# Popping elements from the stack
print(stack.pop()) # prints 'c'
print(stack.pop()) # prints 'b'
print(stack.pop()) # prints 'a'
print(stack) # prints deque([])

Output:

deque(['a', 'b', 'c'])
c
b
a
deque([])

Queues

Queues are linear data structures that follow the principle of "First-in, first-out" (FIFO). This means that the first element that was inserted into the queue is the first one that can be removed from it. Queues are useful for implementing scheduling algorithms, buffering, caching, etc.

Python does not have a built-in queue data type, but we can use lists or deques to implement queues. Lists are simple but slow, as they require shifting all elements when inserting or deleting from the front. Deques are more efficient and fast, as they allow inserting and deleting from both ends.

Deques

Deques are double-ended queues that allow inserting and deleting from both ends. Deques are useful for implementing sliding window algorithms, undo-redo operations, palindromes, etc.

Python provides a built-in deque data type in the collections module. We can create deques using the deque() function and pass an iterable as an argument. We can also specify a maximum length for the deque, which will discard old elements when new ones are added.

Example:

# Importing deque from collections module
from collections import deque
# Creating a deque with an iterable
dq = deque(['a', 'b', 'c'])
print(dq)
# Creating a deque with a maximum length
dq = deque(maxlen=3)
dq.append(1)
dq.append(2)
dq.append(3)
print(dq)
dq.append(4)
print(dq) # 1 is discarded

Output:

deque(['a', 'b', 'c'])
deque([1, 2, 3], maxlen=3)
deque([2, 3, 4], maxlen=3)

We can use various methods to manipulate deques, such as append(), appendleft(), pop(), popleft(), extend(), extendleft(), rotate(), etc.

Example:

# Importing deque from collections module
from collections import deque
# Creating a deque with an iterable
dq = deque(['a', 'b', 'c'])
print(dq)
# Appending elements to the right
dq.append('d')
dq.append('e')
print(dq)
# Appending elements to the left
dq.appendleft('x')
dq.appendleft('y')
print(dq)
# Popping elements from the right
dq.pop()
dq.pop()
print(dq)
# Popping elements from the left
dq.popleft()
dq.popleft()
print(dq)
# Extending elements to the right
dq.extend(['f', 'g', 'h'])
print(dq)
# Extending elements to the left
dq.extendleft(['w', 'v', 'u'])
print(dq)
# Rotating elements by n steps
dq.rotate(2) # positive n means rotate right
print(dq)
dq.rotate(-4) # negative n means rotate left
print(dq)

Output:

deque(['a', 'b', 'c'])
deque(['a', 'b', 'c', 'd', 'e'])
deque(['y', 'x', 'a', 'b', 'c', 'd', 'e'])
deque(['y', 'x', 'a', 'b', 'c'])
deque(['a', 'b', 'c'])
deque(['a', 'b', 'c', 'f', 'g', 'h'])
deque(['u', 'v', 'w', 'a', 'b', 'c', 'f', 'g', 'h'])
deque(['f', 'g', 'h', 'u', 'v', 'w', 'a', 'b', 'c'])
deque(['v', 'w', 'a', 'b' ,'c' ,'f' ,'g' ,'h' ,'u'])

Trees

Trees are nonlinear data structures that represent hierarchical relationships among data. Trees consist of nodes that store data and have links to other nodes called children. The node at the top of the tree is called the root, and the nodes at the bottom are called leaves. The nodes that have the same parent are called siblings. The length of the path from the root to any node is called its depth or level. The height of a tree is the maximum depth of any node.

Python does not have a built-in tree data type, but we can create our own tree class using objects. We can also use lists or dictionaries to represent trees.

What are Algorithms?

Algorithms are step-by-step procedures or rules for solving a problem or accomplishing a task. Algorithms can be expressed in various ways, such as natural language, pseudocode, flowcharts, or programming languages. Algorithms are often used to manipulate data structures, such as sorting, searching, inserting, deleting, etc.

Python provides built-in functions and modules for some common algorithms, such as sorted(), bisect(), heapq(), etc. We can also implement our own algorithms using Python code. Algorithms can be classified into different types based on their design techniques, complexity, or application domains. Some examples of algorithm types are:

• Sorting algorithms: These are algorithms that arrange data in a certain order, such as ascending or descending.
• Searching algorithms: These are algorithms that find an element or a set of elements in a data structure that satisfy some criteria.
• Divide and conquer algorithms: These are algorithms that break a problem into smaller subproblems, solve them recursively, and combine their solutions.
• Greedy algorithms: These are algorithms that make locally optimal choices at each step, hoping to find a global optimum.
• Dynamic programming algorithms: These are algorithms that solve complex problems by breaking them into overlapping subproblems and storing their solutions in a table.
• Recursion algorithms: These are algorithms that call themselves repeatedly until a base case is reached.

In this article, we will focus on some of the most common sorting and searching algorithms in Python.

Bubble Sort Algorithm

Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm passes through the list multiple times until no swaps are needed, which means the list is sorted. The name bubble sort comes from the fact that smaller or larger elements bubble up to their positions with each pass.

The algorithm can be implemented as follows:

• Start from the first element of the list and compare it with the next element.
• If the first element is greater than the second element, swap them.
• Move to the next pair of elements and repeat step 2.
• Continue this process until you reach the end of the list. This completes one pass.
• Repeat steps 1 to 4 until no swaps are made in a pass. This means the list is sorted.

Source: Programiz

The following code shows how to implement bubble sort in python:

# Bubble sort in python
def bubble_sort(array):
  # loop through each element of array
  for i in range(len(array)):
    # keep track of swapping
    swapped = False
    # loop to compare array elements
    for j in range(0, len(array) - i - 1):
      # compare two adjacent elements
      # change > to < to sort in descending order
      if array[j] > array[j + 1]:
        # swapping occurs if elements
        # are not in the intended order
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp
        swapped = True
    # no swapping means the array is already sorted
    # so no need for further comparison
    if not swapped:
      break
data = [-2, 45, 0, 11, -9]
bubble_sort(data)
print('Sorted Array in Ascending Order:')
print(data)

Output:

Sorted Array in Ascending Order:
[-9, -2, 0, 11, 45]

The time complexity of bubble sort is O(n^2) in the worst case, when the list is reverse sorted. The best case time complexity is O(n) when the list is already sorted. The space complexity is O(1) as no extra space is required.

Selection Sort Algorithm

Selection sort is another simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the list and putting it at the beginning. The algorithm maintains two sublists in a given list: one that is already sorted and one that is unsorted. In each iteration, the minimum element from the unsorted sublist is selected and moved to the sorted sublist.

The algorithm can be implemented as follows:

• Start from the first element of the list and assume it as the minimum.
• Compare it with each element of the list until you find a smaller element.
• If a smaller element is found, swap it with the current minimum.
• Move to the next element of the list and repeat steps 2 and 3.
• Continue this process until all elements are placed in their correct positions.

Source: Programiz

The following code shows how to implement selection sort in python:

# Selection sort in python
def selection_sort(array, size):
  # loop through each element of array
  for step in range(size):
    # set current element as minimum
    min_idx = step
    # loop to compare current element with remaining elements
    for i in range(step + 1, size):
      # change < to > to sort in descending order
      if array[i] < array[min_idx]:
        # update minimum index with current index
        min_idx = i
    # swap minimum element with current element
    (array[step], array[min_idx]) = (array[min_idx], array[step])
data = [-2, 45, 0, 11, -9]
size = len(data)
selection_sort(data, size)
print('Sorted Array in Ascending Order:')
print(data)

Output:

Sorted Array in Ascending Order:
[-9, -2, 0, 11, 45]

The time complexity of selection sort is O(n^2) in all cases, as there are two nested loops that run n times each. The space complexity is O(1) as no extra space is required.

Insertion Sort Algorithm

Insertion sort is another simple sorting algorithm that works by inserting each element from the unsorted part of the list into its correct position in the sorted part of the list. The algorithm assumes that the first element of the list is already sorted and then compares each subsequent element with the elements in the sorted part, shifting them to make space for the new element.

The algorithm can be implemented as follows:

• Start from the second element of the list and store it in a variable called key.
• Compare key with each element in the sorted part, starting from the rightmost element.
• If key is smaller than an element in the sorted part, shift that element to the right by one position.
• Repeat step 3 until you find an element that is smaller than or equal to key or you reach the beginning of the list.
• Insert key into its correct position.
• Move to the next element of the list and repeat steps 2 to 5.
• Continue this process until all elements are placed in their correct positions.

Source: GeeksforGeeks

The following code shows how to implement insertion sort in python:

# Insertion sort in python
def insertion_sort(array):
  # loop through each element of array, starting from second element
  for i in range(1, len(array)):
    # store current element as key
    key = array[i]
    # set j as index of previous element
    j = i - 1
    # loop through sorted part, starting from rightmost element
    while j >= 0 and key < array[j]:
      # shift element to right if it is larger than key
      array[j + 1] = array[j]
      # decrement j by one
      j = j - 1
    # insert key into its correct position
    array[j + 1] = key
data = [-2, 45, 0, 11, -9]
insertion_sort(data)
print('Sorted Array in Ascending Order:')
print(data)

Output:

Sorted Array in Ascending Order:
[-9, -2, 0, 11, 45]

The time complexity of insertion sort is O(n^2) in the worst case, when the list is reverse sorted. The best case time complexity is O(n) when the list is already sorted. The space complexity is O(1) as no extra space is required.

Merge Sort Algorithm

Merge sort is a divide and conquer sorting algorithm that works by recursively dividing the list into smaller sublists until they have one element each, and then merging them back together in sorted order. The algorithm uses a helper function called merge that takes two sorted sublists and merges them into one sorted list.

The algorithm can be implemented as follows:

• Check if the list has zero or one element. If yes, return the list as it is already sorted.
• Find the middle index of the list and split it into two sublists: left and right.
• Recursively call merge sort on both sublists.
• Merge the sorted sublists using the merge function.

Source: EDUCBA

The following code shows how to implement merge sort in python:

# Merge sort in python
def merge_sort(array):
  # check if array has zero or one element
  if len(array) <= 1:
    return array
  # find middle index of array
  mid = len(array) // 2
  # split array into left and right sublists
  left = array[:mid]
  right = array[mid:]
  # recursively call merge sort on both sublists
  left = merge_sort(left)
  right = merge_sort(right)
  # merge the sorted sublists using merge function
  return merge(left, right)

def merge(left, right):
  # initialize an empty list to store merged elements
  result = []
  # initialize two pointers for left and right sublists
  i = j = 0
  # loop until one of the sublists is exhausted
  while i < len(left) and j < len(right):
    # compare elements from left and right sublists
    # append smaller element to result list
    if left[i] < right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1
  # append remaining elements from left sublist, if any
  result.extend(left[i:])
  # append remaining elements from right sublist, if any
  result.extend(right[j:])
  # return merged list
  return result
data = [-2, 45, 0, 11, -9]
sorted_data = merge_sort(data)
print('Sorted Array in Ascending Order:')
print(sorted_data)

Output:

Sorted Array in Ascending Order:
[-9, -2, 0, 11, 45]

The time complexity of merge sort is O(n log n) in all cases, as there are log n levels of recursion and each level takes O(n) time to merge. The space complexity is O(n) as an extra space is required for merging.

Quick Sort Algorithm

Quick sort is a divide and conquer sorting algorithm that works by choosing a pivot element from the list and partitioning the list around the pivot, such that all elements less than or equal to the pivot are on its left and all elements greater than the pivot are on its right. The algorithm then recursively applies the same process to the left and right sublists until the entire list is sorted.

The algorithm can be implemented as follows:

• Check if the list has zero or one element. If yes, return the list as it is already sorted.
• Choose any element from the list as the pivot element. Usually, we choose the first or last element as the pivot.
• Create two empty lists, left and right.
• For each element in the list except for the pivot:
  • If the element is smaller than or equal to the pivot, add it to the left list.
  • If the element is greater than the pivot, add it to the right list.
• Recursively call quick sort on both left and right lists.
• Concatenate the sorted left list, the pivot element, and the sorted right list.

Source: Khan Academy

The following code shows how to implement quick sort in python:

# Quick sort in python
def quick_sort(array):
  # check if array has zero or one element
  if len(array) <= 1:
    return array
  # choose last element as pivot
  pivot = array[-1]
  # create two empty lists for left and right sublists
  left = []
  right = []
  # loop through each element except for pivot
  for i in range(len(array) - 1):
    # if element is smaller than or equal to pivot, add it to left list
    if array[i] <= pivot:
      left.append(array[i])
    # if element is greater than pivot, add it to right list
    else:
      right.append(array[i])
  # recursively call quick sort on both sublists and concatenate them with pivot
  return quick_sort(left) + [pivot] + quick_sort(right)
data = [-2, 45, 0, 11, -9]
sorted_data = quick_sort(data)
print('Sorted Array in Ascending Order:')
print(sorted_data)

Output:

Sorted Array in Ascending Order:
[-9, -2, 0, 11, 45]

The time complexity of quick sort is O(n log n) in average case, as there are log n levels of recursion and each level takes O(n) time to partition. The worst case time complexity is O(n^2) when the list is already sorted or reverse sorted. The space complexity is O(log n) as an extra space is required for recursion.

Heap Sort Algorithm

Heap sort is a comparison-based sorting algorithm that works by using a binary heap data structure. A binary heap is a complete binary tree where each node has a value less than or equal to its children (min-heap) or greater than or equal to its children (max-heap). Heap sort uses a max-heap to sort an array in ascending order or a min-heap to sort an array in descending order.

The algorithm can be implemented as follows:

• Convert the input array into a max-heap or a min-heap using a heapify function.
• Swap the root element of the heap with the last element of the heap and reduce the size of the heap by one.
• Call the heapify function on the root element to restore the heap property.
• Repeat steps 2 and 3 until the heap size becomes one or zero.

Source: Stack Abuse

The following code shows how to implement heap sort in python:

# Heap sort in python
def heapify(array, n, i):
  # find largest among root and children
  largest = i
  left = 2 * i + 1
  right = 2 * i + 2
  if left < n and array[i] < array[left]:
    largest = left
  if right < n and array[largest] < array[right]:
    largest = right
  # if root is not largest, swap with largest and continue heapifying
  if largest != i:
    array[i], array[largest] = array[largest], array[i]
    heapify(array, n, largest)
def heap_sort(array):
  n = len(array)
  # create max-heap from array
  for i in range(n//2, -1, -1):
    heapify(array, n, i)
  # swap root with last element and reduce size of heap by one
  for i in range(n - 1, 0, -1):
    array[i], array[0] = array[0], array[i]
    # restore max-heap property after each swap
    heapify(array, i, 0)
data = [-2, 45, 0, 11, -9]
heap_sort(data)
print('Sorted Array in Ascending Order:')
print(data)

Output:

Sorted Array in Ascending Order:
[-9, -2, 0, 11, 45]

The time complexity of heap sort is O(n log n) in all cases, as there are log n levels of recursion and each level takes O(n) time to build or restore the heap. The space complexity is O(1) as no extra space is required.

Counting Sort Algorithm

Counting sort is a non-comparison-based sorting algorithm that works by counting the number of occurrences of each distinct element in an array or list. It then uses that information to determine the position of each element in a sorted output array or list. Counting sort is a stable algorithm, meaning that it preserves the relative order of elements with equal values.

The algorithm can be implemented as follows:

• Find the maximum element in the input array or list and create a count array or list of size equal to max + 1, where max is the maximum element. Initialize all elements of the count array or list to zero.
• Traverse through each element of the input array or list and increment its corresponding count by one.
• Modify the count array or list by adding up each element with its previous element, such that each element now stores the cumulative sum of its previous elements.
• Create an output array or list of size equal to the input array or list.
• Traverse through each element of the input array or list from right to left and place it at its correct position in the output array or list using the count array or list. Decrement its corresponding count by one.

Source: FavTutor

The following code shows how to implement counting sort in python:

# Counting sort in python
def counting_sort(array):
  # find maximum element in array
  max_element = max(array)
  # create count array of size max + 1 and initialize with zeros
  count = [0] * (max_element + 1)
  # traverse through each element in array and increment its count by one
  for i in range(len(array)):
    count[array[i]] += 1
  # modify count array by adding up each element with its previous element
  for i in range(1, len(count)):
    count[i] += count[i - 1]
  # create output array of size equal to input array
  output = [0] * len(array)
  # traverse through each element in array from right to left
  for i in range(len(array) - 1, -1, -1):
    # place element at its correct position in output array using count array
    output[count[array[i]] - 1] = array[i]
    # decrement its corresponding count by one
    count[array[i]] -= 1
  # return sorted output array
  return output
data = [-2, 45, 0, 11, -9]
sorted_data = counting_sort(data)
print('Sorted Array in Ascending Order:')
print(sorted_data)

Output:

Sorted Array in Ascending Order:
[-9, -2, 0, 11, 45]

The time complexity of counting sort is O(n + k), where n is the number of elements in the input array or list and k is the range of input values. The space complexity is O(n + k) as well, as an extra space is required for count and output arrays or lists.

Radix Sort Algorithm

Radix sort is a non-comparison-based sorting algorithm that works by sorting the elements of an array or list based on their individual digits from least significant to most significant. The algorithm uses a helper sorting technique called counting sort to sort the elements according to each digit. Radix sort is a stable algorithm, meaning that it preserves the relative order of elements with equal values.

The algorithm can be implemented as follows:

• Find the maximum element in the input array or list and determine its number of digits, which will be the number of iterations for sorting.
• Create a count array or list of size 10, which will store the number of occurrences of each digit from 0 to 9.
• For each iteration from 0 to number of digits - 1:
  • Initialize all elements of count array or list to zero.
  • Traverse through each element of the input array or list and increment its corresponding count by one based on its current digit.
  • Modify the count array or list by adding up each element with its previous element, such that each element now stores the cumulative sum of its previous elements.
  • Create an output array or list of size equal to the input array or list.
  • Traverse through each element of the input array or list from right to left and place it at its correct position in the output array or list using the count array or list. Decrement its corresponding count by one.
  • Copy the output array or list to the input array or list for next iteration.
  • Increase the current digit by multiplying it by 10.

Source: Programiz

The following code shows how to implement radix sort in python:

# Radix sort in python
def counting_sort(array, place):
  size = len(array)
  output = [0] * size
  count = [0] * 10
  # Calculate count of elements
  for i in range(0, size):
    index = array[i] // place
    count[index % 10] += 1
  # Calculate cumulative count
  for i in range(1, 10):
    count[i] += count[i - 1]
  # Place the elements in sorted order
  i = size - 1
  while i >= 0:
    index = array[i] // place
    output[count[index % 10] - 1] = array[i]
    count[index % 10] -= 1
    i -= 1
  for i in range(0, size):
    array[i] = output[i]
def radix_sort(array):
  # Get maximum element
  max_element = max(array)
  # Apply counting sort to sort elements based on place value.
  place = 1
  while max_element // place > 0:
    counting_sort(array, place)
    place *= 10
data = [-2, 45, 0, 11, -9]
sorted_data = radix_sort(data)
print('Sorted Array in Ascending Order:')
print(sorted_data)

Output:

Sorted Array in Ascending Order:
[-9, -2, 0, 11, 45]

The time complexity of radix sort is O(d * (n + b)), where d is the number of digits in the maximum element, n is the number of elements in the input array or list, and b is the base or range of input values (10 for decimal system). The space complexity is O(n + b) as an extra space is required for count and output arrays or lists.

Bucket Sort Algorithm

Bucket sort is a non-comparison-based sorting algorithm that works by dividing the elements of an array or list into several buckets or bins, each of which is sorted individually using another sorting technique, such as insertion sort. Bucket sort is useful when the input is uniformly distributed over a range, such as floating point numbers between 0 and 1.

The algorithm can be implemented as follows:

• Determine the number of buckets or bins to use, which can be equal to the number of elements in the input array or list, or any other value depending on the distribution of input values.
• Create an empty list of buckets or bins.
• For each element in the input array or list, calculate its bucket or bin index by multiplying its value by the number of buckets or bins and taking the floor of the result. Then, append the element to its corresponding bucket or bin.
• For each non-empty bucket or bin, sort its elements using another sorting technique, such as insertion sort.
• Concatenate all sorted buckets or bins into a single output array or list.

Source: Stack Abuse

The following code shows how to implement bucket sort in python:

# Bucket sort in python
def bucket_sort(array):
  # Determine number of buckets or bins
def bucket_sort(array):
  # Determine number of buckets or bins
  num_buckets = len(array)
  # Create an empty list of buckets or bins
  buckets = []
  for i in range(num_buckets):
    buckets.append([])
  # For each element in array, calculate its bucket index and append it to its bucket
  for element in array:
    bucket_index = int(element * num_buckets)
    buckets[bucket_index].append(element)
  # For each non-empty bucket, sort its elements using insertion sort
  for i in range(num_buckets):
    if len(buckets[i]) > 0:
      insertion_sort(buckets[i])
  # Concatenate all sorted buckets into a single output array
  output = []
  for i in range(num_buckets):
    output.extend(buckets[i])
  return output
# Helper function for insertion sort
def insertion_sort(array):
  for i in range(1, len(array)):
    key = array[i]
    j = i - 1
    while j >= 0 and key < array[j]:
      array[j + 1] = array[j]
      j -= 1
    array[j + 1] = key
data = [0.49, 5.9, 3.4, 1.11, 4.5, 6.6, 2.0]
sorted_data = bucket_sort(data)
print('Sorted Array in Ascending Order:')
print(sorted_data)

Output:

Sorted Array in Ascending Order:
[0.49, 1.11, 2.0, 3.4, 4.5, 5.9, 6.6]

The time complexity of bucket sort is O(n + k), where n is the number of elements in the input array or list, and k is the number of buckets or bins. The O(n) term comes from distributing the elements into buckets or bins, and concatenating them into a single output array or list. The O(k) term comes from sorting each non-empty bucket or bin using another sorting technique, such as insertion sort. The space complexity is O(n + k) as well, as an extra space is required for buckets or bins and output array or list.

Shell Sort Algorithm

Shell sort is a comparison-based sorting algorithm that works by dividing the elements of an array or list into several subarrays or sublists, each of which is sorted individually using insertion sort. Shell sort is a generalization of insertion sort that allows exchanging elements that are far apart from each other, thus reducing the number of comparisons and movements. Shell sort is also known as diminishing increment sort.

The algorithm can be implemented as follows:

• Choose a gap sequence, which is a series of numbers that represent the intervals between the elements to be compared and sorted. A common gap sequence is N/2, N/4, ..., 1, where N is the size of the array or list.
• For each gap in the gap sequence, perform insertion sort on the elements that are separated by that gap. This means that for each gap, there are gap subarrays or sublists that are sorted independently.
• Repeat this process until the gap is 1, which means that the whole array or list is sorted.

Source: Programiz

The following code shows how to implement shell sort in python:

# Shell sort in python
def shell_sort(array):
  # Choose a gap sequence (N/2, N/4, ..., 1)
  n = len(array)
  gap = n // 2
  # For each gap in the sequence
  while gap > 0:
    # Perform insertion sort on elements separated by gap
    for i in range(gap, n):
      temp = array[i]
      j = i
      # Shift elements until correct position is found
      while j >= gap and array[j - gap] > temp:
        array[j] = array[j - gap]
        j -= gap
      # Put temp in its correct position
      array[j] = temp
    # Reduce gap by half
    gap //= 2
  return array
data = [9, 8, 3, 7, 5, 6, 4, 1]
sorted_data = shell_sort(data)
print('Sorted Array in Ascending Order:')
print(sorted_data)

Output:

Sorted Array in Ascending Order:
[1, 3, 4, 5, 6, 7, 8, 9]

The time complexity of shell sort depends on the choice of gap sequence. The worst case time complexity is O(n^2), which happens when the gap sequence is N/2, N/4, ..., 1. The best case time complexity is O(n log n), which happens when the gap sequence is based on powers of two (such as Sedgewick's increments). The average case time complexity is hard to determine, but it is usually better than O(n^2). The space complexity is O(1) as no extra space is required.

I hope you enjoyed this post and learned something new. If you want to learn more about data structures and algorithms with Python, check out my other posts on this topic. You can also subscribe to my newsletter to get updates on new posts and other resources. Thank you for reading!