Explore topic-wise InterviewSolutions in .

The correct choice is (b) partitioning

For EXPLANATION: Quick SORT makes partitions of the input array about the pivot in order to IMPLEMENT SORTING. Thus its method of sorting is CALLED partitioning.

Right choice is (C) O(LOG n)

Best explanation: Auxiliary space complexity of randomized quick sort is O(log n) which is USED for storing CALL stack FORMED due to recursion. Note that the algorithms with space complexity as O(log n) also qualifies as in place algorithms as the value of log n is close to 1.

Right choice is (a) so as to AVOID worst case time complexity

To explain: RANDOMIZED quick sort helps in avoiding the worst case time complexity of O(N2) which occurs in case when the input array is ALREADY sorted. However the AVERAGE case and best case time complexities remain unaltered.

Correct choice is (b) quick sort with RANDOM choice of pivot

The BEST I can explain: RANDOMIZED quick sort chooses a random element as a pivot. It is done so as to avoid the worst case of quick sort in which the input ARRAY is already sorted.

Right CHOICE is (B) pivot position can be changed

Easiest explanation - Once a pivot is CHOSEN, its position is FINALIZED in the sorted array, it cannot be MODIFIED.

Correct answer is (d) 1

Easiest explanation - There is only one PIVOT with which the array will be SORTED, the pivot is 1.

The correct OPTION is (d) Binary tree sort

The EXPLANATION is: Quick sort is a space-optimised version of the binary tree sort. In binary sort tree, the ELEMENTS are inserted sequentially into the binary search tree and Quick sort ORGANISES elements into a tree that is implied by the recursive calls.

Right choice is (d) Quick sort

For explanation: The Quick sort is best suited to sort the ARRAY of 1 MILLION elements. The practical implementations of Quick sort use randomised version. In practice randomised Quick sort algorithms rarely shows worst CASE behaviour and is almost always O(nlogn). And Quick sort requires little additional space and exhibits good CACHE LOCALITY.

Right choice is (c) 31.11 sec

The best I can explain: The Quick sort requires NLOG2N comparisons in best case, where n is size of input ARRAY. So, 1000 * log21000 ≈ 9000 comparisons are required to sort 1000 elements, which takes 200 sec. To sort 200 elements MINIMUM of 200 * log2200 ≈ 1400 comparisons are required. This will take 200 * 1400 / 9000 ≈ 31.11 sec.

Right OPTION is (a) 22 25 56 67 89

Easy explanation - If the input sequence is already sorted then worst CASE behaviour occurs for the Quick sort algorithm which use the first ELEMENT as pivot. Therefore, the input sequence given in 22 25 56 67 89 will require a maximum number of comparisons.

Right option is (B) T(n) <= T(n/4) + T(3n/4) + cn

The explanation is: If there are n/4 ELEMENTS in one sub-array then T(n/4) comparisons are needed for this sub-array. And T(3n/4) COMPARISON are required for the rest 4n/5 elements, and cn is TIME required for finding the pivot. If there are more than n/4 elements in one sub-array then other sub-array will have less than 3n/4 elements and time complexity will be less than T(n/4) + T(3n/4) + cn.

Right choice is (B) False

For explanation: In STABLE SORTING algorithm the records with equal keys APPEAR in the same order in the sorted sequence as they appear in the input unsorted sequence. Quick SORT does not preserve the relative order of equal sort items. Therefore, Quick sort is not a stable sort.

Right choice is (a) n/2 : (n/2) – 1

The best I can EXPLAIN: The best case analysis of quick sort occurs when the PARTITION SPLITS the array into two subarrays, each of size no more than n/2 SINCE one is of size n/2 and one of size (n/2) – 1.

The correct ANSWER is (B) 6 3 4 7 9 14 11 12

To explain: Let’s apply Quick SORT on the given sequence,

For first phase, PIVOT = 7

 71114694312

ij

 71114694312

ij

 73146941112

ij

 73469141112

ij

 73469141112

ji

 63479141112

The correct answer is (d) O(N^2)

Easy explanation - The worst case running TIME for QUICK sort is O(n^2). In Quick sort, the worst case behaviour occurs when the partitioning routine produces two sub-arrays one with n – 1 ELEMENT and other with 0 elements.

The correct choice is (b) DIVIDE and conquer ALGORITHM

Explanation: Quick sort is a divide and conquer algorithm. Quick sort first PARTITIONS a large array into two smaller sub-arrays. And then RECURSIVELY sorts the sub-arrays.

The CORRECT choice is (B) N=5-20

To explain: A good cut-off range is ANYWHERE between N=5 and N=20 to avoid NASTY DEGENERATE cases.

Right ANSWER is (a) FIRST ELEMENT as PIVOT

The best I can explain: CHOOSING the first element as pivot is the worst method because if the input is pre-sorted or in reverse order, then the pivot provides a poor partition.

The correct choice is (b) two

The BEST I can explain: The entire ARRAY is divided into two partitions, 1st sub array CONTAINING ELEMENTS less than the pivot element and 2ND sub array containing elements greater than the pivot element.

Right answer is (a) true

The explanation is: Quick sort USES join OPERATION SINCE join is a faster operation than MERGE.

The correct ANSWER is (c) INSERTION SORT

The best explanation: Insertion sort is used along with quick sort to sort the sub arrays.

It is used only at the END.

Correct answer is (c) O(N log N)

For explanation: The BEST case and AVERAGE case analysis of a QUICK sort algorithm are mathematically found to be O(N log N).

Right choice is (a) choosing a random ELEMENT as pivot

For explanation: This is the SAFEST method to choose the pivot element since it is very unlikely that a random pivot would CONSISTENTLY provide a poor PARTITION.

Correct option is (c) median-of-three partitioning

Explanation: Median-of-three partitioning is the BEST method for CHOOSING an appropriate pivot ELEMENT. Picking a first, last or random element as a pivot is not MUCH EFFECTIVE.

The correct option is (c) O(N^2)

The BEST explanation: The worst CASE performance of a quick sort algorithm is MATHEMATICALLY FOUND to be O(N^2).

Correct OPTION is (a) True

Best EXPLANATION: In quick sort, the ARRAY is DIVIDED into sub-arrays and then it is sorted (divide-and-conquer strategy).

Right choice is (b) Quick sort

Easiest explanation - Quick sort is the FASTEST KNOWN sorting ALGORITHM because of its HIGHLY optimized INNER loop.

The correct answer is (a) O(n log n)

Explanation: The merge function in the bottom up merge sort takes O(n) TIME which is placed inside the for LOOP. The loop RUNS for O(log n) time, thus the overall time COMPLEXITY of the CODE becomes O(n log n).

Right answer is (b) O(n)

The best EXPLANATION: The auxiliary space complexity of bottom up merge sort is same as standard merge sort as both USES the same algorithm for merging the sorted arrays which takes o(n) space. But bottom up merge sort does not NEED to maintain a CALL stack.

Right option is (C) O(n)

Easiest explanation - The merging of two sorted arrays requires an additional SPACE of n due to which the auxiliary space REQUIREMENT of merge SORT is O(n). Thus merge sort is not an in PLACE sorting algorithm.

Right ANSWER is (a) O(N log n)

The best I can explain: The recurrence relation for MERGE sort is given by T(n) = 2T(n/2) + n. This can be solved USING master’s THEOREM and is found equal to O(n log n).

Correct option is (c) divide and conquer

Easy explanation - Merge sort uses the technique of divide and conquer in ORDER to sort a GIVEN array. It divides the array into two HALVES and applies merge sort algorithm to each half individually after which the SORTED versions of these halves are MERGED together.

The correct answer is (c) O(LOG N)

Easiest explanation - Space complexity of in place version of merge sort is O(log n) which is used for storing CALL stack formed due to recursion. NOTE that the algorithms with space complexity as O(log n) also qualifies as in place algorithms as the value of log n is close to 1.

Correct ANSWER is (c) O(n)

Easiest EXPLANATION - The merging of two sorted arrays REQUIRES an additional space of n due to which the auxiliary space requirement of merge sort is O(n). Thus merge sort is not an in place sorting algorithm.

Right CHOICE is (a) O(n LOG n)

The best EXPLANATION: The recurrence relation for merge sort is given by T(n) = 2T(n/2) + n. This can be solved using master’s theorem and is found EQUAL to O(n log n).

Right choice is (c) divide and conquer

Easy EXPLANATION - Merge sort uses the technique of divide and conquer in order to sort a GIVEN array. It divides the array into TWO halves and APPLY merge sort ALGORITHM to each half individually after which the sorted versions of these halves are merged together.

Correct choice is (a) merge sort

The best I can EXPLAIN: Quick sort, HEAP sort, and INSERTION sort are in-place sorting ALGORITHMS, whereas an additional space of O(n) is required in order to merge two SORTED arrays. Even though we have a variation of merge sort (to do in-place sorting), it is not the default option. So, among the given choices, merge sort is the most appropriate answer.

Correct choice is (d) linear merge sort

The best I can explain: In-place, top down and bottom up merge sort are different variants of merge sort. Whereas linear merge sort is not a POSSIBLE variant as it is a comparison based sort and the MINIMUM time complexity of any comparison based sort is O(N LOG n).

Correct ANSWER is (a) O(N log n)

For explanation: The time complexity of MERGE sort is not affected in any case as its algorithm has to implement the same number of steps. So its time complexity remains to be O(n log n) even in the best case.

Right option is (a) merging

For explanation: Merge SORT algorithm divides the array into two halves and applies merge sort algorithm to each half individually after which the two SORTED halves are MERGED TOGETHER. Thus its METHOD of sorting is called merging.

Correct answer is (a) O(N LOG n)

Best explanation: The time complexity of merge SORT is not affected by worst case as its algorithm has to implement the same NUMBER of steps in any case. So its time complexity remains to be O(n log n).

Correct choice is (a) true

The explanation is: Standard MERGE sort requires O(N) SPACE to merge TWO sorted arrays. We can optimize this merging process so that it takes only CONSTANT space. This version is known as in place merge sort.

The correct answer is (c) O(n)

The best I can explain: An additional SPACE of O(n) is required in order to MERGE TWO sorted arrays. THUS merge sort is not an in place SORTING algorithm.

Correct choice is (a) O(N log n)

The best I can explain: The RECURRENCE RELATION for MERGE sort is given by T(n) = 2T(n/2) + n. It is found to be equal to O(n log n) using the master theorem.