 # Exercise: Questions on Sorting

Questions on Sorting : Question 1 :
What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

 Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2) Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)  Correct Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn) Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)
Show Answer
Questions on Sorting : Question 2 :
Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

 O(n^2 Logn) O(n^2) O(n Logn Logn) O(nLogn)  Correct
Show Answer
Questions on Sorting : Question 3 :
Which of the following is not a stable sorting algorithm in its typical implementation.

 Insertion Sort Merge Sort Quick Sort  Correct Bubble Sort
Show Answer
Questions on Sorting : Question 4 :
Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).

 Quick Sort Heap Sort Merge Sort Insertion Sort  Correct
Show Answer
Questions on Sorting : Question 5 :
Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

 Insertion Sort with time complexity O(kn) Heap Sort with time complexity O(nLogk)  Correct Quick Sort with time complexity O(kLogk) Merge Sort with time complexity O(kLogk)
Show Answer
Questions on Sorting : Question 6 :
Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?

 Heap Sort Selection Sort  Correct Insertion Sort Merge Sort
Show Answer
Questions on Sorting : Question 7 :
Which of the following is not true about comparison based sorting algorithms?

 The minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array Any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared Counting Sort is not a comparison based sorting algortihm Heap Sort is not a comparison based sorting algorithm.  Correct
Show Answer
Questions on Sorting : Question 8 :
Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this: 2 5 1 7 9 12 11 10 Which statement is correct?

 The pivot could be either the 7 or the 9.  Correct The pivot could be the 7, but it is not the 9 The pivot is not the 7, but it could be the 9 Neither the 7 nor the 9 is the pivot.
Show Answer
Questions on Sorting : Question 9 :
Suppose we are sorting an array of eight integers using heapsort, and we have just finished some heapify (either maxheapify or minheapify) operations. The array now looks like this: 16 14 15 10 12 27 28 How many heapify operations have been performed on root of heap?

 1 2  Correct 3 or 4 5 or 6
Show Answer
Questions on Sorting : Question 10 :
What is the best time complexity of bubble sort?

 N^2 NlogN N  Correct N(logN)^2
Show Answer