Explore topic-wise InterviewSolutions in .

The correct option is (a) O(n^2)

The EXPLANATION is: The average case performance of CYCLE SORT is O(n^2). It is because it has to MAKE n comparisons for each element of the ARRAY.

Right answer is (a) O(n^2)

Easy explanation - Best case time complexity of cycle SORT is O(n^2). This shows that cycle sort is not an adaptive sorting algorithm and thus makes it undesirable when the given array is ALREADY almost SORTED.

Correct ANSWER is (d) O(n^2)

For explanation: The WORST case performance of CYCLE sort is O(n^2). It is because it has to make n comparisons for each ELEMENT of the array.

The correct answer is (a) Heap SORT

Easiest explanation - Heap sort is basically IMPROVEMENT to the BINARY tree sort. Heap sort builds a heap on the input element by adjusting the position of the ELEMENTS within the original array, rather than creating nodes as in binary tree sort.

Right answer is (d) Both quick sort and BINARY tree are in place SORTING algorithms

To explain: Binary tree sort and quick sort have same running TIME i.e O(nlogn)

in average CASE and O(n^2) in worst case. Binary tree is not in-place sorting ALGORITHM.

The correct option is (b) False

Easy EXPLANATION - In binary tree sort it is required to reserve one tree node for each array ELEMENT. Its implementation requires two pointer VARIABLES for each node. So, it requires extra memory. The worst case space complexity of binary tree sort is Θ(n). THEREFORE, binary tree sort is not an in-place sorting algorithm.

The CORRECT OPTION is (a) inorder

To explain: In binary tree SORT is a sort ALGORITHM where a binary search tree is built from the elements to be sorted, and then we perform inorder traversal on the BST to GET the elements in sorted order.

The correct answer is (d) 10

Explanation: Original ARRAY is 17 8 12 4 26. The BST built on this array is shown in the figure below.

To built the BST, we travel down the TREE until a leaf is reached. THEREFORE, for every element we compare the element with the internal nodes until we the leaves and then once again compare the element with its parent to decide WHETHER it is right child or left child. So, for given array we need to perform 10 comparisons to build the BST.

The correct ANSWER is (a) true

The EXPLANATION is: CUBE sort is a comparison based sorting algorithm. This is because it compares elements in ORDER to sort them.

The correct answer is (a) HIGH memory overhead for small DATA

To explain: In a GENERAL CASE the memory overhead of cube sort is low. But when the data set is small then in that case the memory overhead becomes high.

The correct answer is (b) false

The explanation is: Cube SORT has an AUXILIARY SPACE complexity of O(n). So it does not qualify to be an in-place sort.

The CORRECT ANSWER is (d) bogosort

The EXPLANATION is: Out of the GIVEN algorithms only cube sort is stable. This implies that the relative POSITION of equal valued elements in the input and sorted array remains the same.

Right option is (b) O(N log n)

The BEST EXPLANATION: The average case performance of cube sort is O(n log n). This is the fastest POSSIBLE complexity with a comparison based sort.

Right option is (b) O(n)

The best I can EXPLAIN: Best case time complexity of CUBE SORT OCCURS when the input ARRAY is almost sorted. So in such a case only O(n) time is required for sorting.

The correct option is (c) O(n LOG n)

The best EXPLANATION: The WORST case performance of cube sort is O(n log n). This is the FASTEST possible complexity with a comparison based sort.

Correct answer is (c) cube sort

Easy explanation - Out of the GIVEN OPTIONS only cube sort is a parallel sorting algorithm. It builds self balancing MULTI DIMENSIONAL arrays from the INPUT keys.

Right OPTION is (c) 32-64 DEPENDING on size of the array

Best explanation: Usually the size of the run is chosen somewhere between 32 and 64. The size of run is preferably chosen in powers of 2 in order to MAINTAIN balance while merging the sorted runs.

Correct answer is (c) when no. of elements are less than size of run

Easiest explanation - Tim sort uses a hybrid of INSERTION and MERGE sort. It reduces to insertion sort when the size of array is less than the size of run as insertion sort is EFFICIENT in sorting SMALL arrays.

Correct option is (a) Because insertion sort is faster and adaptive

The BEST explanation: When SMALL arrays need to be sorted then insertion sort proves to be the best choice. Also, it is adaptive so it PERFORMS BETTER than others when the given array is fully/partially sorted.

The CORRECT answer is (c) TIM sort

Explanation: JAVA makes use of Tim sort internally for implementing arrays.sort(). It is mainly DUE to the fastness of this algorithm in COMPARISON to other comparison based sorts.

The correct choice is (a) O(N)

Best EXPLANATION: TIM SORT is a hybrid of merge sort and insertion sort. It requires to merge SORTED runs which require a third array of the size equal to the sum of the two runs. So in worst case the auxiliary space requirement will be O(n).

Right choice is (b) O(N log n)

Easy explanation - WORST case TIME complexity of Tim SORT is O(n log n). It is because the worst complexity of merge sort is O(n log n) and INSERTION sort is only applied for small arrays.

Right OPTION is (a) O(N)

For EXPLANATION: Best case time complexity of Tim sort occurs when the input array is already sorted. In such a case only ONE run will be required.

Right answer is (a) true

Easy EXPLANATION - Merge SORT and insertion sort are comparison based sorts. Thus OVERALL Tim sort ALSO becomes a comparison based sort.

Right CHOICE is (B) tim sort

Explanation: Tim sort is not an in-place sorting algorithm as it REQUIRES auxiliary space. It is because it requires to merge sorted runs which requires a THIRD array of the SIZE equal to the sum of the two runs.

The correct answer is (a) Tim sort

Easiest explanation - Out of the GIVEN OPTIONS Tim sort is the only ALGORITHM which is stable. As both CONSTITUENTS of Tim sort (I.e insertion sort and merge sort) are stable so Tim sort ALSO becomes stable.

The correct OPTION is (C) insertion sort

To EXPLAIN: Tim sort begins sorting any given ARRAY by using insertion sort for each run. The array is divided into smaller parts for this purpose, each part having a size EQUAL to value of run. Then these small parts called runs are merged in order to obtain sorted array.

The correct CHOICE is (c) merge sort

The explanation is: TIM sort is a HYBRID sorting ALGORITHM which means it uses more than one sorting algorithm as a routine. It is DERIVED from insertion sort and merge sort.

The correct choice is (d) tim sort

The best EXPLANATION: Tim sort has been python’s standard sorting algorithm since its version 2.3. It is an EXAMPLE of hybrid sorting algorithm which means it USES more than ONE sorting algorithm as a routine.

The correct answer is (a) quick sort

Easiest explanation - Quicksort proves to be the best sorting ALGORITHM for mid SIZED arrays as it has low space and time COMPLEXITY. Thus quick sort is preferred when size of PARTITION is between 16 and 2 log(N).

Correct answer is (d) 2 log (n)

Easy EXPLANATION - Quicksort has a worst CASE time complexity of O(n^2) which is not preferable. So in ORDER to avoid worst case of quicksort, INTROSORT switches to heap SORT when the depth is greater than 2 log(n). This particular value has been deduced experimentally.

Right answer is (a) Because insertion SORT is faster and adaptive

BEST explanation: When SMALL arrays NEED to be sorted then insertion sort proves to be the best choice. Also it is adaptive so it PERFORMS better than others when the given array is fully/partially sorted.

Correct CHOICE is (d) O(log N)

For explanation: Introsort is a hybrid of quick SORT, heap sort and INSERTION sort. So like quick sort it may use O(log n) auxiliary space in the stack to store call STATEMENTS.

Right ANSWER is (b) O(n log n)

Easiest EXPLANATION - Average time complexity of introsort REMAINS to be O(n log n) as for most of the cases QUICK sort and heap sort are used which have O(n log n) time complexity for an average case.

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

The explanation is: Worst CASE TIME complexity of quicksort is AVOIDED when we implement introsort. Introsort switches to heap sort when there is a possibility of crossing the MAXIMUM depth limit.

The CORRECT choice is (B) O(n LOG n)

Easy explanation - Introsort is mainly governed by HEAP sort and QUICK sort. As the best case of both heap sort and quick sort is O(n log n) so the best case of introsort also becomes O(n log n).

Right answer is (a) true

To explain: QUICKSORT, HEAP sort and insertion sort are COMPARISON based sorts. Thus OVERALL introsort also becomes a comparison based sort.

Right option is (a) Introsort

Explanation: Out of the GIVEN options introsort is the only algorithm which is not stable. As it MAY USE QUICK sort in some CASE to perform sorting which is itself not stable. Thus stability of introsort is not guaranteed.

Correct choice is (B) QUICK sort

For explanation: Introsort begins sorting any given ARRAY by using quick sort. Then it may switch to heap sort or insertion sort or may stick to quick sort depending upon the size of the partition.

Right option is (B) INTROSORT

Easy EXPLANATION - Introsort is the in built sorting algorithm used by C++. It is an EXAMPLE of a hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine.