CS1 Unit Review: Searching and Sorting Algorithms

An ___ can be defined as a step-by-step sequence of instructions to solve a problem

For the binary search algorithm to work, the input list needs to be:

• Sorted

• An even length

• Unsorted

• An odd length

Suppose binary search is looking for a key in a sorted list of 7 items. If the key does not show up in its first "check," how many items has it eliminated from the search?

• 1

• 2

• 3

• 4

Given a sorted list and a prize (or "key") to find, which search algorithm would you expect to perform best?

• Binary search

• Linear search

• Any search algorithm

What is an example of an algorithm that you use in real life?

Draw a chart for an algorithm that has linear runtime, that is, O(n)

Draw a chart for an algorithm that has logarithmic runtime, that is, O(log₂n). Binary search is one such algorithm.

The ___-sort algorithm works by repeatedly swapping neighboring items in a list if they are out of order, until the whole list is in order

Draw a chart for an algorithm that has exponential runtime, that is, O(n²). Bubble sort is one such algorithm.

The ___-sort algorithm works by splitting a list in half and separately sorting the two halves