1. Suppose we are given an array of integers, but instead of all integers having
ID: 668637 • Letter: 1
Question
1. Suppose we are given an array of integers, but instead of all integers having the same length they can each have a different number of bits. So e.g. the number 0 or 1 takes one bit, the numbers 2, 3 take 2 bits, the numbers 4, 5, 6, 7 take three bits, etc. However, the total number of bits over all of the integers in the array is equal to n. Show how to sort the array in O(n) time.
2. Suppose now that we are given an array of strings (over some finite alphabet, say the letters a-z). Each string can have a different number of characters, but the total number of characters in all the strings (i.e. the sum over the strings of the length of the string) is equal to n. Show to sort the strings lexicographically in O(n) time. Here lexicographic order is the standard alphabetic order, so for example a < ab < b.
I know the #1 must be a bucket sort or radix sort, but I can't think of a formal way of writing it. For #2, I have no clue. Can someone help me?
Explanation / Answer
Answer:
1.
In order to sort the array of integers with in a given time complexity of O(n), then it is recommended to use the Radix sort with the help of Count sort.
The algorithm is given as,
Algorithm RadixSort(arr[], n):
//find the maximum number’s count of digits
m = getMaximum(arr, n)
for (exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n , exp)
end
end
Algorithm getMaximum(arr[], n):
max = arr[0]
for i = 1 to n
if arr[i] > max
max = arr[i]
endif
end
return max
end
Algorithm countSort(array[], n, exp):
output[n]
i, count[10]={0}
//store the count of occurrence in array count
for i = 1 to n
count[(array [i]/exp)%10]++
end
//convert the count[i] such that it contains original position
//of present digit in the output array
for i = 1 to 10
count[i] +=count[i-1]
end
//Now store the elements into output array
for i = n-1 to 0
output[count[(array [i]/exp)%10]-1] = array [i]
count[(array [i]/exp)%10] = count[(array [i]/exp)%10]-1
end
//copy the elements in the output array into the original array
for I = 1 to n
array[i] = output[i]
end
end
Actually the algorithm runs in O(d*(n+b)) time where d is the number of digits and b is base representation of numbers.
Here, base is 10 and d is the 2-digit number to the base n.
So, O(d(n+b)=O(2*(n+n)) = O(n)
Therefore, the running time of the algorithm is given as O(n).
2.
This problem can also be sorted using Radix sort. But the strings are of varying lengths, so padding of the strings is required in order to make the shorter string equal to the larger string.
But padding the string and sorting does not always gives the correct required time bound.
Suppose, there are m strings and the longest string among the m strings contains d characters.
According to part(a), the padding has to done at character n/2 in worst case.
Therefore, d = n/2 and m = (n/2)+1. Assume the range of the single character is constant. The running time of radix sort would be O(dm) = O(n2).
Let us consider the counting sort in order to obtain the actual sort by counting the number of times each string is sorted.
Assume that the j’th string Sj has length Lj. Then Si is sorted at the most Lj+1 counting sorts.
A call of the counting sort on k strings be takes O(k) time.
Thus, the total time for all calls of counting sort is
Thus, the running time is O(n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.