MCQ Questions on Sorting

What is the best time complexity of bubble sort?

A N^2

B NlogN

C N

D N(logN)^2

Assume that we use Bubble Sort to sort n distinct elements in ascending order. When does the best case of Bubble Sort occur?

A When elements are sorted in ascending order

B When elements are sorted in descending order

C When elements are not sorted by any order

D There is no best case for Bubble Sort. It always takes O(n*n) time

The number of swappings needed to sort the numbers 8, 22, 7, 9, 31, 5, 13 in ascending order, using bubble sort is

A 11

B 12

C 13

D 10

Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

A O(n^2 Logn)

B O(n^2)

C O(n Logn Logn)

D O(nLogn)

Which of the following is not a stable sorting algorithm in its typical implementation.

A Insertion Sort

B Merge Sort

C Quick Sort

D Bubble Sort

Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).

A Quick Sort

B Heap Sort

C Merge Sort

D Insertion Sort

Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?

A Heap Sort

B Selection Sort

C Insertion Sort

D Merge Sort

Which of the following is not true about comparison based sorting algorithms?

A The minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array

B Any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared

C Counting Sort is not a comparison based sorting algortihm

D Heap Sort is not a comparison based sorting algorithm.

Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:

2  5  1  7  9  12  11  10 

Which statement is correct?

A The pivot could be either the 7 or the 9.

B The pivot could be the 7, but it is not the 9

C The pivot is not the 7, but it could be the 9

D Neither the 7 nor the 9 is the pivot

You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?

A Heap sort

B Merge sort

C Quick sort

D Insertion sort

Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.

A Insertion Sort

B Heap Sort

C Merge Sort

D Selection Sort

Which of the following sorting algorithms has the lowest worst-case complexity?

A Merge Sort

B Bubble Sort

C Quick Sort

D Selection Sort

Which sorting algorithms is most efficient to sort string consisting of ASCII characters?

A Quick sort

B Heap sort

C Merge sort

D Counting sort

Which of the following is true about merge sort?

A Merge Sort works better than quick sort if data is accessed from slow sequential memory.

B Merge Sort is stable sort by nature

C Merge sort outperforms heap sort in most of the practical situations.

D     All of the above.

Given an array where numbers are in range from 1 to n^6, which sorting algorithm can be used to sort these number in linear time?

A Not possible to sort in linear time

B Radix Sort

C Counting Sort

D Quick Sort