Question

6. The worst case scenario in the quick sort occurs when the array is partitioned to two equal sized subarray every time that a recursive call takes place.

True

False

7.Suppose that we want to sort an array of n elements, where each element is a string of at most 1000 characters. What is the time requirement for applying radix sort to sort this array?

		O(n2)
		O(1000n)
		O(l000logn)
		O(nlogn)

8.Suppose we want to sort the following array of integers using radix sort:

a=[14 682 120 50 327]

What are the intermediate steps?

		pass1: 14 682 120 50 327 pass2: 14 50 120 682 327 pass3: 14 50 120 327 682
		pass1: 14 682 120 50 327 pass2: 14 120 682 50 327 pass3: 14 50 120 682 327 pass4:14 50 120 327 680
		pass1: 14 50 120 327 682
		pass1: 120 50 682 14 327 pass2: 14 120 327 50 682 pass3: 14 50 120 327 682

9.What are the intermediate steps for patitioning the folloiwng array when taking the pivot as the median of the first,middle, and last items (suppse that the threshold for calling insertion sort is an array of size 2)

a= [12 5 8 6 9 11 10 ]

		[6 5 8 10 9 11 12] [6 5 8 11 9 10 12] [6 5 8 9 11 10 12] [6 5 8 9 10 11 12]
		[12 5 8 11 9 6 10 ] [5 12 8 11 9 6 10] [5 6 12 8 11 9 10]
		[12 11 8 6 9 5 10 ] [5 11 8 6 9 12 10]
		[12 5 8 6 11 9 10 ] [6 5 8 12 11 9 10] [6 5 8 9 11 12 10]

10.Although radix sort has the best time efficiency among other sorting algorithm it is not always applicable because it imposes some restrictions on the type of the data that can be sorted.

True

False

Answer 1

1. FALSE
   • Quicksort has the worst-case scenario when all the items in the list are already sorted.
   • In this case, we have the array partitioned to two subarrays of length 1 and N-1.
   • Hence, we will apply Quicksort on N-1 items again.
   • This will give us the worst-case complexity of O(N²)
2. OPTION B
   • In radix sort, we will take the last digit and map it to some temporary bucket.
   • Then based on the last digit, we will sort.
   • This will be repeated for N times
   • Since we are having 1000 elements as the size of the strings, we will get the complexity of O(1000 n)
3. OPTION A:
   • We will take the last digit.
   • We will apply the radix sort and get the intermediate values as:

     • pass1: 14 682 120 50 327

   • In pass2, we take the second digit from last:

     • pass2: 14 50 120 682 327

   • In pass3, we will check the rightmost digit,

     pass3: 14 50 120 327 682

   • Hence, the correct answer is OPTION A

4. OPTION B

   If we take the pivot as the median, we will get the value of 11

   • Then we will get 9

   • Then we will get 8

   • Then we will get 6

   • So, we choose these values as fixed and use this information and get the intermediate values as:
     

     [12 5 8 11 9 6 10 ]

     [5 12 8 11 9 6 10]

     [5 6 12 8 11 9 10]

5. TRUE

   • Radix sort has the best time complexity of O(N)

     But, we have the restriction of the length of the data we can sort.

     If the data is very lengthy, then it will increase the time taken for sorting