Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures (Ozbirn) > Chapter 7 (Sorting) > Flashcards

Chapter 7 (Sorting) Flashcards

1
Q

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

A

The number of inversions that are present

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is sorting in main memory called?

A

Interal sorting

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

In a bucket sort, initialize the array to all ____

A

Zeroes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

The increment sequence

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

Shell sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What approach does quick sort use?

A

Divide and conquer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the running time of a Radix sort?

A

O(N)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a shell sort sometimes called?

A

Diminishing sequence sort or diminishing increment sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

O(log N)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

Build a maxheap instead of a minheap

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

Theta (N^(3/2))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

F, smallest value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How is a list sorted using a merge sort?

A

Recursively split into 2 smaller lists which are sorted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What might large sets of data require utilizing?

A

Tape or disk

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

Median-of-3

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is a 1-sort the same as?

A

Insertion sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is it called when data requires tape or disk?

A

External sorting

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

A

M

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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

A

Ω(N log N)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is one drawback of a multiway merge?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is the final step of a shell sort?

A

1-sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

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

A

O(N^(4/3))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

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

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What does comparison-based sorting assume?

A

The data being sorted supports the Comparable interface

27
Q

What is the fastest sorting algorithm known in practice?

A

Quicksort

28
Q

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

A

N(N-1)/2

29
Q

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

A

List may already be in sorted order

30
Q

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

A

O(M + N)

31
Q

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

A

Theta(N^2)

32
Q

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

A

Theta(N log N)

33
Q

How many passes does it take for an insertion sort?

A

N - 1

34
Q

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

A

log(N/M) ceiling + initial pass

35
Q

What is the lower bound of a shell sort?

A

Ω (N^2)

36
Q

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

A

O(N) because the inner loop would be skipped

37
Q

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

A

h sub k

38
Q

What is the worst case running time of Quickselect?

A

O(N^2)

39
Q

What is the upper bound of a shell sort?

A

O(N^2)

40
Q

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

A

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

41
Q

What is the running time for the heap sort?

A

O(N log N)

42
Q

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

A

Compare and exchange elements farther apart from each other

43
Q

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

A

Shell sort

44
Q

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

A

Inversion

45
Q

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

A

N

46
Q

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

A

T

47
Q

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

A

Theta (N^2)

48
Q

What is the running time of insertion sort?

A

O(N^2)

49
Q

What is the running time of a merge sort?

A

O(N log N)

50
Q

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

A

Insertion

51
Q

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

A

T

52
Q

What approach does a merge sort use?

A

Divide and conquer

53
Q

What is a common problem when working with data?

A

Sorting

54
Q

How can a shell sort also be viewed?

A

Sorting columns of data

55
Q

How do simple sorts remove inversions?

A

Swapping adjacent elements

56
Q

What does the heap sort make use of?

A

Heap data structure

57
Q

the total inversions for both lists together would be ____

A

N(N-1)/2

58
Q

How can quicksort be implemented?

A

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

59
Q

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

A

Telescoping a sum Repeated substitution

60
Q

Where can small sets of data be sorted?

A

In main memory

61
Q

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

A

T

62
Q

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

A

O(N^2)

63
Q

T/F Shellsort running time analysis is easy

A

F, difficult

Data Structures (Ozbirn) (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions