Question

You are given a list of strings L = {s1,s2 ...sn}. Each si is a string of up to 26 English characters. For example, L consists of the following strings:

{s1, 82... Sn}. Each s; is a string of up to 26 English 13. You are given a list of of strings L = characters. For example L consists of the following strings: S1 =hello', S2 = 'world, s3 = 'what', s4 = 'a', 85 = 'nice', s6 = 'day', s7 = 'which', s8 abcdefghijklmnopqrstuvwxyz', s9 = 'where You need to sort this list lexicographically. So the order after the sorting, the list will be in the following order а, abcde fghijklmnopqrstuvuхуг. day, hellо, nice, what, where, which, world, Assume every character is represented as an ASCII character with 8 bits. You would like to use Radix Sort. Remember that during counting sort, you have to decide about the base by which you represent the keys, since the array C has a cell for each item. For example, if you opt for base 2, then C has two cells. For example, you could use binary, base 4, base 8 etc. So before starting the algorithm, which of the following options would you pick? (a) Base 2. In this case, the number of times Counting Sort is executed is called is = 420. Each call to Counting Sort performs a sort based on only 8bits/char *50character one bit (b) Base 8. That is, the last pass of Counting is performed on the most-significant 3 bits. So the number of times Radix is called is only [8pits/char *50character/3] = 420. (c) Base 256. That is, the last pass of Counting us performed on the most-significant 8 bits. So the number of times Radix is called is only [8hits/char * 50character/3] = 140. (d) Base 2420. So only one pass of Counting Sort is needed Assume that n, the number of strings in L is 10 billion

Answer 1

In my opinion, I would pick option (b).

Reason:
Last pass of counting is performed on the most significant 3 bits. Most of the words can be sorted using this as almost all the words might have different alphabets on the three most significant bits and there won't be a need to sort them again as they will get sorted completely. This will consume less memory and will be efficient.

Algorithm:

Radix Sort works on bucket system.
In this case, the algorithm will be as follows.

1. Start.
2. Compare the least significant bit of all the strings in the array.
3. If ASCII value of the character at LSB of the comparision string is greater than ASCII value of the character at LSB of the first string, interchange.
4. Else, compare it with next string, and so on.
5. If all the comparisions are over, move to next LSB.
6. Repeat steps 2 to 5 until you reach the Most Signnificant Bit.
7. Compare all the MSB and If ASCII value of the character at MSB of the comparision string is greater than ASCII value of the character at MSB of the first string, interchange.
8. Else, Stop.

COMMENT DOWN FOR ANY QUERIES AND ,

LEAVE A THUMBS UP IF THIS ANSWER HELPS YOU.