Questions
These questions are intended as a selftest for readers. Answers may be found in Appendix C.

Computer sorting algorithms are more limited than humans in that

humans are better at inventing new algorithms.

computers can handle only a fixed amount of data.

humans know what to sort, whereas computers need to be told.

computers can compare only two things at a time.

The two basic operations in simple sorting are _________ items and _________ them (or sometimes _________ them).

True or False: The bubble sort always ends up comparing every item with every other item.

The bubble sort algorithm alternates between

comparing and swapping.

moving and copying.

moving and comparing.

copying and comparing.

True or False: If there are N items, the bubble sort makes exactly N*N comparisons.

In the selection sort,

the largest keys accumulate on the left (low indices).

a minimum key is repeatedly discovered.

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

the sorted items accumulate on the right.

True or False: If, in a particular sorting situation, swaps take much longer than comparisons, the selection sort is about twice as fast as the bubble sort.

A copy is ________ times as fast as a swap.

What is the invariant in the selection sort?

In the insertion sort, the "marked player" described in the text corresponds to which variable in the insertSort.java program?

in

out

temp

a[out]

In the insertion sort, "partially sorted" means that

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

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

only some of the items are sorted.

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

Shifting a group of items left or right requires repeated __________.

In the insertion sort, after an item is inserted in the partially sorted group, it will

never be moved again.

never be shifted to the left.

often be moved out of this group.

find that its group is steadily shrinking.

The invariant in the insertion sort is that ________.

Stability might refer to

items with secondary keys being excluded from a sort.

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

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

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