Question

1a)Giving an array of integers A[1:8] ={5, 1, 3, 2, 7, 6, 8, 4}.

What is the running time of the insertion sort if both A[1..n/2] and A[n/2+1,n] are also sorted. Justify your answer.

2-illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, TEA, NOW, FOX.

3-Use counting sort, sort the following numbers: 4, 2, 5, 4, 2, 3, 0, 2, 4, 3

Answer 1

Q.1 If the arrays are sorted in ascendign order, the best case occurs which is O(n), while if the array is sorted in descending order, worst case occurs which result in complexity of O(n²). So according to array given, if 8 element are there and both half arrays are sorted ascending then running time complexity will be n i.e 8. But if the arrays are sorted in descending order then complexity will be n² result in 64.

Q.2

Bucketing on char 0 from the right
[65] SEA -> TEA
[66] MOB -> TAB
[71] DOG -> RUG -> DIG
[82] BAR -> EAR -> TAR
[87] COW -> ROW -> NOW
[88] BOX -> FOX

SEA -> TEA -> MOB -> TAB -> DOG -> RUG -> DIG -> BAR -> EAR -> TAR -> COW -> ROW -> NOW -> BOX -> FOX
Bucketing on char 1 from the right
[65] TAB -> BAR -> EAR -> TAR
[69] SEA -> TEA
[73] DIG
[79] MOB -> DOG -> COW -> ROW -> NOW -> BOX -> FOX
[85] RUG

TAB -> BAR -> EAR -> TAR -> SEA -> TEA -> DIG -> MOB -> DOG -> COW -> ROW -> NOW -> BOX -> FOX -> RUG
Bucketing on char 2 from the right
[66] BAR -> BOX
[67] COW
[68] DIG -> DOG
[69] EAR
[70] FOX
[77] MOB
[78] NOW
[82] ROW -> RUG
[83] SEA
[84] TAB -> TAR -> TEA

BAR -> BOX -> COW -> DIG -> DOG -> EAR -> FOX -> MOB -> NOW -> ROW -> RUG -> SEA -> TAB -> TAR -> TEA

BAR
BOX
COW
DIG
DOG
EAR
FOX
MOB
NOW
ROW
RUG
SEA
TAB
TAR
TEA

Q.3

I hope it helps.
Thank you