Deck 11: Sorting

Question 1

__________ is the process of rearranging the data in an array or container so that the data elements are in increasing (or decreasing) order.

Answer 1

Sorting

Question 2

In a selection sort, there are at most __________ exchanges.

A) 1
B) log n
C) n
D) n - 1

Answer 2

n

Question 3

If the array happens to be sorted before selection sort begins, no exchanges will be required.

Answer 3

True

Question 4

A(n) __________ sort compares adjacent array elements and exchanges their values if they are out of order.

Question 5

In the worst case scenario, the number of comparisons performed by a bubble sort is O(__________).

A) n
B) n log n
C) n²
D) n³

Question 6

If the array bubble sort is applied to a sorted array, the number of exchanges is O(__________).

A) 0
B) 1
C) log n
D) n

Question 7

The __________ sort is a quadratic sorting algorithm based on the technique used by card players to arrange a hand of cards.

Question 8

In the best case scenario for insertion sort, the maximum number of comparisons is O(__________).

Question 9

A shift in an insertion sort requires the movement of only one item, whereas in a bubble sort or a selection sort an exchange involves a temporary item and requires the movement of __________ items.

Question 10

The error written into KW::insert function below can be corrected with the code __________.

A) (next_pos != first || *next_pos < *(next_pos - 1))
B) (next_pos != first && *(next_pos - 1)< *next_pos)
C) std::iter_swap(next_pos - 1, next_pos)
D) --next_post;

Question 11

When comparing selection sort, bubble sort, and insertion sort, we can observe that __________ sort gives the best performance for most arrays, because it takes advantage of any partial sorting that is in the array and uses less costly shifts instead of exchanges to rearrange array elements.

Question 12

A variation on insertion sort, known as Shell sort, has O(__________) or better performance.

A) 1
B) n^3/2
C) n²
D) n³

Question 13

Suppose the growth rate of a sorting routine is O(n log n). If the sorting routine is applied to an array with 1,024 items, we can expect it to perform about __________ operations.

A) 10
B) 1,024
C) 10,240
D) 1,048,576

Question 14

It is known that Shell sort is O(n²) if successive powers of __________ are used for the gap value.

Question 15

The time and space requirements for a single merge operation are each O(__________)

A) log n
B) n
C) n log n
D) n^3/2

Question 16

The total effort to reconstruct a sorted array through merging is O(__________).

A) log n
B) n
C) n log n
D) n²

Question 17

Whenever a recursive function is called, a copy of the local variables is saved on the run-time __________.

Question 18

The merge sort algorithm requires, at least temporarily, n log n extra storage locations.

Question 19

A max heap is a data structure that maintains the largest value at the top.

Question 20

For a node at position p in a heap, the right child is at __________.

A) 2p - 1
B) 2p
C) 2p + 1
D) 2p + 2

Question 21

Because we have n items to insert and each insert (or remove) is O(log n), building a heap is O(__________).

Question 22

The process by which quicksort rearranges an array into two parts around a pivot is called __________.

Question 23

If the pivot value generated by quicksort is a random value selected from the current sequence, then statistically it is expected that one-quarter of the items in the sequence will be less than the pivot value and three-quarters will be greater than the pivot value.

Question 24

In the best case scenario of quicksort, the partitioning process at each level involves moving every element into its correct partition, so quicksort is O(__________).

A) log n
B) n
C) n log n
D) n²

Question 25

If the pivot used by quicksort is always the first element of an input array, the worst possible performance occurs when the input array is sorted.