Chapter 7 (Sorting) Flashcards
In a lower bound simple sort, how many swaps does it take to sort?
The number of inversions that are present
T/F Radix sort sorts by each digit, least significant first
T
What is sorting in main memory called?
Interal sorting
In a bucket sort, initialize the array to all ____
Zeroes
What does the running time of a shell sort depend on?
The increment sequence
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
Shell sort
What approach does quick sort use?
Divide and conquer
What is the running time of a Radix sort?
O(N)
What is a shell sort sometimes called?
Diminishing sequence sort or diminishing increment sort
What is the running time of a deleteMin in a heap sort?
O(log N)
How do you a fix a descending order list in a heap sort?
Build a maxheap instead of a minheap
What is the running time of the shell sorts Hibbard’s sequence?
Theta (N^(3/2))
T/F In Multiway Merge, if there are k tapes to merge, then the largest value across the k tapes must be found
F, smallest value
How is a list sorted using a merge sort?
Recursively split into 2 smaller lists which are sorted
What might large sets of data require utilizing?
Tape or disk
What can give you an efficiency improvement in a quick sort?
Median-of-3
What is a 1-sort the same as?
Insertion sort
What is it called when data requires tape or disk?
External sorting
In a bucket sort, you should start with an array size of ____
M
T/F In a bucket sort, input consists of integer values less than M
T
Any algorithm for sorting that uses only comparisons requires ____ comparisons (and hence time) in the worst case
Ω(N log N)
What is one drawback of a multiway merge?
In a k-way merge, 2k tapes are needed
What is the final step of a shell sort?
1-sort
What is the running time of the shell sorts Sedgewick sequence?
O(N^(4/3))
T/F Elements in 0 through p-1 in an insertion sort are known to be sorted
T
What does comparison-based sorting assume?
The data being sorted supports the Comparable interface
What is the fastest sorting algorithm known in practice?
Quicksort
For an insertion sort of N items, what is the worst case for the number of swaps required?
N(N-1)/2
Why is the first element not good for a pivot in quick sort?
List may already be in sorted order
What is the worst case running time of a bucket sort?
O(M + N)
What is the worst case running time for a quicksort if the pivot is always the smallest value?
Theta(N^2)
What is the worst case running time for a quicksort if the pivot is always the median value?
Theta(N log N)
How many passes does it take for an insertion sort?
N - 1
To sort N records in runs of M in an external sort, how many passes are needed?
log(N/M) ceiling + initial pass
What is the lower bound of a shell sort?
Ω (N^2)
In an insertion sort, if data is already sorted, what is the running time and why?
O(N) because the inner loop would be skipped
Shellsort rearranges the array so that elements spaced ____-distance apart throughout the array are sorted
h sub k
What is the worst case running time of Quickselect?
O(N^2)
What is the upper bound of a shell sort?
O(N^2)
In the lower bound for simple sorts, what is the running time?
O(I + N) where I is the number of inversions
What is the running time for the heap sort?
O(N log N)
How can you beat an Ω (N^2) running time for a swap algorithm?
Compare and exchange elements farther apart from each other
What was one of the first sorting algorithms to break the quadratic time barrier?
Shell sort
A pair of elements in a list that are not in sorted order is called an ____
Inversion
How many deleteMin’s are required in a heap sort?
N
T/F Every list can be expressed as a decision tree
T
What is the running time of the shell sorts original sequence?
Theta (N^2)
What is the running time of insertion sort?
O(N^2)
What is the running time of a merge sort?
O(N log N)
Shell sort is an extension of ____ sort which gains speed by allowing exchanges of elements that are far apart
Insertion
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
T
What approach does a merge sort use?
Divide and conquer
What is a common problem when working with data?
Sorting
How can a shell sort also be viewed?
Sorting columns of data
How do simple sorts remove inversions?
Swapping adjacent elements
What does the heap sort make use of?
Heap data structure
the total inversions for both lists together would be ____
N(N-1)/2
How can quicksort be implemented?
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
What are two ways to solve the recurrence formula for a merge sort?
Telescoping a sum Repeated substitution
Where can small sets of data be sorted?
In main memory
T/F Data is often collected in unsorted order and must be sorted for reporting or other processing
T
What is the worst case run time of a quick sort?
O(N^2)
T/F Shellsort running time analysis is easy
F, difficult
