GATE CSE 2021 Set 1 | Searching and Sorting Question 2 | Algorithms

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0.33

Consider the following array.

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort above array in ascending order?

Insertion sort

Selection sort

Quicksort using the last element as pivot

Merge sort

GATE CSE 2019

Numerical

-0

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ______.

Your input ____

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

-0.3

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

$$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ Quicksort runs in $$\Theta \left( {{n^2}} \right)$$ time
$$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ Bubblesort runs in $$\Theta \left( {{n^2}} \right)$$ time
$$\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ Mergesort runs in $$\Theta \left( n \right)$$ time
$$\,\,\,{\rm I}V.\,\,\,\,\,\,\,$$ Insertion sort runs in $$\Theta \left( n \right)$$ time

$${\rm I}$$ and $${\rm II}$$ only

$${\rm I}$$ and $${\rm III}$$ only

$${\rm II}$$ and $${\rm IV}$$ only

$${\rm I}$$ and $${\rm IV}$$ only

GATE CSE 2016 Set 1

MCQ (Single Correct Answer)

-0.3

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

$$\Theta \left( {n\,\log n} \right),\Theta \left( {n\,\log n} \right),\,\,$$ and $$\,\,\Theta \left( {{n^2}} \right)$$

$$\Theta \left( {{n^2}} \right),\Theta \left( {{n^2}} \right),\,\,$$ and $$\,\,\Theta \left( {n\,\log n} \right)$$

$$\Theta \left( {{n^2}} \right),\,\,\Theta \left( {n\,\log n} \right),\,\,$$ and $$\,\,\Theta \left( {n\,\log n} \right)$$

$$\Theta \left( {{n^2}} \right),\Theta \left( {n\,\log n} \right),\,\,$$ and $$\,\,\Theta \left( {{n^2}} \right)$$