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: BLUE = Sorted data

Bubblesort

Selectionsort

Insertionsort (note that the 0th datum is sorted to begin with, so the first pass starts at index 1)

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? (red data are array1 , black data are array2)

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.

RED = Unsorted data, BLUE = sorted data, BLACK = sorted data that is part of the median

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?

This is a somewhat misguided test question because all of the sorts can be applied to the first 10 elements of the array. Selection sort would need 45 comparisons and up to 9 swaps. Insertion would be better on average in terms of comparisons, but would have more swaps. Bubble would take similar time to selection. Heap would be a lot of work to set up and O(nlogn) isn't particularly interesting for small n. Same for quick and merge. Quick supposedly uses insertion when it gets to 5 elements or fewer, so after one or two chops, it would be more or less insertion.

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.

The first one is heap, the second bubble. The first example is roughly f(n) = 2nlogn. The second is g(n) = .02n².