04 Searching and Sorting

Lecture from: 10.10.2024 | Video: Videos ETHZ | Rui Zhangs Notes | Visualisations: VisualGo and Toptal | Official Script

Searching

Given an array A[1..n] containing numbers and a target number b, our goal is to find the index k such that A[k] = b.

Case 1: Linear Search (Unsorted Arrays)

• Algorithm: In linear search, we traverse each element in the array sequentially until we find the target value b.
• Time Complexity: $O(n)$. In the worst case, we need to examine every element. This makes linear search inefficient for large arrays.

Implementation Example:

public static int linearSearch(int[] arr, int b) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == b) {
            return i; // Found it!
        }
    }
    return -1; // Not found in the array
}

Geht es besser?

No, but how would we prove that. The core idea is to show that any algorithm attempting to search an unsorted array must, in the worst case, perform at least n operations.

We can demonstrate this by focusing on a specific scenario: what if the target element b is not present in the array A?

If b isn’t in the array, any algorithm needs to check every single element to definitively say “b is not here.” This means it must perform at least one operation (comparison, look-up, etc.) for each element.

Case 2: Binary Search (Sorted Arrays)

• Pre-requisite: The input array A must be sorted in ascending order for binary search to work correctly.
• Algorithm: Binary search exploits the sorted nature of the array. It repeatedly divides the search interval in half. If the middle element is equal to the target, we’ve found it! Otherwise, we discard half the array based on whether the target is less than or greater than the middle element and continue searching in the remaining half.
• Time Complexity: O(log n). The search space halves with each comparison, leading to a significantly faster search for large arrays.

Implementation Example:

public static int binarySearch(int[] arr, int b) {
    int low = 0;
    int high = arr.length - 1;
 
    while (low <= high) {
        int mid = low + (high - low) / 2; // Calculate mid to avoid overflow
 
        if (arr[mid] == b) {
            return mid; // Found it!
        } else if (arr[mid] < b) {
            low = mid + 1; // Search the right half
        } else {
            high = mid - 1; // Search the left half
        }
    }
    return -1; // Not found in the array
}

Geht es besser

Now this is a fairly tough question to answer. If we want to prove that there is no better way, then we’d have to prove that for all algorithms even the ones not invented until now, there isn’t one that could possibly be better.

Every comparison-based search algorithm can be visualized as a decision tree. Each node in this tree represents a comparison, and the branches emanating from each node correspond to the possible outcomes of that comparison (e.g., “target is greater” or “target is smaller”). The leaves of the tree represent all possible final results – finding the target element or determining its absence.

Crucially, for any algorithm to be considered correct, it must account for every possible input. This means that our decision tree must have at least n+1 leaves, representing each element’s potential index and the case where the target is not found.

The depth of this decision tree directly corresponds to the worst-case number of comparisons an algorithm requires. To achieve n+1 leaves, the tree must have a minimum of $n+1=1+2+4+\cdots =2^{H+1}-1$ nodes, where $H$ is the height of the tree. This leads us to:

• $n+1\le \text{No. Knoten}\le 1+2+4+\cdots =2^{H+1}-1$
• ${\log }_2(n+1)\le H+1$
• $H\ge {\log }_2(n+1)-1=\Omega (\log n)$

This is an information theoretical argument.

Sorting

The input is an array (or list) named A containing n numbers. These numbers can be of various data types (integers, floats, etc.)

The output is a new permutation of the original array A, where the elements are arranged in non-decreasing order: $A[1]\le A[2]\le ...\le A[n]$. This means the smallest element is at index 1, the next smallest at index 2, and so on.

Bubble Sort

Let’s dive into Bubble Sort – a simple yet fundamental sorting algorithm.

How Bubble Sort Works:

1. Repeated Passes: Bubble sort operates by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order.

2. The “Bubbling” Effect: Larger elements gradually “bubble up” to their correct positions at the end of the list with each pass.

3. Sorted Subarrays: After each pass, the largest element in the unsorted portion is placed in its final position. The sorted portion of the list grows with each iteration.

Pseudocode Example:

function bubbleSort(A):
  n = length(A)
  for i = 1 to n-1:
    for j = 1 to n-i:
      if A[j] > A[j+1]:
        swap(A[j], A[j+1])
  return A

Visualisation:

Imagine you have a list of numbers and you’re repeatedly comparing adjacent elements. If they are out of order, you swap them. This process continues until the entire list is sorted.

Time Complexity:

• Best Case: $O(n)$ – If the array is already sorted, only one pass is needed to verify the order.
• Average Case: $O(n^2)$ – In most cases, multiple passes are required to bring all elements into their correct positions.
• Worst Case: $O(n^2)$ – Occurs when the input array is in reverse sorted order.

Space Complexity: $O(1)$ – Bubble sort sorts in-place, requiring only a constant amount of additional memory.

Why does it work?

The key insight is that each pass of Bubble Sort places the largest unsorted element in its correct position at the end of the array. To formally demonstrate why n passes are necessary, we can consider:

1. Initial State: The array begins in a potentially unsorted state with n elements.
2. Iterative Process: In each pass (iteration) of the outer loop, we compare adjacent elements and swap them if out of order. This ensures that the largest element within the unsorted portion is “bubbled” to its final position at the end.
3. Sorted Subarray Growth: After each pass, a single element is definitively placed in its correct sorted position. The subarray containing already sorted elements grows by one with each iteration.
4. Termination Condition: This process continues until the entire array has been iterated over n times. At this point, every element has been compared and swapped as necessary, resulting in a fully sorted array.

Consider the worst-case scenario: The input array is in reverse sorted order. In this situation, each pass requires n-1 comparisons and swaps to bring the largest unsorted element (which is initially at index 1) to its correct position (index n). Therefore, a minimum of n passes are required to fully sort the array.

Formal Analysis with Invariant:

Invariant: At the end of each pass in Bubble Sort, the largest unsorted element is guaranteed to be in its correct sorted position at the end of the array. This property acts as an invariant throughout the algorithm’s execution.

1. Initial State: The array begins in a potentially unsorted state with n elements.
2. Iterative Process: Each pass of the outer loop compares adjacent elements and swaps them if out of order. This process, guided by the invariant, ensures that the largest unsorted element “bubbles” to its correct position at the end of the array.
3. Sorted Subarray Growth: After each pass, a single element is definitively placed in its correct sorted position. The subarray containing already sorted elements grows by one with each iteration. This growth directly corresponds to the invariant holding true for each subsequent pass – the largest unsorted element is guaranteed to be in place.
4. Termination Condition: This process continues until the entire array has been iterated over n times. At this point, every element has had its chance to “bubble” up and reach its final sorted position, resulting in a fully sorted array. The invariant ensures that with each pass, we are making consistent progress towards the final sorted state.

The worst-case scenario (array in reverse sorted order) demonstrates why n passes are necessary: After n-1 passes, all but one element will be correctly placed. The last remaining unsorted element requires a single pass to reach its correct position.

…Geht es besser?…

Let us try to create a new algorithm using the same invariant.

Selection Sort

Last time we examined Bubble Sort and its reliance on the crucial invariant: At the end of each pass, the largest unsorted element is guaranteed to be in its correct sorted position at the end of the array. This concept will serve as a foundation for understanding Selection Sort.

Instead of repeatedly moving elements towards their final positions like Bubble Sort, Selection Sort adopts a different strategy:

1. Finding the Maximum: In each pass, we identify the largest element within the unsorted portion of the array. This is akin to “selecting” the maximum value.
2. Swap and Advance: The identified largest element is then swapped with the element at the end of the unsorted subarray (index n-i-1).

Understanding the Progression:

• Imagine a partially sorted array. With each pass of Selection Sort, we essentially “fill in” the next correct position with the maximum remaining value.
• The sorted subarray at the end expands one element at a time.

Why n Passes?

To guarantee that every element is placed in its correct position, we need to perform n passes. In each pass, we locate and swap the largest element from the unsorted portion, ensuring that by the end of n passes, the entire array is sorted.

Key Difference: Bubble sort iteratively moves elements towards their final positions, while Selection Sort swaps only the maximum value with its designated place.

Insertion Sort, Merge Sort (MIT)

Insertion Sort

For this algorithm we are going to be thinking of a different and much simpler and natural invariant.

Insertion Sort is another simple sorting algorithm that builds the sorted list one element at a time. The algorithm iterates over the array, and at each step, it inserts the current element into its correct position in the already sorted part of the array.

The invariant we’ll maintain in Insertion Sort is:

In other words, after each iteration, the subarray from $A[1]$ to $A[j]$ is already sorted.

How Insertion Sort Works:

1. Iterate through the array: For each element in the array (starting from the second element), insert it into its correct position in the already sorted part of the array.
2. Shifting Elements: Inserting an element might involve shifting larger elements one position to the right to make space for the new element.
3. Place the element: Once the correct position is found, place the current element there.

Pseudocode:

for j = 1 to n-1:
    x = A[j]
    # Use binary search to find the position k where A[j] belongs
    k = binarySearch(A, 0, j-1, x)
    # Shift the elements to the right to make room for A[j]
    for i = j-1 down to k:
        A[i + 1] = A[i]
    A[k] = x

Runtime

Comparisons: For the binary search part $c\log (j-1)$ comparisons are required. We need to do this n times. Therefore:

Switchings of Elements:

In the worst case we need to switch (we are using an array, not an linked list) n times and repeat that n times → $O(n^2)$.

Merge Sort

For this algorithm we are going to be thinking of a divide and conquer type invariant.

Merge Sort is a divide and conquer sorting algorithm. It works by recursively splitting the array into smaller subarrays, sorting those subarrays, and then merging them back together in sorted order. This results in an efficient time complexity of $O(n\log n)$.

The correct invariant in Merge Sort is:

This means that after the recursive sorting step, the subarray from left to mid and the subarray from mid+1 to right are each sorted individually. The merge step then combines these two sorted subarrays into a single sorted subarray.

How Merge Sort Works:

1. Divide: Recursively split the array into two halves until each subarray contains a single element (base case).
2. Conquer: Recursively sort the left and right halves.
3. Merge: Combine the two sorted halves into one sorted array.

Pseudocode:

function mergeSort(A, l, r):
    if l < r:
        mid = (l + r) // 2
        mergeSort(A, l, mid)       # Sort left half
        mergeSort(A, mid + 1, r)   # Sort right half
        merge(A, l, mid, r)        # Merge the two sorted halves
 
function merge(A, l, mid, r):
    left_part = A[l:mid+1]
    right_part = A[mid+1:r+1]
    
    i = j = 0
    k = l
    # Merge the sorted subarrays back into A[l..r]
    while i < len(left_part) and j < len(right_part):
        if left_part[i] <= right_part[j]:
            A[k] = left_part[i]
            i += 1
        else:
            A[k] = right_part[j]
            j += 1
        k += 1
    
    # Copy any remaining elements from left_part
    while i < len(left_part):
        A[k] = left_part[i]
        i += 1
        k += 1
    
    # Copy any remaining elements from right_part
    while j < len(right_part):
        A[k] = right_part[j]
        j += 1
        k += 1

Runtime

Time Complexity: Merge Sort operates by recursively splitting the array in half. Each level of recursion requires $O(n)$ time to merge the two halves back together. Since the array is divided in half at each step, the depth of recursion is $O(\log n)$. Thus, the overall time complexity is:

$T(n)=O(n\log n)$

Space Complexity: Merge Sort requires additional space to store the temporary subarrays during the merge process, leading to a space complexity of $O(n)$.

Why the Invariant Holds:

1. Base Case: When the subarray has a single element (i.e., $l=r$), it’s trivially sorted.
2. Inductive Step: Assuming that both $A[l..mid]$ and $A[mid+\mathrm{1..}r]$ are sorted after the recursive calls, the merge step ensures that $A[l..r]$ is sorted. Hence, the invariant holds throughout the algorithm’s execution.

Continue here: 05 Sorting, Data Structures