Study your flashcards anywhere!
Download the official Cram app for free >
 Shuffle Toggle OnToggle Off
 Alphabetize Toggle OnToggle Off
 Front First Toggle OnToggle Off
 Both Sides Toggle OnToggle Off
 Read Toggle OnToggle Off
How to study your flashcards.
Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key
Up/Down arrow keys: Flip the card between the front and back.down keyup key
H key: Show hint (3rd side).h key
A key: Read text to speech.a key
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 RADIXSORT 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 inplace sorting algorithm can be used as the auxiliary sort in radix sort.

False. The auxiliary algorithm has to be stable. Inplace 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 worstcase running time; the running time doesn’t depend on the order of the inputs in any significant way.
