Explore topic-wise InterviewSolutions in .

Correct choice is (c) O(logn/log(logn))

The EXPLANATION is: The time complexity of Heap sort is O(klogk) for K input ELEMENTS,

for k = logn/log(logn),

O(klogk) = O(logn/log(logn) * log(logn/log(logn)))

∴ O(klogk) = O(logn/log(logn) * (log(logn) – log(log(logn))))

= O(logn)

HENCE the correct option is O(logn/log(logn)).

The correct OPTION is (a) QUICK sort and HEAP sort

Easy explanation - Introsort is a hybrid sorting algorithm that combines Quick sort and Heap sort to retain advantages of both. It has WORST case speed of Heap sort and average case speed of Quick sort.

Correct ANSWER is (b) Smooth sort

Easy EXPLANATION - Smooth sort is a variation of Heap sort. Smooth sort has O(nlogn) WORST case TIME complexity like Heap sort. But Smooth sort takes O(n) time to sort the nearly sorted input array.

The correct choice is (a) O(nlogn)

Easy EXPLANATION - In Heap sort, the call to procedure build_Max-heap takes O(N) TIME and each of O(n) calls to the function max_Heapify takes O(logn) time. So the WORST case complexity of Heap sort is O(nlogn).

The correct option is (c) A[Parent(i)] >= A[i]

For EXPLANATION: The max-heap is also KNOWN as descending heap. Max-heap of SIZE n is an almost complete BINARY tree of n nodes such that the element at each node is LESS than or equal to the element at its parent node.

Right choice is (d) 9

Explanation: In max-heap element at each node is smaller than or EQUAL to the element at its PARENT node. On applying the heapify PROCEDURE on item at position 2, it will be in position 9 as shown below.

Right option is (c) Heap sort is stable sort

Best EXPLANATION: Heap sort is a COMPARISON based sorting algorithm and has time complexity O(nlogn) in the average case. Heap sort is an in-place algorithm as it needs O(1) of AUXILIARY space. Heap sort uses heap and operations on heap can change the relative order of items with the same key VALUES. Therefore, Heap sort is not a stable sort.

Right CHOICE is (b) selection sort

Explanation: HEAP sort is an implementation of selection sort using the input array as a heap representing a descending priority queue. Heap sort algorithm is divided into two PHASE. In first phase the max-heap is created and the SECOND phase (selection phase) DELETES the elements from the priority queue using siftdown operation.

Right choice is (a) O(N)

BEST explanation: The TIME taken to copy ELEMENTS to and from the MAIN array and extra array is found to be O(N).

Correct answer is (d) 2N LOG N + O(N)

The best I can explain: The AVERAGE number of COMPARISONS in a heapsort algorithm is mathematically found to be 2N log N + O(N).

Correct choice is (a) true

Explanation: HEAP sort uses fewer comparisons than other sorting algorithms and HENCE it is an EXTREMELY stable algorithm.

Correct option is (C) O(log N)

The best I can explain: The time TAKEN to perform a DELETION of a minimum ELEMENT is mathematically FOUND to be O( log N).

The CORRECT CHOICE is (b) 2

Best explanation: To perform deletion operation in a HEAP, we require 2 arrays and that OCCUPIES extra memory space and hence increase in running time.

The CORRECT answer is (b) O(N log N)

The best explanation: The total running time of a heap sort ALGORITHM is MATHEMATICALLY FOUND to be O(N log N).

The correct option is (b) decreasing SORTING order

Explanation: By logic, after DELETING minimum element, the HEAP will contain elements in decreasing sorting order. We can CHANGE this by altering the ORDERING property.

Right option is (a) 0

Easy explanation - The array for heap sort contains data at position 0 whereas for a BINARY heap, array BEGINS at 1. This is the reason for its COMPLEXITY.

The CORRECT option is (d) 97,53,59,26,41,58,31

Easy EXPLANATION - Constructing a MAX heap USING the elements 97,53,59,26,41,58,31 will cause the heap to look like that.

Correct option is (B) false

Best EXPLANATION: HEAP sort is slower than Shell sort because Shell sort uses Sedgewick’s increment sequence.

The CORRECT answer is (a) O(N)

The best I can explain: The BASIC STRATEGY is to build a binary heap of N ELEMENTS which takes O(N) TIME.

The correct OPTION is (C) Priority QUEUE

The best explanation: Heap sort is based on the algorithm of priority queue and it gives the best sorting TIME.

The CORRECT CHOICE is (a) Shell sort’s passes completely sort the ELEMENTS before going on to the next-smallest gap while Comb sort’s passes do not completely sort the elements

Explanation: Both Shell sort and Comb sort have repeated sorting passes with DECREASING gaps. Unlike Comb sort, in Shell sort the array is sorted completely in each pass before going on to the next-smallest gap.

The correct answer is (b) False

The best I can explain: Insertion sort is more EFFICIENT than SHELL sort if the length of array is SMALL because insertion sort is QUITE SIMPLE to program and involve very few actions other than comparisons and replacements on each pass.

Correct option is (d) Ki <= Ki+hfor 1<= i <= N-h

Best EXPLANATION: Records are h-orderedif every hth ELEMENT (STARTING anywhere) yields a sorted array. Therefore, given records with keys K1, K2, K3,.. KNare said to be h-ordered, if Ki <= Ki+hfor 1<= i <= N-h.

The correct CHOICE is (a) O(nlogn)

Explanation: The best case occurs when the array is already sorted. In best case the number of comparison for each of the increments-based insertion sorts is equal to length of array.

Here 2k –1 < n, where n is the number of records. So K < log(n+1), thus the sorting time in best case is LESS the n * log(n+1). Therefore best case time COMPLEXITY is O(nlogn).

The correct OPTION is (d) both 7-ordered and 5-ordered

The BEST explanation: An array that is 7-sorted, BECOMES 7-ordered. And an array that is 5-sorted, becomes 5-ordered. If k-ordered array is h-sorted, it REMAINS k-ordered. THUS, an array that is first 7-sorted, then 5-sorted becomes both 7-ordered and 5-ordered.

Right choice is (a) insertion sort

The best explanation: Shell sort is an improvement on insertion sort that allows the EXCHANGE of ELEMENTS that are far apart. Shell sort algorithm SORTS separate sub-arrays of the original input array. These sub-arrays contains EVERY hth element of the original array.

Right ANSWER is (c) 27 59 39 37 15 90 81 49

Easiest EXPLANATION - GIVEN elements 27 59 49 37 15 90 81 39,

First Iteration (span = 5):

So, the SEQUENCE after first iteration will be, 27 59 39 37 15 90 81 49.

The correct option is (b) Statement 2 is true but statement 1 is false

The BEST explanation: In Shell sort, the relative order of elements with EQUAL values MAY change. THEREFORE, it is not a stable sorting algorithm. Shell sort is an in-place sorting algorithm as it requires O(1) auxiliary SPACE.

Right option is (b) O(N^2)

The EXPLANATION is: The WORST case ANALYSIS is mathematically found to be O(N^2). The proof is RATHER complicated.

Correct choice is (b) 1,3,7,….,2k-1

Easy explanation - SHELL’s increments are of the form 1,3,7,….,2k-1. The KEY difference is that the consecutive elements have no COMMON FACTORS.

Correct answer is (d) O(N^3/2)

Explanation: Mathematically, the LOWER bound ANALYSIS for SHELL sort using Hibbard’s increments is O(N^3/2).

Right option is (a) SHELL sort ALLOWS an exchange of far items WHEREAS INSERTION sort moves elements by one position

For explanation: Shell sort is an extension of insertion sort because it swaps elements at far distances and at a FASTER rate.

The CORRECT CHOICE is (c) Insertion sort

To explain: Shell sort performs an insertion sort on hk independent ARRAYS. It is mainly a variation of insertion sort.

The correct CHOICE is (a) True

The best I can explain: Shell sort uses an INCREMENT SEQUENCE h1, h2, h3… and this sequence will WORK as long as h1=1.

Right OPTION is (b) Internal sorting

For EXPLANATION: Shell SORT is an example of internal sorting because sorting of elements is done internally using an ARRAY.

The correct OPTION is (a) True

The best explanation: Shell sort broke the quadratic time barrier as it WORKS by COMPARING elements that are DISTANT.

The correct option is (b) Donald Shell

The best explanation: Shell sort algorithm is invented by Donald shell. MERGE sort is invented by John Von NEUMANN. Quick sort is invented by TONY Hoare.

The correct choice is (a) Diminishing increment sort

Easy EXPLANATION - The other name for a shell sort algorithm is diminishing DECREMENT sort as the DISTANCE between COMPARISONS decreases as the algorithm runs until the LAST phase.

Correct choice is (a) O(n LOG n)

To EXPLAIN: The average case time COMPLEXITY of median of three quick SORT is the same as that of a standard quick sort as randomized quick sort only helps in PREVENTING the worst case. It is equal to O(n log n).

The CORRECT option is (c) O(log n)

The explanation is: Auxiliary space complexity of median of three 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.

The correct answer is (d) choosing median of FIRST, last and middle element as pivot

Easy explanation - In the median of three TECHNIQUE the median of first, last and middle element is chosen as the pivot. It is done so as to avoid the worst CASE of quick sort in which the TIME complexity shoots to O(n^2).

The CORRECT option is (C) divide and CONQUER

Best explanation: Quick SORT uses the technique of divide and conquer in order to sort a given array. It divides the array into two parts about the pivot and then applies quick sort to both the parts.

The correct choice is (a) true

Explanation: In-place algorithms REQUIRES CONSTANT or very less auxiliary space. Quick sort qualifies as an in place sorting algorithm as it has a very low auxiliary space requirement of O(LOG N).