Carry out radix sort (only three pass) on the following 3-character words in order to sort them in ascending order. Also state time complexity of given procedure.
Question
Carry out radix sort (only three pass) on the following 3-character words in order to sort them in ascending order. Also, the state the time complexity of the given procedure.
COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB
Summary
We must use radix sort to sort the items in the supplied question. To sort the entire number, we do a radix sort by sorting the elements by their digit locations (1’s digit, 10’s digit, 100’s digit).
To sort the elements, we use a counting sort.
Explanation
Counting sort has an O(n+k) time complexity.
Radix sort has an O time complexity (n.k)
The difficulty in this question is O(n2).
The answer is:
COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB
In radix sort, we perform the sequence by sorting its radix
COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB
We perform counting sort.
| 1) | A | B | G | K | O | P | W | X |
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Count | 1 | 2 | 2 | 0 | 0 | 0 | 2 | 1 |
| 2) Add the previous count |
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Count | 1 | 3 | 5 | 5 | 5 | 5 | 7 | 8 |
1)Output String
SEA, MOB,TUB,DOG, RUG,COW,ROW,BOX
Sorting by next radix
SEA, MOB,TUB,DOG, RUG,COW,ROW,BOX
1) Applying counting sort
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Count | 0 | 1 | 0 | 5 | 0 | 0 | 2 | 0 |
Add previous
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Count | 0 | 1 | 1 | 6 | 6 | 6 | 8 | 8 |
Output
SEA, MOB,TUB,DOG, RUG,COW,ROW,BOX
Sorting by next radix
SEA, MOB,TUB,DOG, RUG,COW,ROW,BOX
1)Counting sort
| B | C | D | M | P | R | S | T | |
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Count | 1 | 1 | 1 | 1 | 0 | 2 | 1 | 1 |
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Count | 1 | 2 | 3 | 4 | 4 | 6 | 7 | 8 |
Output
BOX, COW, DOG, MOB, ROW, RUG, SEA, TUB
Sorted sequence:
BOX, COW, DOG, MOB, ROW, RUG, SEA, TUB
Also, read a pointer that points to an array in C.
