9 min read•june 18, 2024
Avanish Gupta
Milo Chang
Avanish Gupta
Milo Chang
Using , we can make our searching and from much more concise, and we will also have new searching and sorting that may be more efficient than our previous algorithms!
We already covered this iteratively in Topic 7.5. As a reminder, here is the :
public static int linearSearch(ArrayList<Integer> array, int n) { for (int i = 0; i < array.size(); i++) { if (array.get(i) == n) { return i; } } return -1; }
Here is the recursive version:
public static int recursiveLinearSearch(ArrayList<Integer> array, int n, int startingIndex) { if (array.get(startingIndex) == n) { return startingIndex; // base case #1: element found } else if (startingIndex == array.size() - 1) { return -1; //base case #2: element not found } else { //[recursive call](https://www.fiveableKeyTerm:Recursive_Call) to check next element return recursiveLinearSearch(array, n, startingIndex + 1); } } //To use this method: recursiveLinearSearch(array, n, 0);
Binary search is the new search algorithm that we'll learn in this unit, and it is quicker than linear sort. However, the tradeoff for the speed is that the list has to be presorted. Binary search will not work if the data is not presorted.
Here is its implementation, along with how it works both iteratively and recursively:
/** Uses binary search on a sorted ArrayList * 1. Looks at the middle of the list, which divides it into two sublists * 2. The left sublist is less than the middle and the right is greater * 3. Compare the value to be searched for to the middle value * 4. If this value > middle, repeat 1-3 to the right sublist * 5. If this value < middle, repeat 1-3 to the left sublist * 6. If this value = middle, return the middle value * 7. Return -1 if value not found */ public static int binarySearch(ArrayList<Integer> array, int n) { int left = 0; int right = array.size() - 1; while (left <= right) { // left > right is "illegal" int middle = (left + right) / 2; // get the middle index of sublist if (n == array.get(middle)) { // item in middle of sublist return middle; } else if (n < array.get(middle)) { // item in left sublist right = middle - 1; } else if (n > array.get(middle)) { // item in right sublist, could just use else left = middle + 1; } } return -1; // item not in list } public static int recursiveBinarySearch(ArrayList<Integer> array, int n, int left, int right) { int middle = (left + right) / 2; // get the middle index of sublist if (left > right) { // base case #1: item not in list return -1; } else if (n == array.get(middle)) { // base case #2: item in middle of sublist return middle; } else if (n < array.get(middle)) { // recursive call #1: item in left sublist return recursiveBinarySearch(array, n, left, middle - 1); } else if (n > array.get(middle)) { // recursive call #2: item in right sublist, could just use else return recursiveBinarySearch(array, n, middle + 1, right); } } //To use this, call: recursiveBinarySearch(array, n, 0, array.size() -1);
Here is a visualization of binary search:
We already covered this iteratively in Topic 7.6. As a reminder, here is the iterative code:
/** Uses insertion sort on an ArrayList * 1. Assume the first element is already sorted * 2. Select the second element * 3. Insert it before the first element or keep it in place to make the first 2 elements sorted * 4. Select the third element and insert it so that the first 3 elements are sorted * 5. Repeat until all elements are sorted. */ public static ArrayList<Integer> insertionSort(ArrayList<Integer> array) { for (int i = 1; i < array.length(); i++) { int currentElement = array.get(i); int currentIndex = i; for (int j = i; j > 0 ; j--) { if (currentElement < array.get(j - 1)) { // shifting the item left until properly placed by swapping consecutive items int itemToRight = array.get(j - 1); array.set(j - 1, currentElement); array.set(j, itemToRight); } } } return array; }
Here is the recursive version:
public static ArrayList<Integer> recursiveInsertionSort(ArrayList<Integer> array, int index) { if (index == array.size()) { // base case: end of list reached, list sorted return array; } else { int currentItem = array.get(index) for (int i = index; i > 0; i--) { // shifting item to the left until sorted if (currentItem < array.get(i - 1)) { int itemToRight = array.get(i - 1); array.set(i - 1, currentItem); array.set(i, itemToRight); } } return recursiveInsertionSort(array, index + 1); // recursive call to sort the next item } } //To use this method: recursiveInsertionSort(array, 0);
We already covered this iteratively in Topic 7.6. As a reminder, here is the iterative code:
/** Uses [selection sort](https://www.fiveableKeyTerm:Selection_Sort) on an ArrayList * 1. Originally the ArrayList is unsorted * 2. We select the smallest number and swap it with the first element * 3. Now the sorted subarray is the first item and the rest of the array is unsorted * 4. Select the smallest of the unsorted numbers (the second smallest overall) and * swap it with the second element * 5. Now the first two elements are sorted and the rest are unsorted * 6. Repeat until the rest of the elements are sorted */ public static ArrayList<Integer> selectionSort(ArrayList<Integer> array) { for (int i = 0; i < array.size() - 1; i++) { // traverse to the second to last item, the last item is automatically the largest int smallestIndex = i; int smallestElement = array.get(i); for (int j = i + 1; i < array.size(); j++) { //traverse through the rest of the array, //looking for the smallest remaining item (less than smallestElement) if (array.get(j) < smallestElement) { smallestIndex = j; smallestElement = array.get(j); } } if (smallestIndex > i) { // swap the elements of i and j if the element of i isn't already the smallest int originalItem = array.get(i); array.set(i, smallestElement); array.set(smallestIndex, originalItem); } } return array; }
Here is the recursive version:
public static ArrayList<Integer> recursiveSelectionSort(ArrayList<Integer> array, int index) { if (index == array.size()) { return array; } else { int smallestIndex = index; int smallestElement = array.get(index); for (int i = index + 1; i < array.size(); i++) { if (array.get(i) < smallestElement) { smallestIndex = i; smallestElement = array.get(i); } } if (smallestIndex > index) { int originalItem = array.get(index); array.set(index, smallestElement); array.set(smallestIndex, originalItem); } return recursiveSelectionSort(array, index + 1); } } //To use this method: recursiveInsertionSort(array, 0);
is the new sorting algorithm learned in this unit, and it is quicker than insertion and selection sort. However, the tradeoff for the speed is that the algorithm requires more memory.
Here is its implementation, along with how it works both iteratively and recursively:
/** Performs Merge sort (each version requires 2 methods, one specific to each version to split the lists and one common method to merge the sublists) * 1. Split the list in half repeatedly (2 sublists, 4 sublists, 8, 16, ...) until each sublist has one item 2. Sort and Merge consecutive items until we get sorted sublists of length 2 3. Sort and Merge consecutive sublists of 2 to get sorted sublists of length 4 4. Repeat until the list is fully merged and sorted */ // ITERATIVE SPLITTING FUNCTION // void bc the method adjusts the array itself, so you can call the array in an // outside method public static void mergeSort(ArrayList<Integer> array) { // determine the size of the sublists to be merged for (int currentSublistSize = 1; currentSublistSize < array.size(); currentSublistSize *= 2) { // merge sublists of the current size for (int startOfSubarray = 0; startOfSubarray < array.size() - 1; startOfSubarray += 2 * currentSublistSize) { // determine the end indices of the subarrays to be merged int middle=Math.min(startOfSubarray + currentSublistSize - 1, array.size() - 1); int endOfSubarray = Math.min(startOfSubarray + 2 * currentSublistSize - 1, array.size() - 1); merge(array, startOfSubarray, middle, endOfSubarray); } } } // RECURSIVE SPLITTING FUNCTION public static void recursiveMergeSort(ArrayList<Integer> array, int left, int right) { // merge sorts a sublist from starting index left to ending index right if (left < right) { // if the sublist has more than 1 item int middle = (left + right) / 2; // split the sublist in half and mergeSort the halves recursiveMergeSort(array, left, middle); recursiveMergeSort(array, middle + 1, right); merge(array, left, middle, right); } } // MERGING FUNCTION public static void merge(ArrayList<Integer> array, int left, int middle, int right) { int leftLength = middle - left + 1; int rightLength = right - middle; // create 2 temporary ArrayLists for the left and right halves int[] leftTemporary = new int[leftLength]; int[] rightTemporary = new int[rightLength]; for (int i = 0; i < leftLength; i++) { // copy data into temp lists leftTemporary[i] = array.get(left + i); } for (int i = 0; i < rightLength; i++) { // copy data into temp lists rightTemporary[i] = array.get(middle + 1 + i); } int i = 0; int j = 0; int k = left; // start sorting the merged section of the array by combining the sublists while (i < leftLength && j < rightLength) { if (leftTemporary[i] <= rightTemporary[j]) { array.set(k, leftTemporary[i]); i++; } else { array.set(k, rightTemporary[j]); j++; } k++; } while(i < leftLength) { // copy remaining elements of left and right if sublists of different size array.set(k, leftTemporary[i]); i++; k++; } while(j < rightLength) { // copy remaining elements of left and right if sublists of different size array.set(k, rightTemporary[j]); j++; k++; } }
Here is a visual look at merge sort:
If you've made it this far, congratulations, you've reached the end of AP Computer Science A! By now, you should be an expert on — loops, recursion, and conditional statements, object orientated programming — , , , and polymormism, and basic — 1-D and 2-D arrays and ArrayLists!
If you're interested in further pursuing computer science, what comes next?
You will most likely take a set of two courses, one being a more mathematically orientated and the other being more programming orientated. The first is a class, which covers the theory of discrete , which consists of things that we can count on our fingers, like whole numbers, as opposed to continuous sets, which are uncountable, such as real numbers. In this class, you'll learn a lot of so that we can understand programs and algorithms more. You will also learn and as well, which represent random algorithms and will help with machine learning and other fields where our methods are mostly consisting of random numbers with random outputs. Finally, you'll learn about , which are a type of that consists of different elements and connections between these elements.
On the other hand, the second Java course is a continuation of this course. You'll learn some advanced topics in inheritance and with the introduction of the interface and the abstract class and also make better loops, recursion, and classes with what are known as invariants (which are the basis of the "Four Loopy Questions" in Unit 4). Then, you'll move onto more advanced data structures, including the following:
With AP CSA and these two courses, these set up the foundation for any computer science that you will do afterwards, like , , , graphics, , and so much more! The possibilities are endless! Moreover, there are many resources to learn these online as well and you don't need to go to a university to be a good programmer, but instead you can teach yourself and achieve great things!
If you have reached the end of this guide, thank you for sticking along on this journey through AP CSA. We as the Fiveable team have spent countless hours making and curating the best resources available for your use so that you can pass the AP exam and hopefully learn something new, fun, and insightful throughout this course that you can use later. We hope that you have found this information valuable and we wish you the best of luck on your AP exams and beyond!