Algorithms

An algorithm is a finite set of instructions, used to solve a problem.

Note

In s1, only searching and sorting algorithms are discussed.

Searching algorithms

Iterative sequential search

def iterative_sequential_search(a_list, item):
    for i in range(len(a_list)):
        if a_list[i] == item:
            return i

    return -1

Recursive sequential search

def recursive_sequential_search(a_list, item, offset=0):
    if len(a_list) == offset - 1:
        return False

    if a_list[offset] == item:
        return True

    return recursive_sequential_search(a_list, item, offset+1)

Binary search

Works in a sorted array.

def binary_search(a_list, item):
    first = 0
    last = len(a_list) - 1
    found = False

    while first <= last and not found:
        mid = (first + last) // 2
        if a_list[mid] == item:
            found = True
        else:
            if item < a_list[mid]:
                last = mid - 1 # search in first half
            else:
                first = mid + 1 # search in second half

    if found:
        return mid
    else:
        return None

Time complexities

Algorithms	Best	Average	Worst
Sequential search	O(1)	O(n)	O(n)
Binary search	O(1)	O(log n)	O(log n)

Sorting algorithms

A sorting algorithm reorganizes a collection of items into some order as defined by values intrinsic to the items.

Properties

1. Number of swaps required
2. Number of comparisons - represented using “big-o” notation
3. Stability - it’s stable when relative order of the equal items are maintained.
4. Recursive or iterative
5. Amount of extra space

Bubble sort

Makes multiple passes through a collection and compare adjacent items to reorder those.

def bubble_sort(arr: list[int | float]):
    sorted_index_count = 0
    while sorted_index_count < len(arr):
        for i in range(len(arr)-sorted_index_count-1):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
        sorted_index_count += 1

Selection sort

Iterates through the list to find the smallest (or highest) value. Swaps its position with the first element. Then redo this starting from index 1. And repeat.

def selection_sort(arr):
    for current_starting_index in range(len(arr)):
        smallest_index = current_starting_index
        for i in range(current_starting_index + 1, len(arr)):
            if arr[i] < arr[smallest_index]:
                smallest_index = i
        arr[smallest_index], arr[current_starting_index] = arr[current_starting_index], arr[smallest_index]

Insertion sort

Maintains a sorted sublist in the lower positions in the list. Each item picked from the unsorted sublist is inserted into the sorted sublist.

def insertion_sort(a_list):
    start_index = 1
    while start_index < len(a_list):
        pointer = start_index
        while pointer > 0 and a_list[pointer - 1] > a_list[pointer]:
            # swap the position
            a_list[pointer], a_list[pointer -1] = \
                a_list[pointer-1], a_list[pointer]
            pointer -= 1
        start_index += 1

Shell sort

A specific “gap” is chosen. Start from any index (which is smaller than gap), and use insertion sort to sort the elements that are gap number of indices away. Redo this after reducing the gap. Repeat until the gap eventually becomes 1.

The performance depends on the sequence of gaps chosen.

# a modified version of insertion sort
def gap_insertion_sort(a_list, start_index, gap):
    while start_index < len(a_list):
        pointer = start_index
        while pointer >= gap and a_list[pointer - gap] > a_list[pointer]:
            # swap the position
            a_list[pointer], a_list[pointer - gap] = \
                a_list[pointer-gap], a_list[pointer]

            pointer -= gap
        start_index += gap


def shell_sort(a_list):
    for gap in range(4, 0, -1):
        for starting_index in range(0, gap):
            gap_insertion_sort(a_list, starting_index, gap)

Merge sort

Recursive algorithm that continually splits a list in half.

• If the list is empty or has one item, it is sorted
• If the list has more elements, the list is split in the middle and merge sort is recursively used on those parts
• Once sorted, the halves are combined to create a new, sorted list

def merge_sort(a_list):
    if len(a_list) < 2:  # then it's sorted
        return a_list

    # break at the middle and sort
    mid_index = len(a_list)//2
    left_half = merge_sort(a_list[:mid_index])
    right_half = merge_sort(a_list[mid_index:])

    # merge the sides
    cursor_left = 0
    cursor_right = 0
    sorted_list = []

    # merging step 1: loop through each side and add the smallest
    while cursor_left < len(left_half) and cursor_right < len(right_half):
        if left_half[cursor_left] > right_half[cursor_right]:
            sorted_list.append(right_half[cursor_right])
            cursor_right += 1
        else:
            sorted_list.append(left_half[cursor_left])
            cursor_left += 1

    # merging step 2: add left over items
    while cursor_left < len(left_half):
        sorted_list.append(left_half[cursor_left])
        cursor_left += 1
    while cursor_right < len(right_half):
        sorted_list.append(right_half[cursor_right])
        cursor_right += 1

    return sorted_list

Quick sort

Recursive algorithm that use the divide and conquer strategy to continually split a list around a selected value called the split point.

• Selects a pivot (a value in the list)
• List is partitioned into 2 parts
  • With the elements lesser than the pivot
  • With the elements greater than the pivot
• The partitions are recursively sorted

def quick_sort(a_list, first, last):
    if first < last:
        split_point = partition(a_list, first, last)
        quick_sort(a_list, first, split_point - 1)
        quick_sort(a_list, split_point + 1, last)

def partition(a_list, first, last):
    pivot_value = a_list[first]
    left_mark = first + 1
    right_mark = last
    done = False

    while not done:
        while left_mark <= right_mark and a_list[left_mark] <= pivot_value:
        left_mark = left_mark + 1

        while a_list[right_mark] >= pivot_value and right_mark >= left_mark:
            right_mark = right_mark - 1 36 / 46

            if right_mark < left_mark:
                done = True
            else:
                temp = a_list[left_mark]
                a_list[left_mark] = a_list[right_mark]
                a_list[right_mark] = temp

    temp = a_list[first]
    a_list[first] = a_list[right_mark]
    a_list[right_mark] = temp

    return right_mark

Heap sort

Uses a binary heap.

Similar to selection sort where a search is done to find the item with the minimum value and this item is placed at the beginning of the list. The same process is repeated for remaining items.

Steps:

1. A max-heap is built from the input data
2. Largest item is stored at the root of the heap. Replace it with the last item of the heap.
3. Size of the heap is reduced by 1
4. Heapify the root of the tree
5. Repeat steps 2-4 until the size of the heap is greater than 1.

The heapify procedure can be applied to a node only if its children nodes are heapified. So the heapification must be performed in the bottom-up order.

# To heapify subtree rooted at index i. Heap size is n.
def heapify(a_list, n, i):
  largest = i # Initialize largest as root
  l = 2 * i + 1 # left = 2*i + 1
  r = 2 * i + 2 # right = 2*i + 2

  # See if left child of root exists and is > root
  if l < n and a_list[i] < a_list[l]:
    largest = l

  # See if right child of root exists and is > root
  if r < n and a_list[largest] < a_list[r]:
    largest = r

  # Change root, if needed
  if largest != i:
    a_list[i],a_list[largest] = a_list[largest],a_list[i] # swap

    # Heapify the root.
    heapify(a_list, n, largest)

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

  # Build a maxheap. Since last parent will be
  # at ((n//2)-1) we can start at that location.
  for i in range(n // 2 - 1, -1, -1):
    heapify(a_list, n, i)

  # One by one extract elements
  for i in range(n-1, 0, -1):
    a_list[i], a_list[0] = a_list[0], a_list[i] # swap
    heapify(a_list, i, 0)

Time complexities

Algorithms	Best	Average	Worst
Bubble sort	O(n)	O(n^2)	O(n^2)
Selection sort	O(n^2)	O(n^2)	O(n^2)
Insertion sort	O(n)	O(n^2)	O(n^2)
Shell sort	O(n)	O((n log n)^2)	O((n log n)^2)
Merge sort	O(n log n)	O(n log n)	O(n log n)
Quick sort	O(n log n)	O(n log n)	O(n^2)
Heap sort	O(n log n)	O(n log n)	O(n log n)