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 Implementation and Analysis

In this code-along, we'll implement recursive solutions to several problems and analyze their performance characteristics.

Objectives

• Identify base cases and recursive cases in algorithm development
• Implement recursive algorithms for factorial, Fibonacci, and more complex problems
• Analyze the time and space complexity of recursive algorithms
• Compare recursive solutions with their iterative counterparts

Factorial Implementation

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

/**
 * Calculate factorial recursively
 * @param n The number to calculate factorial for
 * @return n!
 */
public static long factorial(int n) {
    // Base case
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // Recursive case
    return n * factorial(n - 1);
}

Recursive String Reversal

String reversal is another problem that can be solved elegantly with recursion.

/**
 * Reverse a string using recursion
 * @param str The string to reverse
 * @return The reversed string
 */
public static String reverseString(String str) {
    // Base case
    if (str.isEmpty() || str.length() == 1) {
        return str;
    }
    
    // Recursive case: first character goes to the end
    return reverseString(str.substring(1)) + str.charAt(0);
}

Recursive vs. Iterative Approaches

During this code-along, we'll explore the tradeoffs between recursive and iterative solutions:

• Recursive solutions are often more elegant and readable
• Iterative solutions typically use less memory (no call stack overhead)
• Some problems (like tree traversal) are naturally recursive
• Recursive solutions can suffer from stack overflow for large inputs