Which of the following is not a stable sorting algorithm?

a) Insertion sort

b) Selection sort

c) Bubble sort

d) Merge sort

Option : b

Which of the following is a stable sorting algorithm?

a) Merge sort

b) Typical in-place quick sort

c) Heap sort

d) Selection sort

Option : a

Which of the following is not an in-place sorting algorithm?

a) Selection sort

b) Heap sort

c) Quick sort

d) Merge sort

Option : d

Running merge sort on an array of size n which is already sorted is

a) O(n)

b) O(nlogn)

c) O(n^2)

d) None

Option : b

The time complexity of a quick sort algorithm which makes use of median,

found by an O(n) algorithm, as pivot element is

a) O(n^2)

b) O(nlogn)

c) O(nloglogn)

d) O(n)

Option : b

Which of the following is not a noncomparison sort?

a) Counting sort

b) Bucket sort

c) Radix sort

d) Shell sort

Option : d

The time complexity of heap sort in worst case is

a) O(logn)

b) O(n)

c) O(nlogn)

d) O(n^2)

Option : c

If the given input array is sorted or nearly sorted, which of the following

algorithm gives the best performance?

a) Insertion sort

b) Selection sort

c) Quick sort

d) Merge sort

Option : a

Which of the following algorithm pays the least attention to the ordering of the

elements in the input list?

a) Insertion sort

b) Selection sort

c) Quick sort

d) None

Option : b

Consider the situation in which assignment operation is very costly. Which of

the following sorting algorithm should be performed so that the number of

assignment operations is minimized in general?

a) Insertion sort

b) Selection sort

c) Heap sort

d) None

Option : b

Time complexity of bubble sort in best case is

a) θ (n)

b) θ (nlogn)

c) θ (n2)

d) θ (n(logn) 2)

Option :A

Given a number of elements in the range [0….n3

]. which of the following

sorting algorithms can sort them in O(n) time?

a) Counting sort

b) Bucket sort

c) Radix sort

d) Quick sort

Option : c

Which of the following algorithms has lowest worst case time complexity?

a) Insertion sort

b) Selection sort

c) Quick sort

d) Heap sort

Option : d

Which of the following sorting algorithms is/are stable

a) Counting sort

b) Bucket sort

c) Radix sort

d) All of the above

Option : d

Counting sort performs ……………. Numbers of comparisons between input

elements.

a) 0

b) n

c) nlogn

d) n2

Option : A

The radix sort does not work correctly if each individual digit is sorted using

a) Insertion sort

b) Counting sort

c) Selection sort

d) Bubble sort

Option : c

Which of the following sorting algorithm has the running time that is least

dependant on the initial ordering of the input?

a) Insertion sort

b) Quick sort

c) Merge sort

d) Selection sort

Option : d

Time complexity to sort elements of binary search tree is

a) O(n)

b) O(nlogn)

c) O(n^2)

d) O(n^2logn)

Option : a

The lower bound on the number of comparisons performed by

comparison-based sorting algorithm is

a) Ω (1)

b) Ω (n)

c) Ω (nlogn)

d) Ω (n^2)

Option : c

Which of the following algorithm design technique is used in the quick sort

algorithm?

a) Dynamic programming

b) Backtracking

c) Divide-and-conquer

d) Greedy method

Option : C

Merge sort uses

a) Divide-and-conquer

b) Backtracking

c) Heuristic approach

d) Greedy approach

Option : a

For merging two sorted lists of size m and n into sorted list of size m+n, we

require comparisons of

a) O(m)

b) O(n)

c) O(m+n)

d) O(logm + logn)

Option : c

A sorting technique is called stable if it

a) Takes O(nlogn) times

b) Maintains the relative order of occurrence of non-distinct elements

c) Uses divide-and-conquer paradigm

d) Takes O(n) space

Option : b

In a binary max heap containing n numbers, the smallest element can be

found in time

a) θ (n)

b) θ (logn)

c) θ (loglogn)

d) θ (1)

Option : a