Explore topic-wise InterviewSolutions in .

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

The best I can explain: Worst CASE complexity is observed when the INPUT array is reverse sorted. This is same as the worst case complexity of bubble SORT.

The CORRECT option is (a) is equal to NUMBER of elements in the array

The best I can explain: INITIAL gap is TAKEN to be equal to the number of elements in the array and shrinks by a factor of 1.3 in each iteration, initial gap is independent of the number of ITERATIONS and compiler being used.

The correct CHOICE is (c) 1.3

Easy explanation - It has been found EXPERIMENTALLY that the gap between the TWO ELEMENTS should shrink by a factor of 1.3 after each iteration for the most efficient sorting.

The CORRECT option is (b) Bubble sort

The BEST I can explain: Comb sort compares TWO elements at a VARIABLE gap from each other in each iteration unlike bubble sort where the gap REMAINS 1. This reduces the average time complexity of comb sort.

Correct CHOICE is (b) False

The BEST EXPLANATION: Both BUBBLE sort and cocktail sort has the same time complexities. But cocktail sort has a comparatively better performance.

The CORRECT choice is (a) 4,2

The best explanation: Cocktail sort applies bubble sort in two phases until the array GETS SORTED. So here bubble sort will take 4 iterations to sort the given array WHEREAS cocktail sort takes only 2 iterations. This shows cocktail sort has a comparatively better PERFORMANCE.

The correct OPTION is (a) O(N)

The explanation is: Best case complexity is OBSERVED when the input array is ALREADY sorted. This is the same as the best case complexity of bubble SORT.

Right CHOICE is (c) O(n^2)

EXPLANATION: Worst case COMPLEXITY is observed when the input array is reverse SORTED. This is the same as the worst case complexity of bubble sort.

The correct OPTION is (a) True

For explanation: Cocktail SORT compares the value of DIFFERENT elements in the array for SORTING. Thus, it is a comparison based sort.

The correct option is (a) cocktail sort

The EXPLANATION is: Cocktail sort is an in PLACE SORTING technique as it only requires constant AUXILIARY space for manipulating the INPUT array. Rest all other options are not in place.

Right CHOICE is (c) O(1)

Best explanation: In COCKTAIL sort manipulation is done on the input array itself. So no extra space is REQUIRED to perform sorting. Thus it requires CONSTANT auxiliary space.

Right ANSWER is (a) Bubble sort

To EXPLAIN: Cocktail sort is very similar to bubble sort. It WORKS by traversing an array in both directions alternatively. It compares the adjacent ELEMENTS in each iteration and SWAPS the ones which are out of order.

Correct choice is (d) ripple sort

For explanation: Cocktail sort is ALSO known by the name of ripple sort. It is also known by other NAMES LIKE – bidirectional bubble sort, cocktail shaker sort, shuttle sort, SHUFFLE sort etc.

Correct ANSWER is (b) STRAND sort

For explanation: Strand sort is an adaptive sorting algorithm. This is because it gives a better performance when the input LIST is almost SORTED.

The CORRECT ANSWER is (b) SELECTION

Easiest EXPLANATION - Strand sort uses the method of selection for sorting any given list. This is because it SELECTS the strands of elements from the input list which are sorted.

Correct ANSWER is (a) O(n)

Best explanation: Best case TIME complexity of STRAND sort is O(n). It occurs in the case where the INPUT array is ALREADY sorted.

Correct CHOICE is (c) O(n^2)

The explanation is: Average case time complexity of strand SORT is O(N2). So it is not as EFFICIENT as quick sort or merge sort.

Correct OPTION is (a) true

The explanation is: STRAND sort is an example of a stable SORTING algorithm. It is because the elements with IDENTICAL values APPEAR in the same order in the output array as they were in the input array.

Right OPTION is (a) true

To EXPLAIN: Pigeonhole sort is an example of a comparison based SORTING algorithm. This is because it COMPARES the value of elements present in a list in ORDER to sort them.

Right OPTION is (B) STRAND sort

To EXPLAIN: Strand sort has an auxiliary space complexity of O(n). So it is not an in place sorting algorithm.

The CORRECT option is (a) O(n)

EXPLANATION: The AUXILIARY space complexity of STRAND sort is O(n). It is because a sub-list of size n has to be maintained.

The correct answer is (b) strand SORT

Best explanation: Strand sort REQUIRES the use of RECURSION for implementing its algorithm. On the other hand, the sorting ALGORITHMS given in the remaining options use ITERATIVE methods.

Right choice is (d) it is an in PLACE sorting algorithm

Easy EXPLANATION - Library sort is not an in place sorting algorithm as it requires O(n) auxiliary SPACE. The array needs to be re balanced after every insertion so as to ensure that GAPS are present between every successive element.

The correct option is (a) LIBRARY SORT

For EXPLANATION: Out of the given options library sort is the only algorithm which is not in place. It is because the auxiliary SPACE required by library sort is O(N).

Right OPTION is (a) library sort

Easiest explanation - Library sort is an adaptive algorithm. It is because the TIME complexity of the algorithm improves when the INPUT array is ALMOST sorted.

Correct choice is (a) Library sort has a BETTER average time complexity

Best explanation: Library sort has a better average time complexity as COMPARED to insertion sort because it USES binary search for finding the index where the ELEMENT has to be inserted in the sorted ARRAY. This makes the process faster.

The correct ANSWER is (a) gapped insertion sort

The best explanation: Library sort is also KNOWN as gapped insertion sort because it uses insertion sort with GAPS in between SUCCESSIVE ELEMENTS. These gaps allow for fast insertion.

The correct OPTION is (c) O(n^2)

Easiest EXPLANATION - The worst case TIME complexity of library sort is the same as that of INSERTION sort. The worst case time complexity is O(n^2).

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

Easiest EXPLANATION - Library sort USES BINARY search in order to insert elements in the sorted segment of the array which reduces its TIME complexity. So the average time complexity of library sort is O(n log n).

Correct choice is (b) library sort

The best I can explain: Library sort makes use of a binary SEARCH algorithm. It is used to FIND the correct INDEX in the array where the element should be inserted. Then after the INSERTION of the element re-balancing of the array TAKES place.

Correct OPTION is (C) Library sort

For explanation: Out of the given options library sort is the only algorithm which is stable. It is because the elements with IDENTICAL values appear in the same ORDER in the output array as they were in the input array.

Correct choice is (a) true

Easy explanation - Library sort does not require the entire input DATA at the BEGINNING itself in order to sort the array. It rather creates a partial solution in every step, so FUTURE elements are not required to be considered. Hence it is an online sorting algorithm like INSERTION sort.

Correct OPTION is (b) library sort has greater SPACE complexity

The explanation is: Library sort has a DISADVANTAGE that it takes up O(n) AUXILIARY space whereas insertion sort takes constant auxiliary space.

The correct choice is (a) 4

The best I can explain: CYCLE sort requires a minimum number of write OPERATIONS in order to sort a GIVEN array. So in this CASE, only 4 write operations will be required.

Right answer is (a) cycle sort

The BEST I can EXPLAIN: Cycle sort is the only ALGORITHM from the given ONES that uses the METHOD of insertion. Other than this, insertion sort also uses the method of insertion for sorting.

Correct option is (a) true

Easiest EXPLANATION - Cycle sort is a comparison BASED SORTING algorithm. This is because it COMPARES elements in order to sort them.

Right choice is (c) it REQUIRES minimal write operations

The EXPLANATION is: Cycle sort is a slow sorting algorithm as compared to quick sort, merge sort etc. and is ALSO not adaptive. But it offers an advantage that it PERFORMS minimal write operations which can be very useful in a situation where the write operation is expensive.