Recursion

10.2) Recursive Searching and Sorting

Skill 2.D (10.2.1) - Binary Search

Learning Objective

  • CON-2.P
    • Apply recursive search algorithms to information in String, 1D array, or ArrayList objects.

Essential Knowledge

  • CON-2.P.1
    • Data must be sorted in sequential order so you can use binary search
  • CON-2.P.2
    • The binary search algorithm starts at the middle of a sorted array (or ArrayList) and eliminates half of the array (or ArrayList) in each iteration until the desired value is found or all elements have been eliminated.
  • CON-2.P.3
    • Binary search can be more efficient than sequential/linear search.
      • Important: any search algorithms apart from linear and binary search will not be tested on the AP Exam and are out of the scope for AP CSA.
  • CON-2.P.4
    • The binary search algorithm can be written iteratively or recursively.

Binary search w/recursion:

  • Draft a binary search algorithm with recursion (cannot use loops)
    • What do we do if lowPosition is greater than highPosition?
    • What do we do if the middle value is less than target?
    • What do we do if the middle value is greater than target?
    • What do we do if the middle value is equal to target?
// Binary search function to find the index of a target value in a sorted array using an iterative approach
public static int binarySearch(int[] intArray, int lowPosition, int highPosition, int target) {
    // Declare a variable to store the middle index of the current search range
    int midPosition;

    // Continue searching while the lower bound is less than or equal to the upper bound
    while (lowPosition <= highPosition) {
        // Calculate the middle index of the current search range
        // (highPosition + lowPosition) / 2 could potentially overflow; a safer alternative is:
        // midPosition = lowPosition + (highPosition - lowPosition) / 2;
        midPosition = (highPosition + lowPosition) / 2;

        // If the value at the middle index is less than the target, adjust the lower bound
        if (intArray[midPosition] < target) {
            lowPosition = midPosition + 1; // Narrow search to the upper half of the range
        }
        // If the value at the middle index is greater than the target, adjust the upper bound
        else if (intArray[midPosition] > target) {
            highPosition = midPosition - 1; // Narrow search to the lower half of the range
        }
        // If the value at the middle index matches the target, return the index
        else {
            return midPosition; // Target found
        }
    }

    // If the loop ends without finding the target, return -1 to indicate it was not found
    return -1;
}

public static int binarySearchRecursive(int[] intArray, int lowPosition, int highPosition, int target) {
    int midPosition;

    if (lowPosition > highPosition) {
        // could not find the target
        return -1;
    }
    else {
        midPosition = (lowPosition + highPosition) / 2;

        if (intArray[midPosition] < target) {
            // if the mid value is less than the target, the target is in the upper half of the list
           return binarySearchRecursive(intArray, midPosition + 1, highPosition, target);
        }

        else if (intArray[midPosition] > target) {
        // if the mid value is greater than the target, the target is in the lower half of the list
           return binarySearchRecursive(intArray, lowPosition, midPosition - 1, target);
        }

        else if (intArray[midPosition] == target) {
            // target was found; return its location
            return midPosition;
        }
    }
    return -1;
}

int[] intArray = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40};
binarySearchRecursive(intArray, 0, 20, 24);
  • intArray = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40]
  • Call 1: binarySearchRecursive(intArray, 0, 20, 24)
    • midPosition = (0 + 20) / 2 = 10
    • intArray[midPosition] = intArray[10] = 20
      • intArray[midPosition] &lt; 24 (intArray[midPosition] &lt; target)
    • Our middle value (20) was less than the target (24), so we can eliminate the bottom half of the list. We call the function again but this time, we only look at the top half (we set the lower bounds to the middlePosition + 1)
  • Call 2: binarySearchRecursive(intArray, 11, 20, 24)
    • Now, we only look at the values [24, 26, 28, 30, 32, 34, 36, 38, 40].
    • midPosition = (11 + 20) / 2 = 15
    • intArray[midPosition] = intArray[15] = 30
      • intArray[midPosition] > 30 (intArray[midPosition] > target)
    • The new middle value of 30 is greater than 24, so we can eliminate the top half of the list. When we call the function again, we only change the upper bound to ignore values greater than or equal to 30.
  • Call 3: binarySearchRecursive(intArray, 11, 14, 24)
    • Now, we only look at the values [24, 26, 28].
    • midPosition = (11 + 14) / 2 = 12
    • intArray[midPosition] = intArray[12] = 24
      • intArray[midPosition] = target
    • We found that the target value of 24 is located in the 12th position. We return the midPosition (12) as the final answer.

Popcorn Hack 3 - Selection sort

Introduction

Using your knowledge of local variables, global variables, and parameters, please create a recursive method which sorts an array through selection.

// By the way the max variable didn't seem to be necessary so I removed it, since I just find the maximum value in the actual function itself

public static int[] selectionSort(int[] arr, int index) { 
    // your code here
    if (index == arr.length) {
        return arr;
    }

    int maxIndex = 0;
    int maxVal = arr[index];
    for (int i=index; i < arr.length; i++) {
        if (arr[i] <= maxVal) {
            maxIndex = i;
            maxVal = arr[i];
        }
    }

    int tmp = arr[index];
    arr[index] = arr[maxIndex];
    arr[maxIndex] = tmp;
    return selectionSort(arr, index+1, max);
}

int[] intArray = {5, 2, 7, 4, 8, 5, 3};
int[] sortedArr = selectionSort(intArray, 0, 7);

for (int i=0; i < sortedArr.length; i++) {
    System.out.print(sortedArr[i] + " ");
}
System.out.println(); // it's very goofy to not have a newline at the end of the output so I just added this, should output "2 3 4 5 5 7 8"

Skill 2.C (10.2.2) - Merge Sort 😍

Learning Objective

  • CON-2.Q
    • Apply recursive algorithms to sort elements of array or ArrayList objects.

Essential Knowledge

  • CON-2.Q.1
    • Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList.

How it works:

Image Description
Alt text When you merge sort, you recursively call the sorting function. You first look at the left half of the list, then the right half, and then both. Remember: left, right, merge; left, right, merge…
Alt We first call the mergeSort() function on the entire list. Remember, we look at the left half first. On the first call (at the bottom of the “tree”), the algorithm takes the left half of the list. It keeps going until there are no more halves left (it reached the end of the branch).
Alt — Alt When it reached the end of the branch (5), it would consider that call to be complete. It goes back and then considers the right branch (25). Again, it reached the end. So to summarize what we did: if the array is the tree, we went to go find the end of the branches on the left side. In our case, we found the ends to be 5 and 25. When we remerge, we will sort them. So in this case, 5 < 25 so that branch is already sorted.
Alt — Alt — Alt We do the same thing but with the other branch. However, the numbers are out of order this time. When we merge the 8 branch and the -9 branch, we flip the numbers.
Alt Now, we are back at the larger branch of the four numbers. When we merge, we are going to sort the numbers again.
Alt The numbers are sorted. You’ll see that on the parent branch (at the very bottom), the left half of the array is fully sorted. This whole process is repeated on the right half of the array. Eventually, the whole array will be sorted.

Skill 2.C (10.2.3) - Merge Sort: The Actual Code

Image Description
Alt Variable to keep track of the left most value of the parent array Variables to keep track of the left most value of the child arrays (the left and right halves)
Alt We compare the value at index 0 and index 4. Since 1 < 3, we replace the value at index 0 of the parent array with 1.
Alt — Alt Increment the variable in the parent array and the 2nd half (child array). Compare the values and then update the parent array.
Alt Alt — Alt Alt Everything done above is done again. Increment the variables, compare, and update. However, this time, 3 < 5. Basically, a value from the left child array is less than the value from the right child array (the previous two iterations were the opposite). So, when we update the parent array, we will put 3 to replace 6. Then, we increment the variable for the left child array.
Alt What happens when we reach the end? Here, you can see that the arrow is outside the array so we will get an out of bounds error. In this case, we would need to have a clause in the code that just tells us to copy over the 8 to the final element in the array. 
import java.util.Arrays;

// Merge sort in Java

class Main {

    // Merge two sub arrays L and M into array
    void merge(int array[], int p, int q, int r) {

        int n1 = q - p + 1;
        int n2 = r - q;

        int L[] = new int[n1];
        int M[] = new int[n2];

        // fill the left and right array
        for (int i = 0; i < n1; i++) {
            L[i] = array[p + i];
        }

        for (int j = 0; j < n2; j++) {
            M[j] = array[q + 1 + j];
        }

        // Maintain current index of sub-arrays and main array
        int i, j, k;
        i = 0;
        j = 0;
        k = p;

        // Until we reach either end of either L or M, pick larger among
        // elements L and M and place them in the correct position at A[p..r]
        // for sorting in descending
        // use if(L[i] >= <[j])
        while (i < n1 && j < n2) {
            if (L[i] <= M[j]) {
                array[k] = L[i];
                i++;
            } 
            else {
                array[k] = M[j];
                j++;
            }
            
            k++;
        }

        // When we run out of elements in either L or M,
        // pick up the remaining elements and put in A[p..r]
        while (i < n1) {
            array[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            array[k] = M[j];
            j++;
            k++;
        }
    }

    // Divide the array into two sub arrays, sort them and merge them
    void mergeSort(int array[], int left, int right) {
        if (left < right) {

            // m is the point where the array is divided into two sub arrays
            int mid = (left + right) / 2;

            // recursive call to each sub arrays
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);

            // Merge the sorted sub arrays
            merge(array, left, mid, right);
        }
    }

    public static void main(String args[]) {

        // created an unsorted array
        int[] array = { 5, 25, 8, -9, 14, 0, -2, 2 };

        Main ob = new Main();

        // call the method mergeSort()
        // pass argument: array, first index and last index
        ob.mergeSort(array, 0, array.length - 1);

        System.out.println("Sorted Array:");
        System.out.println(Arrays.toString(array));
    }
}

Main.main(null);

Popcorn Hack 4 - 2D Array Recursion

Introduction

Using your knowledge of local variables, global variables, and parameters, please create a recursive method which sorts an array through selection. Remember you have your parameters to keep your indices, just keep track of your indices.

// ok so my thought process here was to basically implement selection sort but just use the 2d indexes instead, kind of just treating it as a 1d array but instead accessing with the row

public static int[][] TwoDArrSort(int[][] arr, int x_index, int y_index) { 
    if (x_index == arr[arr.length-1].length-1 && y_index == arr.length-1) {
        return arr;
    }

    int maxIndexX = x_index;
    int maxIndexY = y_index;
    int maxVal = arr[y_index][x_index];
    for (int i=y_index; i < arr.length; i++) {
        // ok the reason I have this goofy ternary condition is because I need to start at the index for the row we're in, but then later rows should start at 0
        for (int j=(i == y_index ? x_index : 0); j < arr[i].length; j++) {
            if (arr[i][j] <= maxVal) {
                maxIndexY = i;
                maxIndexX = j;
                maxVal = arr[i][j];
            }
        }
    }

    int tmp = arr[y_index][x_index];
    arr[y_index][x_index] = arr[maxIndexY][maxIndexX];
    arr[maxIndexY][maxIndexX] = tmp;
    if (x_index == arr[y_index].length-1) {
        return TwoDArrSort(arr, 0, y_index+1);
    } else {
        return TwoDArrSort(arr, x_index+1, y_index);
    }
}

int[][] arr = new int[3][3]
arr[0] = {5, 2, 7}
arr[1] = {4, 8, 5}
arr[2] = {3, 1, 6}
int[][] sortedArr = TwoDArrSort(arr, 0, 0);

for (int i=0; i < sortedArr.length; i++) {
    for (int j=0; j < sortedArr[i].length; j++) {
        System.out.print(sortedArr[i][j] + " ");
    }
    System.out.println();
}

Homework Hack - Recruiting Scrum Unpaid Interns for Mr. Mortensen!!!

Introduction

Mr. Mortensen needs help recruiting new Scrum Unpaid Interns to help integrate his project. However, he has a dilemna on who to recruit for this job!

Luckily for you, you have three statistics for each student:

  • collab - How well they collaborate with fellow students!
  • iq - The intelligence level of the student (who wouldn’t want someone smart?)
  • efficiency - The efficiency at which they work at (time is of the essence to Mr. Mortensen!)

Using these three statistics, please calculate a performance score for each student, and sort them into an array (using an algo of your choice!) in descending order.

Here are the list of students with their statistics:

Student
 collab
 iq
 efficiency
srijus
 98
 95
 92
aadit
 95
 97
 97
erox
 90
 93
 89
shubs
 92
 94
 90
aashray
 50
 53
 59
 
// Pro tip: Think of why the index is stored as a parameter
// What are parameters usually used as?
public class Student {
    String name;
    int efficiency, collab, iq;
    int performanceScore;

    public Student (String name, int efficiency, int collab, int iq) {
        this.name = name;
        this.efficiency = efficiency;
        this.collab = collab;
        this.iq = iq;
        this.performanceScore = calculatePerformanceScore();
    }

    public int calculatePerformanceScore() {
        return (collab * 2) + (iq * 3) + efficiency;
    }
}

public static Student[] sortStudents(Student[] arr, int index) { 
    if (index == arr.length) {
        return arr;
    }

    int maxIndex = 0;
    int maxVal = arr[index].performanceScore;
    for (int i=index; i < arr.length; i++) {
        if (arr[i].performanceScore <= maxVal) {
            maxIndex = i;
            maxVal = arr[i].performanceScore;
        }
    }

    Student tmp = arr[index];
    arr[index] = arr[maxIndex];
    arr[maxIndex] = tmp;
    return sortStudents(arr, index+1);
}

Student[] skibidiSigmas = new Student[] {
    new Student("Sigma", 5, 3, 4),
    new Student("Skibidi", 2, 5, 3),
    new Student("SkibidiSigma", 3, 4, 5),
    new Student("Aadit", 1000, 10000, -2000),
    new Student("Shuban", 10000000, 100000000, +2000),
    new Student("EricYu-m", 8175098, 28025, 275480),
    new Student("AlwaysReddy", 420, 1490178, 2)
};

Student[] sortedSigmas = sortStudents(skibidiSigmas, 0);
for (int i = 0; i < sortedSigmas.length; i++) {
    System.out.println(sortedSigmas[i].name + " " + sortedSigmas[i].performanceScore);
}