Code-Alongs

Sorting Algorithms Overview

In this code-along, we'll implement and analyze different sorting algorithms, focusing on their time complexity and practical applications.

Objectives

• Implement selection sort and understand its O(n²) time complexity
• Implement merge sort and understand its O(n log n) time complexity
• Compare the performance of different sorting algorithms
• Analyze when to use each sorting algorithm based on data characteristics

Selection Sort Implementation

Selection sort works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.

public static void selectionSort(int[] arr) {
    int n = arr.length;
    
    // One by one move boundary of unsorted subarray
    for (int i = 0; i < n - 1; i++) {
        // Find the minimum element in unsorted array
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        
        // Swap the found minimum element with the first element
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

Merge Sort Implementation

Merge sort is a divide and conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves.

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        // Find the middle point
        int mid = left + (right - left) / 2;
        
        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    // Find sizes of two subarrays to be merged
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // Create temp arrays
    int[] L = new int[n1];
    int[] R = new int[n2];
    
    // Copy data to temp arrays
    for (int i = 0; i < n1; ++i) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; ++j) {
        R[j] = arr[mid + 1 + j];
    }
    
    // Merge the temp arrays
    int i = 0, j = 0;
    int k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // Copy remaining elements of L[] if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    // Copy remaining elements of R[] if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Recursion Fundamentals

In this code-along, we'll explore recursion and implement various recursive algorithms to solve problems.

Objectives

• Understand the core concepts of recursion (base case and recursive case)
• Implement classic recursive algorithms like factorial and Fibonacci
• Analyze the time and space complexity of recursive solutions
• Compare recursive implementations with iterative alternatives

Factorial Implementation

The factorial function is a classic example of recursion, computing the product of all positive integers less than or equal to n.

public static int factorial(int n) {
    // Base case
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // Recursive case
    return n * factorial(n - 1);
}

Fibonacci Implementation

The Fibonacci sequence is another classic recursive problem, where each number is the sum of the two preceding ones.

public static int fibonacci(int n) {
    // Base cases
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Optimized Fibonacci with Memoization

A more efficient implementation using memoization to avoid redundant calculations.

public static int fibonacciMemoized(int n, int[] memo) {
    // Base cases
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // Check if already calculated
    if (memo[n] != 0) {
        return memo[n];
    }
    
    // Calculate and store result
    memo[n] = fibonacciMemoized(n - 1, memo) + fibonacciMemoized(n - 2, memo);
    return memo[n];
}