Exams › GATE › Technical

Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?

1. t1 = 5
2. t1 < t2
3. t1 > t2
4. t1 = t2

Correct answer: t1 > t2

Solution

For [1 2 3 4 5] (sorted, first-element pivot) comparisons are 4+3+2+1=10. For [4 1 5 3 2], pivot 4 makes 4 comparisons, then [1 3 2] makes 2+1=3 and [5] makes 0, total 7. So t1=10 > t2=7, i.e. t1 > t2.

Related GATE Technical questions

• Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?
• Consider the following program in C language: #include <stdio.h> main() { int i; int *pi = &i; scanf("%d", pi); printf("%d ", i+5); } Which one of the following statements is TRUE?
• Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
• Which one of the following is TRUE ?
• Match the following: 1) Waterfall model 2) Evolutionary model 3) Component-based software engineering 4) Spiral development a) Specifications can be developed incrementally b) Requirements compromises are inevitable c) Explicit recognition of risk d) Inflexible partitioning of the project into stages
• Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ________ number of requests.

⚔️ Practice GATE Technical free + battle 1v1 →