Explore topic-wise InterviewSolutions in .

The CORRECT choice is (d) O(n^2)

The BEST I can explain: The best, average and worst case complexities of selection SORT is O(n^2).

(n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n^2)/2.

Correct option is (d) 4 and 1

The best I can EXPLAIN: SELECTION sort is insensitive to input, HENCE 4(n-1) ITERATIONS. Whereas bubble sort iterates only once to set the flag to 0 as the input is already sorted.

Right option is (a) 5 and 4

Best EXPLANATION: Since the INPUT array is not SORTED, bubble sort takes 5 iterations and selection sort takes 4(n-1) iterations.

The correct answer is (b) It is not scalable

The explanation is: As the input SIZE increases, the PERFORMANCE of selection sort DECREASES.

Right answer is (d) Insertion Sort

Easiest explanation - In Exchange sorts, we compare each element of an ARRAY and SWAP those elements that are not in their PROPER position. BUBBLE Sort and Quick Sort are exchange sorts. Quick Sort is ALSO called as Partition-exchange Sort. Insertion sort is not an exchange sort.

Right OPTION is (b) 4

Best explanation: On average (k + 1) / 2 comparisons are required to place the k^th ELEMENT into its correct position. THEREFORE, average number of comparisons required for 7th element = (7 + 1)/2 = 4.

Right option is (b) Statement 1 is TRUE but statement 2 is false

The best I can explain: In insertion SORT, after m passes through the array, the first m ELEMENTS are in sorted order but they are whatever the first m elements were in the UNSORTED array.

Right option is (a) 7 9 4 2 1

4 7 9 2 1

2 4 7 9 1

1 2 4 7 9

Easiest explanation - The steps performed while RUNNING insertion sort on given array are:

INITIAL : 9 7 4 2 1 key = 7

7 9 4 2 1 key = 4

4 7 9 2 1 key = 2

2 4 7 9 1 key = 1

1 2 4 7 9

In each step, the key is the element that is compared with the elements PRESENT at the left side to it.

The correct answer is (a) True

Explanation: In the incremental algorithms, the complicated structure on n ITEMS is built by first BUILDING it on n − 1 items. And then we make the necessary changes to fix things in adding the last item. Insertion sort builds the sorted sequence one ELEMENT at a time. Therefore, it is an example of an incremental ALGORITHM.

Right option is (c) INSERTION Sort

The best I can explain: The best case running time of the insertion sort is O(n). The best case occurs when the input ARRAY is ALREADY sorted. As the elements are already sorted, only one comparison is made on each PASS, so that the time required is O(n).

The CORRECT option is (a) insertion sort is stable and it sorts In-place

Easiest EXPLANATION - During insertion sort, the relative ORDER of elements is not changed. Therefore, it is a stable SORTING algorithm. And insertion sort requires only O(1) of ADDITIONAL memory space. Therefore, it sorts In-place.

The correct option is (B) ARRAY SORTED in reverse order

The explanation is: The worst case INPUT for an insertion sort ALGORITHM will be an array sorted in reverse order and its running time is quadratic.

The correct CHOICE is (a) Linear

To explain: The best case INPUT for an insertion sort ALGORITHM runs in linear TIME and is given by O(N).

The correct ANSWER is (B) Insertion sort

Easy EXPLANATION - For sorting small ARRAYS, insertion sort runs even FASTER than quick sort. But, it is impractical to sort large arrays.

Correct answer is (d) STABLE, adaptive

Best explanation: An insertion SORT is stable, adaptive, in-place and incremental in nature.

Right ANSWER is (c) for and while

For explanation: To PERFORM an insertion SORT, we use two basic loops- an OUTER for LOOP and an inner while loop.

The correct option is (a) arranging a pack of playing cards

Easiest EXPLANATION - Arranging a pack of cards mimics an insertion SORT. Database SCENARIO is an EXAMPLE for MERGE sort, arranging books is a stack and real-time systems uses quick sort.

The correct choice is (c) O(N)

Easy explanation - If the INPUT is pre-sorted, the running time is O(N), because the test in the inner for loop ALWAYS fails immediately and the ALGORITHM will RUN QUICKLY.

Right answer is (a) N(N-1)/4

Easiest explanation - The total number of PAIRS in a list L is N(N-1)/2. Thus, an average list has half this amount, or N(N-1)/4 inversions.

Correct ANSWER is (a) True

To explain: Each swap removes only ONE inversion, so O(N^2) swaps are REQUIRED.

Correct choice is (d) O(N^2)

The best I can explain: The AVERAGE CASE analysis of a tight bound ALGORITHM is MATHEMATICALLY achieved to be O(N^2).

Correct option is (a) Binary heap

The EXPLANATION is: INSERTION sort is SIMILAR to that of a binary heap ALGORITHM because of the USE of temporary variable to swap.