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.