Questions & Answers of Sorting

Weightage of Sorting

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

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?

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

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

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

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?

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

Tn=nn3Tn3+cnotherwise

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

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

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

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

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:

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);
}

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?

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?