Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
10 Cards in this Set
- Front
- Back
|
(Spring 2011) Instead of using counting sort to sort digits in the radix sort algorithm, we can use any valid sorting algorithm and radix sort will still sort correctly.
|
False. Need stable sort.
|
|
|
[Spring 2009] A set of n integers whose values are in the range [0, n8) can be sorted in O(n) time.
|
True. Use radix sort with a radix of size n. Then each invocation of counting sort takes O(n + n) = O(n) time. Each element has 8 “digits”, so the total time for radix sort is O(8n) = O(n).
|
|
|
[Fall 2009] Heapsort is not a stable sorting algorithm.
|
True
|
|
|
[Fall 2009] Finding the minimum element of a binary min heap takes logarithmic time.
|
False
|
|
|
[Fall 2009] Any type of sorting algorithm can be used to sort the digits in one phase of radix sort.
|
False
|
|
|
[Spring 2008] To sort n integers in the range from 1 to n2, a good implementation of radix sort is asymptotically faster in the worst case than any comparison sort.
|
True. Split each number into two digits, each between 0 and n. Then make two passes of counting sort, each taking θ(n) time. Any comparison sort will take Ω(n log n) time.
|
|
|
[Spring 2008] Call an ordered pair (x1,y1) of numbers lexically less than an ordered pair (x2,y2) if either (i)x1 < x2 or(ii)x1 = x2 and y1 < y2. Then a set of ordered pairs can be sorted lexically by two passes of a sorting algorithm that only compares individual numbers.
|
True. The idea is similar to RADIX-SORT though it is not exactly the same. First we sort on the yi digit of each pair, (xi, yi). Next we sort on the xi digit using a stable sort.
|
|
|
[Spring 2008] Any in-place sorting algorithm can be used as the auxiliary sort in radix sort.
|
False. The auxiliary algorithm has to be stable. In-place means the algorithm only uses constant additional memory.
|
|
|
[Spring 2008] Every sorting algorithm requires Ω(n lg n) comparisons in the worst case to sort n elements.
|
False. Counting sort, radix sort, and bucket sort all sort in fewer than O(n lg n) comparisons. The lower bound only applies to comparison sorts.
|
|
|
[Fall 2008] The running time of Radix sort is effectively independent of whether the input is already sorted.
|
True. All input orderings give the worst-case running time; the running time doesn’t depend on the order of the inputs in any significant way.
|
