# GATE Questions & Answers of Sorting

## What is the Weightage of Sorting in GATE Exam?

Total 14 Questions have been asked from Sorting topic of Algorithms subject in previous GATE papers. Average marks 1.64.

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?

I.    Quicksort runs in $\mathrm\Theta\left(\mathit n^\mathit2\right)$ time

II.   Bubblesort runs in $\mathrm\Theta\left(\mathit n^\mathit2\right)$ time

III.  Mergesort runs in $\mathrm\Theta\left(\mathit n\right)$ time

IV Insertion sort runs in $\mathrm\Theta\left(\mathit n\right)$ time

##### Show Answer

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

##### Show Answer

Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

##### Show Answer

The number of elements that can be sorted in Θ(log n) time using heap sort is

##### Show Answer

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

##### Show Answer

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

##### Show Answer

The running time of an algorithm is represented by the following recurrence relation:

$T\left(n\right)=\left\{\begin{array}{ll}n& n\le 3\\ T\left(\frac{n}{3}\right)+cn& otherwise\end{array}\right\$

Which one of the following represents the time complexity of the algorithm?

##### Show Answer

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

##### Show Answer

Consider the following C functions:
int f1 (int n)
{
if (n == 0 | | n == 1)
return n;
else
return (2* f1 (n - 1) + 3 * f1 (n - 2))
}
int f2 (int n)
{
int i:
int X[N], Y[N], Z[N];
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
for (i = 2; i <= n; i ++) {
X[i] = Y[i ? 1] + Z[i ? 2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];
}
return X[n];
}

The running time of f1 (n) and f2 (n) are

##### Show Answer

Consider the following C functions:
int f1 (int n)
{
if (n == 0 | | n == 1)
return n;
else
return (2* f1 (n - 1) + 3 * f1 (n - 2))
}
int f2 (int n)
{
int i:
int X[N], Y[N], Z[N];
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
for (i = 2; i <= n; i ++) {
X[i] = Y[i ? 1] + Z[i ? 2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];
}
return X[n];
}

f1 (8) and f2 (8) return the values

##### Show Answer

Consider the following segment of C-code:

int j, n;
j = 1;
while (j <= n)
j = j*2;

The number of comparisons made in the execution of the loop for any n > 0 is:

##### Show Answer

What is the time complexity of the following recursive function:

int DoSomething (int n) {
if (n <= 2)
return 1;
else
return (DoSomething (floor(sqrt(n))) + n);
}

##### Show Answer

An array n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

##### Show Answer

Consider the following C code segment:

int IsPrime(n)
{
int i,n;
for(i=2;i<=sqrt(n);i++)
if(n%i == 0)
{printf(“Not Prime\n”); return 0;}
return 1;
}

Let T(n) denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?