This chapter is from the book
This chapter is from the book
This chapter is from the book
Questions
These questions are intended as a self-test 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.