ch 7.txt

Card Set Information

ch 7.txt
2015-03-03 10:03:27
diane cs111
diane cs111 ch 7
Show Answers:

  1. How does a sequential search work?
    • A sequential search looks at each item in a list and compares it to the sought item. If the list item is not the sought item, the search continues with the next item.
    • The time required to perform a sequential search has a linear relationship with the length of the list.
  2. What is recursion?
    • Recursion is an approach used in algorithms which is analagous to "divide and conquer". In this method, a problem's size is repeatedly reduced until the problem becomes manageable.
    • An example of recursion is the flood-fill algorithm.
  3. How does a recursive search algorithm work?
    It works by finding the middle of the list. Then it determines if the sought item is the middle item. If not, it determines if the sought item is before or after the middle item. In this way, half of the remaining list can be discarded with every iteration. *It is important to note that the list must be sorted for algorithms of this type to work.*
  4. Sorting lists is more / less complicated than searching lists.
  5. Describe how a selection sort works.
    Starting at the left, find the smallest item in the list. When you find it, move it to the 1st position in the list, and move the item that was in the first position to the position the item was found in. Now, repeat the process, working from the next position until the 2nd to last position has been set.
  6. Name two weaknesses of selection sort.
    • 1) No mechanism for determining when it is done. (Other than cycling through the whole list.)
    • 2) Takes the same amount of time to get through a list that is already sorted.
  7. Describe how a bubble sort works.
    Start with the leftmost pair in the list. If the smaller item is not on the left, swap the items. Move to the pair that includes the 2nd item in the 1st pair and the 3rd item in the list. If they are not in order, swap them. Repeat until you reach the end of the list. This is one iteration of the bubble sort. You may have to perform several iterations.
  8. How do you know when a bubble sort is done?
    When you complete an interation and don't make any swaps you are finished sorting.
  9. Describe how a quick sort works.
    I don't know :(