8-3 Sorting variable-length items a. You are given an array of integers, where d

Question

8-3 Sorting variable-length items
a. You are given an array of integers, where different integers may have different
numbers of digits, but the total number of digits over all the integers in the array
is n. Show how to sort the array in O.n/ time.
b. You are given an array of strings, where different strings may have different
numbers of characters, but the total number of characters over all the strings
is n. Show how to sort the strings in O.n/ time.
(Note that the desired order here is the standard alphabetical order; for example,
a < ab < b.)

Explanation / Answer

Please follow the data and description :

a) For the numbers to sort the array,

Initially, we need to group the numbers by the number of digits and order the groups followed by the Radix sort of each group.

Let Gi be the group of numbers with i digits and ci = |Gi|.

Thus,

T(n) = (sigma)i=1 [nci . i] = n.

b) For the strings/character type data to sort the array,

First group the strings by length and order the groups, then starting i on the maximum length and going down to 1, perform the counting sort on the i th character. One need to make sure to include only the groups that have an ith character.

If the groups are subsequent sub-arrays in the original array, we are performing the counting sort on a subarray ending on the last index of the original array.

Hope this is helpful.

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

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