###### Bookmarks

Subjects and resources that you bookmark will appear here.

Light Mode

The AP Computer Science A 5-hour live stream review is here!Β π»

Join us on May 5, 2021 for the πΆοΈ AP Computer Science A Cram Finale for a last minute review to get all your questions answered!

π

All Subjects

Β >Β

π»Β

AP Comp Sci A

Β >Β

π±

Unit 10

# 10.2 Recursive Searching and Sorting

Peter Cao

Caroline Koffke

Using recursion, we can make our searching and sorting algorithms from Unit 7 much more concise, and we will also have new searching and sorting algorithms that may be more efficient than our previous algorithms!

## Searching β Linear/Sequential Search

We already covered this iteratively in Topic 7.5. As a reminder, here is the iterative code:
```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 { return recursiveLinearSearch(array, n, startingIndex + 1); //recursive call to check next element } } //To use this method: recursiveLinearSearch(array, n, 0); ```

## Searching: Binary Search

Binary searchΒ is the new search algorithm learned in this unit, and it is quicker than linear sort. However, the tradeoff for the speed is that the list has to be 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:

Courtesy ofΒ Study.com.

## Sorting: Insertion Sort

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 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 { currentItem = array.get(index) for (int i = index; i > 0; i--) { // shifting item to the left until sorted if (currentItem < array.get(i - 1)) { 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); ```

## Sorting: Selection Sort

We already covered this iteratively in Topic 7.6. As a reminder, here is the iterative code:
```/** Uses 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() - 1) { 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(j); } } 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); ```

## Sorting: Merge Sort

Merge sortΒ 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 public static void mergeSort(ArrayList<Integer> array) { // void bc the method adjusts the array itself, so you can call the array in an outside method for (int currentSublistSize = 1; currentSublistSize <= array.size() - 1; currentSublistSize *= 2) { // merge all of size 1 to make size 2, then 2 to size 4, etc. for (int startOfSubarray = 0; startOfSubarray < array.size() - 1; startOfSubarray += (2*currentSublistSize)) { // set the sublists to merge int middle; int endOfSubarray; if (startOfSubarray + currentSublistSize - 1 > n -1) { middle = n - 1; } else { middle = startOfSubarray + currentSublistSize - 1; } if ( startOfSubarray + 2 * currentSublistSize - 1 > n -1) { endOfSubarray = n - 1; } else { endOfSubarray = startOfSubarray + 2 * currentSublistSize - 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; int[] leftTemporary = new int[leftLength]; // create 2 temporary ArrayLists for the left and right halves 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:

Courtesy ofΒ Techie Delight.

## Closing β What's Next?

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 control structures β loops, recursion, and conditional statements, object orientated programming β abstraction/method writing, encapsulation/class writing, inheritance, and polymormism, and basic data structures β 1-D and 2-D arrays and ArrayLists!
If you're interested in further pursuing computer science, what comes next?

Courtesy ofΒ GIPHY.

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 discrete math class, which covers the theory of discrete sets, 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 logic and proofs so that we can understand programs and algorithms more. You will also learn probability and state machines 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 graphs, which are a type of data structure 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 polymorphism 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:
• These do not have indices but just pointers between one element and the next (and sometimes previous)
• Hash maps and other maps
• These map one element to another which is like a dictionary word and its definition (the hash map uses a hash function like those described in Topic 9.7)
• Sets
• These are like lists, but are unordered and have nonduplicating items
• Trees
• These represent data in a branched structure, and are best when items have multiple different "levels"
• Graphs
• Explained above, these represent data and connections between this data
You'll learn about these data structures and also implement algorithms, being able to analyze how fast they run and how much memory they take up. Finally, you'll also learn to make GUIs, which are graphics which display information in a visual manner.
With AP CSA and these two courses, these set up the foundation for any computer science that you will do afterwards, like artificial intelligence and machine learning, algorithm analysis, programming language construction, graphics, web development, 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!

##### πͺπ½ Are you ready for the Comp Sci exam?
Take this quiz for a progress check on what youβve learned this year and get a personalized study plan to grab that 5!
START QUIZ
Studying with Hours = the ultimate focus mode
Start a free study session
##### FREE AP comp sci a Survival Pack + Cram Chart PDF
Browse Study Guides By Unit
π
Exam Reviews
β
Unit 1: Primitive Types
π±
Unit 2: Using Objects
π₯
Unit 3: Boolean Expressions and if Statements
πΉ
Unit 4: Iteration
βοΈ
Unit 5: Writing Classes
βοΈ
Unit 6: Array
πΎ
Unit 7: ArrayList
π»
Unit 8: 2D Array
π²
Unit 9: Inheritance