GROUP ACTIVITY - Sorting Review

• Complete the following table with the properties of the indicated sorts. DON'T JUST LOOK UP THE ANSWERS SCAVENGER-HUNT-STYLE. The point of this exercise is to think about what you know about each sort and its behavior. It would not be very useful to memorize the entries in this table. It is useful to get the the point where you know the sorts well enough to answer the questions based on your own understanding. In other words, you should be able to justify all of your answers in this table.

  Your answers should be as precise as possible. For example, we can give an exact number for the worst-case number of comparisons for selection sort: \(\frac{n(n-1)}{2} \in \Theta(n^2)\). On the other hand, it isn't possible to have an exact number for the worst case time for selection sort. We can only use asymptotic notation to describe how the running time grows as a function of the input size.

  (Note that an "in-place" sort is a sort that doesn't require any additional space beyond the space required to store the input.)

  	Worst-Case Comparisons	Worst-Case Assignments	Worst-Case Time	Best-Case Time	Average Time	In place?	Stable?
  Selection Sort
  Insertion Sort
  Mergesort
  Quicksort
  Radix Sort

• Choose the best sorting algorithm for each of the following scenarios. You should choose from among selection sort, insertion sort, quicksort, and mergesort. In each case, justify your answer.

  • You need to sort a large list of unordered medical records by both date of birth and last name. After sorting, the list should be ordered by date of birth, with individuals who have the same date of birth ordered according to their last name. This will be accomplished by applying the same sorting algorithm twice: sorting first by name, then by date.

   

   

   

  • You are sorting shipping containers according to their scheduled departure time. The arrangement of the warehouse makes it impossible to reorder all of the containers at once. There is only room to swap one pair of containers at a time.

   

   

   

• Dr. Arugorizumu has recently submitted a paper claiming that he has developed a \(\Theta(n)\) comparison-based algorithm for within-two-sorting an array. He claims that, while the algorithm is not guaranteed to completely sort a sequence, it does guarantee that each key will end up no more than two positions away from its correct sorted location. Is this claim believable? Why or why not?