# Sorting Algorithms Mock Test – 1

 Question 1
The best case of quick sort helps Student-1 to sort a particular data set of size 'n' in 640 ms. Student-2 also tried the same algorithm on similar data set and it took him 256 ms in best case to sort a file of size 16. What could be Student-1's file size?
 A 40 B 6 C 32 D 64
Algorithm
Question 1 Explanation:
Best case of quick sort is $c \times n \log n$ for input size n.

For, for student-1
$c \times n \log n = 640$

For, for student-2, n=16
$c \times 16 \log 16 = 256$
$c=4$
Use this value of c=4 in student-1's equation

$4 \times n \log n = 640$
$n = 32$ Click to Join Our Telegram Group for Latest Update of MOCK TEST Question 2
Consider a modification of the insertion sort algorithm, which performs a binary search instead of sequential to find the position where the element to be inserted in each pass of the algorithm. What is the worse case running time of this algorithm?
 A $O(n^2)$ B $O(n \ log n)$. C $O(n)$. D None of these
Algorithm
Question 2 Explanation:
Time Complexity of insertion sort consist of two part.
(1) Cost of comparison
(2) Cost of shifting

Using binary search instead of linear search for finding the correct position of element in insertion sort decrease the searching time or Cost of comparison from $O(n^2)$ to $O(n \log n)$, but Cost of shifting still remain $O(n^2)$.

Hence, Total, time complexity still remains $O(n^2)$. Click to Join Our Telegram Group for Latest Update of MOCK TEST Question 3
Consider a modification of the insertion sort algorithm, which use link list as data structure to store elements instead of array to reduce the number of shifting of elements while sorting. What is the worse case running time of this algorithm?
 A $O(n^2)$ B $O(n \ log n)$. C $O(n)$. D None of these
Algorithm
Question 3 Explanation:
Time Complexity of insertion sort consist of two part.
(1) Cost of comparison
(2) Cost of shifting

Using link list, Cost of shifting can be reduced to $O(n)$ from $O(n^2)$, but Cost of comparison remains $O(n^2)$ as binary search can not be applied in link list. Hence, time complexity remain $O(n^2)$. Click to Join Our Telegram Group for Latest Update of MOCK TEST Question 4
Suppose the given array of size n is sorted other than first 10 element and last 50 elements. Find the sorting algorithm which can run faster than other algorithms.
 A Merge Sort B Insertion sort C Quick Sort D Bubble sort
Algorithm
Question 4 Explanation:
Insertion Sort works faster, because only few elements need to ben inserted in proper places. Merge sort runs longer time compared to quicksort and quicksort runs longer than insertion sort. In this case, bubble sort is slower than insertion sort. So, Insertion sort is faster. Click to Join Our Telegram Group for Latest Update of MOCK TEST Question 5
Which of the following cases is definite to give $O(n log n)$ time complexity always for quick sort to sort the array $A[0...n]$, for any set of values of array A.

Case 1: Choosing middle element as pivot.
Case 2: Choosing pivot element as $(2^0)$th element initially followed by $(2^1)$th element, followed by $(2^2)$th element of array A and so on. Case 3: Choosing median element as pivot.
Case 4: Choosing the pivot element randomly from the array A.
Case 5: Choosing pivot such that the array is portioned into almost two equal sub arrays
 A Only 1 and 4 B Only 1, 2 and 3 C Only 3 and 5 D Only 1, 3 and 4
Algorithm
Question 5 Explanation:
Case 1 : In worse case, middle element is smallest or highest element which converts quick sort into worse case.

Case 2 : In worse case, the selected element is smallest or highest element which converts quick sort into worse case.

Case 3 : if median is selected as pivot then both partition size remain same which converts quick sort into best case.

Case 4 : In worse case, randomly selected element is smallest or highest element which converts quick sort into worse case.

Case 5 : If pivot is selected such that the array is partitioned into almost two equal sub arrays then it converts quick sort into best case.

So, Case 3 and 5 is correct. Click to Join Our Telegram Group for Latest Update of MOCK TEST 1. 