Register

GATE CSE 2014 Set 1 | Question: 14

• edited by
19,308 views
46 votes
46 votes

Let $P$ be quicksort program to sort numbers in ascending order using the first element as the pivot. Let $t_1$ and $t_2$ 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. $t_1 = 5$
  2. $t_1 < t_2$
  3. $t_1>t_2$
  4. $t_1 = t_2$
• edited by
User Avatar

6 Answers

–3 votes
–3 votes
both arrays are worst case example of Quick sort .∴ t1=t2.
User Avatar
–5 votes
–5 votes

i think equal number of comparisons are required as the pivot element is always the highest or lwest element in the current array being worked on

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

31 votes
31 votes
5 answers
1
go_editor asked Sep 26, 2014
7,693 views
GATE CSE 2014 Set 1 | Question: 13
Consider the directed graph below given. Which one of the following is TRUE? The graph does not have any topological ordering. Both PQRS and SRQP are topological orderings. Both PSRQ and SPRQ are topological orderings. PSRQ is the only topological ordering.
Consider the directed graph below given. Which one of the following is TRUE?The graph does not have any topological ordering.Both PQRS and SRQP are topological orderings....
User Avatar
61 votes
61 votes
10 answers
2
go_editor asked Sep 28, 2014
30,889 views
GATE CSE 2014 Set 3 | Question: 14
You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is $O(n^2)$ $O(n \log n)$ $\Theta(n\log n)$ $O(n^3)$
You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the...
User Avatar
19 votes
19 votes
4 answers
3
go_editor asked Sep 28, 2014
5,265 views
GATE CSE 2014 Set 1 | Question: 46
The function $f(x) =x \sin x$ satisfies the following equation: $f''(x) + f(x) +t \cos x = 0$The value of $t$ is______.
The function $f(x) =x \sin x$ satisfies the following equation: $$f''(x) + f(x) +t \cos x = 0$$The value of $t$ is______.
User Avatar
54 votes
54 votes
4 answers
4
go_editor asked Sep 28, 2014
18,912 views
GATE CSE 2014 Set 1 | Question: 36
Which of the regular expressions given below represent the following DFA? $0^*1(1+00^*1)^* $ $0^*1^*1+11^*0^*1 $ $(0+1)^*1$ I and II only I and III only II and III only I, II and III
Which of the regular expressions given below represent the following DFA?$0^*1(1+00^*1)^* $$0^*1^*1+11^*0^*1 $$(0+1)^*1$I and II onlyI and III onlyII and III onlyI, II an...
User Avatar
Link Copied!