Questions Chapter 7

Question 1

The Shellsort works by:

a. partitioning the array
b. swapping adjacent elements
c. dealing with widely separated elements
d. starting with the normal insertion sort.

Answer 1

c. dealing with widely separated elements

Question 2

If an array has 100 elements, then Knuth’s algorithm would start with an interval of _____.

Answer 2

40

Question 3

To transform the insertion sort into the Shellsort, which of the following do you NOT do?

a. substitute h for 1
b. insert an algorithm for creating gaps of decreasing width
c. enclose the normal insertion sort in a loop
d. change the direction of the indices in the inner loop

Answer 3

d. change the direction of the indices in the inner loop

Question 4

True or False: a good interval sequence for the Shellsort is created by repeatedly dividing the array size in half.

Answer 4

False

Question 5

Fill in the big O values: The speed of the Shellsort is more than _______ but less than _______.

Answer 5

Shellsort speed more than O(N^2), but less than O(N*logN)

Question 6

Partitioning is:

a. putting all the elements larger than a certain value on one end of the array
c. dividing an array in half
d. sorting each half of an array separately

Answer 6

a. putting all the elements larger than a certain value on one end of the array

Question 7

When partitioning, each array element is compared to the _________.

Answer 7

pivot

Question 8

In partitioning, if an array element is equal to the pivot:

a. it is passed over
b. it is passed over or not, depending on the other array element
c. it is placed in the pivot position
d. it is swapped

Answer 8

d. it is swapped

Question 9

True or False: In quicksort, the pivot can be an arbitrary element of the array

Answer 9

True

Question 10

Assuming larger keys on the right, the partition is:

a. the element between the left and right subarrays
b. the key value of the element between the left and right subarrays
c. the left element in the right subarray
d. the key value of the left element in the right subarray

Answer 10

c. the left element in the right subarray

Question 11

QuickSort involves partitioning the original array and then ______________________.

Answer 11

recursively calling recQuickSort

Question 12

After a partition in a simple version of quickSort, the pivot may be:

a. used to find the median of the array
b. exchanged with an element of the right subarray
c. used as the starting point of the next partition
d. discarded

Answer 12

d. discarded

Question 13

Median-of-three partitioning is a way of choosing the _________.

Answer 13

pivot

Question 14

In quicksort, for an array of N elements, the partitionIt( ) method will examine each element approximately ________ times

Answer 14

n+2

Question 15

True or False: you can speed up quicksort if you stop partitioning when the partition size is 5 and finish by using a different sort

Answer 15

True

Question 16

The expression _____________ means sorting every nth element.

Answer 16

n-sorting

Question 17

A sequence of numbers, called the _______ ________ or ______ ________, is used to determine the sorting intervals in the Shellsort

Answer 17

interval sequence or gap sequence

Question 18

A widely used interval sequence is generated by the recursive expression __________, where the initial value of __ is 1.

Answer 18

interval sequence recursive expression: h=3*h+1

initial value of h is 1

Question 19

The _______ is the value that determines into which group an item will go during partitioning. Items _______ than the _____ go in the ______ group; _______ items go in the ______ group.

Answer 19

the pivot value.
items smaller than the pivot go in the left group.
items larger go in the right group.

Question 20

In the partitioning algorithm, two array indices, each in its own ________ _______, start at opposite ends of the array and step toward each other, looking for items that need to be _______.

Answer 20

each in its own while loop.

items that need to be swapped.

Question 21

Partitioning operates in ______ time, making N plus 1 or 2 comparisons and fewer than N/2 swaps

Answer 21

O(N) time

Question 22

Quicksort partitions an array and then calls itself recursively _______ number of times to sort the remaining subarrays.

Answer 22

calls itself recursively 2 times

Question 23

During the partition, the _____ is placed out of the way on the _______ side, and is not involved in the partitioning process

Answer 23

pivot is placed out of the way on the right side

Question 24

In the simple version of quicksort, performance is only ______ for already sorted (or inversely sorted) data.

Answer 24

O(N^2) time

Question 25

In the more advanced version of quicksort, the pivot can be the ______ of the first, last, and centre items in the subarray. This is called the ____________________ partitioning

Answer 25

median. median-of-three partitioning.

Question 26

Median-of-three partitioning effectively eliminates the problem of _______ performance for already sorted data.

Answer 26

O(N^2) performance for already sorted data

Question 27

Subarrays smaller than the cutoff can be sorted by ___________ sort.

Answer 27

insertion sort

Question 28

The _______ sort is about as fast as quicksort, but uses twice as much memory

Answer 28

radix sort