Chapter 7 (Sorting)

Question 1

In a lower bound simple sort, how many swaps does it take to sort?

Answer 1

The number of inversions that are present

Question 2

T/F Radix sort sorts by each digit, least significant first

Answer 2

T

Question 3

What is sorting in main memory called?

Answer 3

Interal sorting

Question 4

In a bucket sort, initialize the array to all ____

Answer 4

Zeroes

Question 5

What does the running time of a shell sort depend on?

Answer 5

The increment sequence

Question 6

Name this sort: Comparing and swapping distant elements at first, and the distance decreases as the algorithm runs, until the last phase when adjacent elements are compared

Answer 6

Shell sort

Question 7

What approach does quick sort use?

Answer 7

Divide and conquer

Question 8

What is the running time of a Radix sort?

Answer 8

O(N)

Question 9

What is a shell sort sometimes called?

Answer 9

Diminishing sequence sort or diminishing increment sort

Question 10

What is the running time of a deleteMin in a heap sort?

Answer 10

O(log N)

Question 11

How do you a fix a descending order list in a heap sort?

Answer 11

Build a maxheap instead of a minheap

Question 12

What is the running time of the shell sorts Hibbard’s sequence?

Answer 12

Theta (N^(3/2))

Question 13

T/F In Multiway Merge, if there are k tapes to merge, then the largest value across the k tapes must be found

Answer 13

F, smallest value

Question 14

How is a list sorted using a merge sort?

Answer 14

Recursively split into 2 smaller lists which are sorted

Question 15

What might large sets of data require utilizing?

Answer 15

Tape or disk

Question 16

What can give you an efficiency improvement in a quick sort?

Answer 16

Median-of-3

Question 17

What is a 1-sort the same as?

Answer 17

Insertion sort

Question 18

What is it called when data requires tape or disk?

Answer 18

External sorting

Question 19

In a bucket sort, you should start with an array size of ____

Answer 19

M

Question 20

T/F In a bucket sort, input consists of integer values less than M

Answer 20

T

Question 21

Any algorithm for sorting that uses only comparisons requires ____ comparisons (and hence time) in the worst case

Answer 21

Ω(N log N)

Question 22

What is one drawback of a multiway merge?

Answer 22

In a k-way merge, 2k tapes are needed

Question 23

What is the final step of a shell sort?

Answer 23

1-sort

Question 24

What is the running time of the shell sorts Sedgewick sequence?

Answer 24

O(N^(4/3))

Question 25

T/F Elements in 0 through p-1 in an insertion sort are known to be sorted

Answer 25

T

Question 26

What does comparison-based sorting assume?

Answer 26

The data being sorted supports the Comparable interface

Question 27

What is the fastest sorting algorithm known in practice?

Answer 27

Quicksort

Question 28

For an insertion sort of N items, what is the worst case for the number of swaps required?

Answer 28

N(N-1)/2

Question 29

Why is the first element not good for a pivot in quick sort?

Answer 29

List may already be in sorted order

Question 30

What is the worst case running time of a bucket sort?

Answer 30

O(M + N)

Question 31

What is the worst case running time for a quicksort if the pivot is always the smallest value?

Answer 31

Theta(N^2)

Question 32

What is the worst case running time for a quicksort if the pivot is always the median value?

Answer 32

Theta(N log N)

Question 33

How many passes does it take for an insertion sort?

Answer 33

N - 1

Question 34

To sort N records in runs of M in an external sort, how many passes are needed?

Answer 34

log(N/M) ceiling + initial pass

Question 35

What is the lower bound of a shell sort?

Answer 35

Ω (N^2)

Question 36

In an insertion sort, if data is already sorted, what is the running time and why?

Answer 36

O(N) because the inner loop would be skipped

Question 37

Shellsort rearranges the array so that elements spaced \_\_\_\_-distance apart throughout the array are sorted

Answer 37

h sub k

Question 38

What is the worst case running time of Quickselect?

Answer 38

O(N^2)

Question 39

What is the upper bound of a shell sort?

Answer 39

O(N^2)

Question 40

In the lower bound for simple sorts, what is the running time?

Answer 40

O(I + N) where I is the number of inversions

Question 41

What is the running time for the heap sort?

Answer 41

O(N log N)

Question 42

How can you beat an Ω (N^2) running time for a swap algorithm?

Answer 42

Compare and exchange elements farther apart from each other

Question 43

What was one of the first sorting algorithms to break the quadratic time barrier?

Answer 43

Shell sort

Question 44

A pair of elements in a list that are not in sorted order is called an \_\_\_\_

Answer 44

Inversion

Question 45

How many deleteMin's are required in a heap sort?

Answer 45

N

Question 46

T/F Every list can be expressed as a decision tree

Answer 46

T

Question 47

What is the running time of the shell sorts original sequence?

Answer 47

Theta (N^2)

Question 48

What is the running time of insertion sort?

Answer 48

O(N^2)

Question 49

What is the running time of a merge sort?

Answer 49

O(N log N)

Question 50

Shell sort is an extension of ____ sort which gains speed by allowing exchanges of elements that are far apart

Answer 50

Insertion

Question 51

T/F Shell sort works by comparing and swapping distant elements at first, and the distance decreases as the algorithm runs, until the last phase when adjacent elements are compared

Answer 51

T

Question 52

What approach does a merge sort use?

Answer 52

Divide and conquer

Question 53

What is a common problem when working with data?

Answer 53

Sorting

Question 54

How can a shell sort also be viewed?

Answer 54

Sorting columns of data

Question 55

How do simple sorts remove inversions?

Answer 55

Swapping adjacent elements

Question 56

What does the heap sort make use of?

Answer 56

Heap data structure

Question 57

the total inversions for both lists together would be \_\_\_\_

Answer 57

N(N-1)/2

Question 58

How can quicksort be implemented?

Answer 58

Partitioning an array so that values on the left side are less than the pivot, and values on the right side are greater than the pivot

Question 59

What are two ways to solve the recurrence formula for a merge sort?

Answer 59

Telescoping a sum Repeated substitution

Question 60

Where can small sets of data be sorted?

Answer 60

In main memory

Question 61

T/F Data is often collected in unsorted order and must be sorted for reporting or other processing

Answer 61

T

Question 62

What is the worst case run time of a quick sort?

Answer 62

O(N^2)

Question 63

T/F Shellsort running time analysis is easy

Answer 63

F, difficult