Which is faster, sorting a list of elements or searching the same list of elements?

Select one answer, then check.

• Sorting is always faster.
  Not quite. An iterative search checks each element at most once, while the sorting algorithms in the reading compare and move elements many times.
• Searching is always faster.
  Almost. Searching is never slower, but in one case the two take about as long: when the list is already sorted, Insertion Sort only has to walk through it once, and a search for a missing item checks every element.
• Sorting is usually faster, unless the list is already sorted and the item we search for is not in the list.
  Not quite. It is the other way around: searching is usually faster.
• Searching is usually faster, unless the list is already sorted and the item we search for is not in the list.
  Correct. An iterative search checks each element at most once, while sorting usually moves elements around many times. But on an already sorted list, Insertion Sort only walks through the list once, and a search for an item that isn't there checks every element: the two take about as long.

True or False: time that an algorithm takes is always dependent on the size of the input, not on the actual values of the input.

Select one answer, then check.

• True
  Not quite. Insertion Sort from the reading is faster on an already sorted list than on a list of the same size in reverse order: the values affect the time too.
• False
  Correct. Insertion Sort is the counterexample: on an already sorted list it only walks through once, while in the worst case it drags every element back through the list.

True or False: binary search would not work on an unsorted list of numbers.

Select one answer, then check.

• True
  Correct. After each check, binary search throws away half of the list, depending on whether the target is smaller or larger than the midpoint; that is only safe when the list is sorted.
• False
  Not quite. On an unsorted list, the target can be in the half that binary search throws away, so it can miss an item that is in the list.

True or False: binary search only works on numbers, because you cannot order strings.

Select one answer, then check.

• True
  Not quite. Strings do support ordering comparisons: "apple" < "banana" is True, and sorted sorts a list of strings.
• False
  Correct. Strings support ordering comparisons (the reading says sorted works on strings too), so a sorted list of strings can be searched with binary search.

Why is binary search faster than iterative search?

Select one answer, then check.

• Binary search uses binary numbers, which are faster than regular numbers.
  Not quite. The "binary" refers to splitting the list in two, not to binary numbers.
• Binary search repeatedly divides the search space in half each time.
  Correct. Every check throws away half of the remaining list, so a list of 1024 elements takes only about 11 checks.
• Binary search uses ancient forbidden magic taught to us by the elder gods.
  No magic involved: every check halves the part of the list that is left.
• Binary search uses the RAM Model to estimate where the item is before seeking it.
  Not quite. The RAM Model is a way to estimate how long a program takes, not something a search uses.
• Binary search alternates between checking the first and last elements, moving inwards, finding the value in half the time.
  Not quite. That still checks elements one at a time, just in a different order, so in the worst case it checks every element.
• Nobody knows. The secret is lost to time.
  The reason is well known: every check halves the part of the list that is left.

Which of the following is an accurate summary of Insertion Sort?

We recommend you check out this page: https://visualgo.net/en/sorting

Select one answer, then check.

• Repeatedly find the smallest element in the rest of the list and move it to the front of the list.
  Not quite. That is Selection Sort, which picks the smallest remaining element each time.
• Walk through each position of the list, and move the current element into the earlier position in the list where it belongs.
  Correct. The elements before the current one are already in sorted order, and the inner while loop drags the current element back to its place among them.
• Swap each pair of elements repeatedly until all the elements are in the proper order.
  Not quite. That is Bubble Sort, which swaps adjacent elements inside a nested for loop.
• Repeatedly divide the list into two halves, sort each half, and then merge them back together.
  Not quite. That is MergeSort, one of the other sorts the reading lists.
• Repeatedly shuffle the list until the list is in sorted order.
  Not quite. Shuffling until the list happens to be sorted could take forever; Insertion Sort moves each element to its place once.

Which of the following are valid reasons that Computer Scientists study sorting and searching so much?

Select every answer that applies, then check.

• Searching and sorting are common problems for lists.
  Correct. The reading calls them two important operations on a list, useful in their own right.
• Both searching and sorting have been studied closely, so they are well-understood.
  Correct. They have been exhaustively studied, which also makes them very educational.
• Programmers often need to make their own sorting and search algorithms, since most languages do not have their own implementation built-in to the language.
  Not a valid reason. Most languages do have them built in: Python has the sorted function, for example.
• Sorting and searching are very complicated problems, so studying them makes us feel smarter and superior to other disciplines.
  Not a valid reason. They are studied because they are useful and educational, not to feel superior.