Quiz 3 Simple Sorting

COP 3540 Spring 2007

Quiz 3 – Simple Sorting

Name: ______

Directions: Put the letter of your choice over the dotted lines accompanying each question’s number. For True / False, put T or F over the dotted lines accompanying each question’s number. Fill-in: obvious.

1……… In comparing these ‘slower’ sorts with each other two features that contribute toward the lack of speed in the sort are:

a. comparisons and copies b. comparisons and swaps

c. swaps and copies d. comparisons and copies

2…….. All the sorts discuss in this chapter are ______sorts.

a. O(n) b. O(logn) c. O(log2n) d. O(n2)

3...... (True, False) The fastest of the sort types listed in the previous question will always be O(log2n).

4…..Of the sorts discussed in this chapter, that sort that will likely have the largest number of swaps is the:

a. bubble sort b. selection sort c. insertion sort d. quick sort.

5…..Of the sorts discussed in this chapter, that sort that will likely have the largest number of copies is the:

a. bubble sort b. selection sort c. insertion sort d. quick sort.

6. (True, False) Ideally, a client of a Sort class likely does not know how the method in the Sort object actually ‘insert’ or actually ‘sorts’ the target structure.

7. One big tip off that a sort provides O(n2) performance can be seen by merely looking at the algorithm. The tip off is:

8. (True, False) If we are sorting an array of objects, then a class describing the format of each of those objects must be provided in code – assuming that this is an object whose class is not defined within the API.

9……In the selection sort,

a. the largest keys accumulate on the left

b. a minimum key is repeatedly discovered

c. a number of items must be shifted to insert each item in its correctly sorted position.

d. the sorted items accumulate on the right.

10. A copy is ______times faster than a swap.

11. In the insertion sort, ‘partially ordered’ means that

a. some items are already sorted, but they may need to be moved

b. most items are in their final sorted positions, but a few still need to be sorted.

c. only some of the items are sorted

d. group items are sorted among themselves, but items outside the group may need to be inserted in it.

12. Stability might refer to

a. items with secondary keys being excluded from a sort

b. keeping cites sorted by increasing population within each state, in a sort by state

c. keeping the same first names matched with the same last names

d. items keeping the same order of primary keys without regard to secondary keys.