Low budget practice problems

1. Given the array: { 4, 10, 5, 5, 7, 8, 3, 5, 6, 8 }:

What would the contents be after one pass of:

Bubblesort

Selectionsort

Insertionsort

Quicksort if the datum on the right were used as the pivot?

What would the array look like after a max-heap is built?

And then after the first element in the heap is sorted?

What two arrays would be in the final merge if mergesort were used?

2. Given the array: { 10, 7, 3, 9, 6, 4, 1, 2, 5, 8 }:

If you had to find the median and were using the datum on the right as the pivot, draw the contents of the array after each iteration of quicksort.

3. Ms. Hall at the SAC has an array containing an unsorted list of all of the names of the roughly 1800 students at Gunn. She wants you to produce ten names from that list in alphabetical order. She does not care which names you produce, but she wants to minimize the time it takes to get the results.

Mr. Bell has the code for Bubble, Insertion, Selection, Heap, Quick, and Merge sorts. He has to pass the whole array into a sorting routine, but he has a magic button that he can press to stop the sorting process at any time. Mr. Bell thinks about how he can use the magic button for a couple of seconds and then declares which sorting routine he would use in this way.

Which sort did Mr. Bell tweak and why?

4. Consider the following tables:

TABLE 1

One of these tables is the result of heap sort, the other is a result of bubble sort. Which one is which? Explain. Hint: Use both order of growth in Big-O format and an actual function to describe each table to make your argument.