Recursion/Searching/Sorting

Recursion/Searching/Sorting

1. Recursion: A loop created by a method calling itself, it is stopped by a "base case"

   • Only need to know how to trace, don't need to create recursive methods.
   • Has a return type, and adds on over time.

2. Searching

   • Binary: A binary search can only be used if the data is sorted. It compares a target value to the value in the middle of a range of indices. If the value isn’t found it looks again in either the left or right half of the current range. Each time through the loop it eliminates half the values in the search area until either the value is found or there is no more data to look at.
   • Linear/Sequential: Sequential search is the only method that can be used to find a value in unsorted data. It usually starts at the first element and walks through the array or list until it finds the value it is looking for and returns the index it found it at, or it loops until the end of the array or list and then it returns a -1 to show that it didn’t find the value in the array or list.

3. Sorting

   • Selection sort: The selection sort that you need to know for the exam starts at index 0 and looks through the entire array keeping track of the the index of the smallest value in the array and then swaps the value at the smallest index with the value at index 0. Then it does the same thing for index 1, then 2, and so on until it reaches the length of the array minus one. At this point the array is sorted in ascending order.
     • What to look for
       • a nested for loop with the outer loop starting at 0 and ending when the index reaches length - 1
       • the index of the smallest value should start at the outer loop index
       • the inner loop should start at the outer loop index + 1 and loop through the whole array
       • if the value in the array at the index of the inner loop is less than the value at the smallest index then set the smallest index to the index of the inner loop
       • swap the value at the outer loop index and the smallest value (the one at the smallest value index)
   • Insertion sort: The insertion sort that you need to know for the exam starts at index 1 and inserts the value at index 1 into its correct place in the already sorted part (the part to the left of the current index). It moves any value larger than the value stored in temp to the right until it either finds the appropriate place to put temp or gets to the front of the array.
     • What to look for
       • an outer for loop that starts at 1 and loops through the entire array
       • storing the element value at the outer loop index in temp
       • setting the possible index to the outer loop index
       • an inner while loop that loops while the possible index is greater than 0 and the value in temp is less than the value at the possible index minus one
       • set the value at the possible index to the one to the left of it (the one at possible index minus one)
       • decrement the possible index (subtract one from it)
       • when the while loop ends set the value at the possible index to temp
   • Merge sort: A merge sort recursively breaks the values to be sorted in half until there is only one value to be sorted and then it merges the two sorted lists into one sorted list. The code shown below uses a second array the same size as the original array for merging the values in order. Then it copies all of the sorted values back into the original array.
     • What to look for
       • 3 methods, merge sort, mergeSortHelper, and merge
       • mergeSortHelper is recursive

Images and files in the map