Short answer: The standard ASCII table contains 128 character codes which includ

Question

Short answer:

The standard ASCII table contains 128 character codes which include upper case alpha, lower case alpha, the decimal digits, some special characters, and control characters. The extended ASCII table contains an additional 128 special characters and primitive “drawing” characters. Using the radix sort how many queues would be required for each pass to sort an array of 5,000 strings that could contain up to 10 characters each with any character being taken from the combined standard ASCII standard and ASCII extended tables? How many passes will be required? Big 0 for the radix sort is different from the other algorithms we have studied. Why is it different? Describe two factors that affect the efficiency of any given radix sort.

Explanation / Answer

As in radix sort we sort them based on chars of given string. So we sort the sort the given array if string using counting sort (or any stable sort) according to the i’th char.

In our example we have 5000 array of string with each string can contain upto 10 char So we need 10 queue to store all i'th position char in queue. and in each queue it can contain 5000 char.

Let there be d(10) char in input string. Radix Sort takes O(d*(n+b)) time where b is the base for representing string, for example, b is 256. What is the value of d? If k is the maximum possible value, then d would be O(logb(k)). So overall time complexity is O((n+b) * logb(k)). Which looks more than the time complexity of comparison based sorting algorithms for a large k. Let us first limit k. Let k <= nc where c is a constant. In that case, the complexity becomes O(nLogb(n)). But it still doesn’t beat comparison based sorting algorithms.

What if we make value of b larger?. What should be the value of b to make the time complexity linear? If we set b as n, we get the time complexity as O(n). In other words, we can sort an array of integers with range from 1 to nc if the numbers are represented in base n (or every digit takes log2(n) bits).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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