Questions Chapter 3

Question 1

Computer sorting algorithms are more limited than humans in that:

a. humans are better at inventing new algorithms.
b. computers can handle only a fixed amount of data
c. humans know what to sort, whereas computers need to be told
d. computers can compare only two things at a time

Answer 1

d. computers can compare only two things at a time

Question 2

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

Answer 2

comparing items, moving them ( or sometimes swapping them)

Question 3

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

Answer 3

False

Question 4

The bubble sort algorithm alternates between:

a. comparing and swapping
b. moving and copying
c. moving and comparing
d. copying and comparing

Answer 4

a. comparing and swapping

Question 5

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

Answer 5

False

Question 6

In the selection sort:

a. the largest keys accumulate on the left (low indices)
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.

Answer 6

b. a minimum key is repeatedly discovered

Question 7

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

Answer 7

True

Question 8

A copy is _____ times as fast as a swap

Answer 8

3

Question 9

What is the invariant in the selection sort?

Answer 9

Data items with indices less than or equal to out.

Question 10

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

a. in
b. out
c. temp
d. a[out]

Answer 10

c. temp

Question 11

In the insertion sort, “partially sorted” 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.

Answer 11

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

Question 12

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

Answer 12

copies

Question 13

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

a. never be moved again
b. never be shifted to the left
c. often be moved out of this group
d. find that its group is steadily shrinking

Answer 13

b. never be shifted to the left

Question 14

The invariant in the insertion sort is that _______________________________.

Answer 14

data items with smaller indices than outer.

Question 15

Stability might refer to:

a. items with secondary keys being excluded from a sort
b. keeping cities 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

Answer 15

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

Question 16

Bubble sort, selection sort, and insertion sort execute in _______ time.

Answer 16

O(N^2)

Question 17

A(n) _________ is a condition that remains unchanged while an algorithm runs.

Answer 17

invariant

Question 18

The ___________ sort is the least efficient, but the simplest sort.

Answer 18

bubble

Question 19

The ___________ sort is the most commonly used of bubble, selection, and insertion sorts.

Answer 19

insertion sort

Question 20

A sort is ______ if the order of elements with the same key is retained.

Answer 20

stable