Problem 2. Lecture 7 presented radix sort as performed on integers; this problem

Question

Problem 2. Lecture 7 presented radix sort as performed on integers; this problem explores radix sort performed on strings. a) Consider the following list of four-letter words (not that kind, don't worry): PATH PAST FAST CHIP HOME List the words in the order they would appear after two passes of radix sort done top-to-bottom using lexicographic (i.e. alphabetical) ordering. Order the list least-to-greatest from top to bottom: (lexicographically least) (lexicographically greatest) b) Give a list of five 4-character strings (they do not have to be real words) on which radix sort would return an incorrect answer if done in most-significant- to least-significant-position order Assume the radix sort scans the list from top to bottom on each pass. c) If radix sort as presented in Lecture 7 were implemented on same-length strings of English and Chinese characters, which implementation would be faster on a small input set of 100 strings in the worst case? Consider relevant constant factors. Why?

Explanation / Answer

b)

abcd

abdc

pqrs

qprs

radix sort from most significat will sort this into

abdc

abcd

pqrs

qprs

which is wrong

right order is

abcd

abdc

pqrs

qprs

c)

Implementation on English language wil work faster as English language has only 26 characters but chinnese has 50,000+ chacrters so constant factor for sorting one charcter in one pass of radix sort will be high and chinnese sort will be slower.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.