Unit 14 (Algorithms) Assignment (Optional)
AP Computer Science 2021-22 / Dr. Kessner

Code exercises

Here are some optional fun code exercises to practice thinking about algorithms. Choose any that look interesting to you. Make sure to write unit tests to verify that your code is behaving the way you expect it to.

Implement a linear search function. Note: You have written similar functions before, finding an object with a specified name in a list, for example. In this case you want to return the index into the array, not the object.

Example:

int find(int[] values, int searchValue);

find({1, 3, 5, 7}, 0) -> -1  // return -1 if searchValue is not found
find({1, 3, 5, 7}, 1) -> 0
find({1, 3, 5, 7}, 3) -> 1
find({1, 3, 5, 7}, 5) -> 2
find({1, 3, 5, 7}, 7) -> 3

Sorting

  • Implement selection sort. Your function should take an ArrayList as input, and return another ArrayList with the same values sorted.

  • Implement insertion sort.

  • Implement bubble sort.

  • Implement merge sort.

Implement a binary search function. Remember: the input list must be sorted in order for this to work.