The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged quicksort
+2
votes
2
answers
1
GATE201920
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 ________
asked
Feb 7
in
Algorithms
by
Arjun
Veteran
(
395k
points)

2.6k
views
gate2019
numericalanswers
algorithms
quicksort
probability
0
votes
0
answers
2
MadeEasy Test Series: Algorithms  Sorting
Consider a scenario of modified quick sort, where we have given an input sorted array A[1 .. . n], all elements of array are distinct and n >=3. Pivot is the median of set of 3 elements [First element, middle element, and last element]. What will be worst case time complexity of modified quick sort? a.O($n^{2}$) b.O(nlogn) c.O($n^{2}$logn) d.O(nloglogn)
asked
Jan 21
in
Algorithms
by
newdreamz a1z0
Active
(
1.7k
points)

57
views
algorithms
sorting
quicksort
madeeasytestseries
0
votes
1
answer
3
Ace Test Series: Algorithms  Sorting
asked
Jan 13
in
Algorithms
by
Shankar Kakde
(
373
points)

38
views
acetestseries
algorithms
quicksort
+1
vote
0
answers
4
Self Doubt Quick Sort
Que  Consider the recursive quicksort algorithm with random pivoting . That is, in each recursive call, a pivot is chosen uniformly at random from the subarray being sorted. When this randomized algorithm is applied to an array of size n all whose elements are distinct, what is the probability ...  $\frac{2}{n}+(\frac{1}{n}*\frac{2}{n1}) = \frac{2}{n1} $ Please verify.
asked
Dec 3, 2018
in
Algorithms
by
Soumya29
Boss
(
15.5k
points)

101
views
algorithms
quicksort
0
votes
2
answers
5
Adaptive sorting Algorithm.
Is Quick sort an adaptive sorting Algorithm? I think no. Because as per the definition given in the Wikipedia is that A adaptive sorting Algorithm is one who takes the advantage of preorderedness of the input. But in case of Quick sort it act as disadvantage.
asked
Dec 1, 2018
in
Algorithms
by
Shubhanshu
Boss
(
19.2k
points)

68
views
algorithms
sorting
quicksort
mergesort
0
votes
0
answers
6
Self Doubt  Quick Sort
Consider the following inputs: 1) 2 2 2 2 2 2 2 2) 1 2 3 4 5 6 7 3) 7 6 5 4 3 2 1 In all three cases, the worstcase time complexity of quicksort is O(n2) My doubt is if I am taking the middle element as a pivot, ... ), right? Can someone explain how we are saying worstcase time complexity for these three cases is O(n2) irrespective of the selection of the pivot element?
asked
Nov 16, 2018
in
Algorithms
by
garvit_vijai
(
297
points)

32
views
algorithms
quicksort
timecomplexity
0
votes
0
answers
7
chache performance between hoare and loranto quicksort
between hoare and loranto quicksort which give better cache performance ? we know that in hoare quicksort we move the pointer i,j in different direction but in loranto quicksort we move i,j in same direction so the cache performance of loranto should be better?
asked
Nov 13, 2018
in
Algorithms
by
Gurdeep Saini
Loyal
(
9.5k
points)

43
views
algorithms
sortingalgorithmsquicksort
sorting
quicksort
0
votes
0
answers
8
Quick Sort Analysis
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sublists each of which contains at least onefifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then: A. T(n)<=2T(n/5)+n B. T(n)<=T(n/5)+T(4n/5)+n C. T(n)<=2T(4n/5)+n D. T(n)<=2T(n/2)+n
asked
Sep 21, 2018
in
Algorithms
by
Vaishnavi01
(
217
points)

107
views
quicksort
algorithms
sorting
timecomplexity
0
votes
0
answers
9
Code Quick Sort
Why the code is not showing correct sorting ?(here pivot is smaller index element, i.e. arr[low]) #include <stdio.h> #include <stdlib.h> #include <time.h> void fillArray(int array[], int n) { time_t t; time(&t);//get current time srand(t);/ ... ;n); array = malloc(n * sizeof(int)); fillArray(array, n); quickSort(array,low,n); printArray(array, n); return 0; }
asked
Aug 16, 2018
in
Programming
by
srestha
Veteran
(
110k
points)

34
views
quicksort
+1
vote
1
answer
10
Made Easy algorithms
After applying few passes of quick sort on a given array, the following output was obtained: 1,10,5,8,25,44,55,30,70 Then how many pivot elements are there in the above output?
asked
Aug 6, 2018
in
Algorithms
by
Sambhrant Maurya
Active
(
1.7k
points)

60
views
algorithms
quicksort
+1
vote
2
answers
11
Quick Sort Time Complexity
Quick sort gives O(nlogn) worst case performance if the pivot is selected as: a) First element of the array b) Median of first, last and middle elements c) Arithmetic mean of the elements d) None of these Now, the answer is given as Option (b). But, ... order of elements and not on pivot element. So, answer should be option (d) i.e None of these Correct me if I am wrong
asked
Jul 1, 2018
in
Algorithms
by
garvit_vijai
(
297
points)

381
views
quicksort
sorting
timecomplexity
0
votes
0
answers
12
cormen 3rd edition 7.26
Argue that for any constant 0<α≤1/2, the probability is approximately 1−2α that on a random input array, PARTITION produces a split more balanced than 1−α to α. Please explain how the probability is calculated?
asked
Jun 14, 2018
in
Algorithms
by
Aarvi Chawla
(
397
points)

19
views
quicksort
+3
votes
1
answer
13
Quick Sort Algorithm
Let $0<α<.5$ be some constant (independent of the input array length $n$). What is the probability that, with a randomly chosen pivot element, the Partition subroutine produces a split in which the size of the smaller of the two subarrays is $≥α$ times the size of the original array? 1. $1  2*\alpha$ 2. $\alpha$ 3. $1  \alpha$ 4. $2  2*\alpha$
asked
May 23, 2018
in
Algorithms
by
Shailin Shah
(
115
points)

142
views
algorithms
probability
quicksort
+1
vote
1
answer
14
Doubt
In Randomized Quick sort, Can we have partitioning algorithm that never gives worst case as $O(n^2)$ for every input?
asked
Mar 29, 2018
in
Algorithms
by
Angkit
Active
(
3.8k
points)

96
views
algorithms
quicksort
+1
vote
1
answer
15
quick sort
You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest lower bound for the best case performance is a) O(n2) b) O(nlogn) c) Θ(nlogn) d) O(n3)
asked
Jan 14, 2018
in
Algorithms
by
iarnav
Loyal
(
9.7k
points)

270
views
quicksort
algorithms
sorting
timecomplexity
0
votes
0
answers
16
Quick Sort Number Of Comparison Query
What is the number of Comparison to sort below arrays using quick sort using first element as pivot ? Please show steps . A1=4,1,5,3,2 A2=1,2,3,4,5
asked
Dec 3, 2017
in
Algorithms
by
hem chandra joshi
Active
(
4.7k
points)

490
views
quicksort
+4
votes
1
answer
17
Modified form of GATE1996_2.15
Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot i) 1,2,3,…n ii) n,n−1,n−2,…,2,1 Let S1 and S2 be the number of swaps made for the inputs (i) and (ii) respectively. Then, i) How is S1 and S2 related ? ii) How will the answer change if the pivot is changed to middle element ?
asked
Oct 18, 2017
in
Algorithms
by
rishi71662data4
Active
(
2.6k
points)

277
views
algorithms
datastructure
sorting
quicksort
0
votes
1
answer
18
QUICKSORT
Could anyone describe how the partitioning algorithm vary when the pivot is varied ? In Cormen , last element is taken as pivot . Suppose I took first element or middle element or 3 rd element as pivot then how the partitioning algorithm will change.
asked
Sep 27, 2017
in
Algorithms
by
ashwina
Active
(
2.1k
points)

121
views
algorithms
sorting
sortingalgorithmsquicksort
quicksort
+3
votes
3
answers
19
Quick Sort
"Quick sort has good cache performance" , Can anyone explain this statement.How is cache related to quick sort.I searched for this over the internet but could not find a good article.
asked
Sep 3, 2017
in
Algorithms
by
Sourajit25
Active
(
1.1k
points)

286
views
algorithms
sorting
timecomplexity
quicksort
+2
votes
1
answer
20
Quick sort
When array is already sorted in reverse order then what will be the recurrence relation for number of swaps on array of n elements using quick sort?
asked
Aug 10, 2017
in
Algorithms
by
SHALINI PORWAL
(
31
points)

331
views
algorithms
sorting
timecomplexity
quicksort
+2
votes
3
answers
21
With quick sort The results after first partioning of the given array
With quick sort The results after first partioning of the given array. A = (2,8,7,1,3,5,6,4,9). Analysis the time complexity of Quick sort in the best case.
asked
Apr 15, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
5.2k
points)

217
views
algorithms
quicksort
timecomplexity
sorting
0
votes
2
answers
22
A list of elements are given A  <3,1,4,1,5,9,2,6,5,3,5,8,9 >
A list of elements are given A  <3,1,4,1,5,9,2,6,5,3,5,8,9 > Show Howw the "Pivot" and quick sort algorithm work. finally show the Best Case analysis for quick sort .
asked
Apr 15, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
5.2k
points)

404
views
algorithms
quicksort
0
votes
1
answer
23
GATE 2008 Quick Sort
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sublists each of which contains at least onefifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then A. T(n) < ... (4n/5) + n, if elements are more than (n/5)( since it is given 'AT LEAST'). Where am I going wrong?
asked
Mar 29, 2017
in
Algorithms
by
Bongbirdie
Junior
(
765
points)

403
views
quick
quicksort
algorithms
sorting
timecomplexity
+2
votes
1
answer
24
quick sort
If we use quicksort algorithm to sort the elements: $16, 13, 14, 12, 21, 16, 23$ and $15$ in ascending order, what is the output after the first pass of quicksort? (Assume pivot element is beginning of an array)
asked
Jan 20, 2017
in
Algorithms
by
Debashish Deka
Veteran
(
58.2k
points)

540
views
algorithms
quicksort
sorting
+8
votes
1
answer
25
New Gradience Sorting
There are many variations of Quicksort. We may choose the pivot for each partition step in various ways. There are various strategies for partitioning an array segment into one subpartition of consecutive array positions that has values less than or equal to the pivot and another subpartition of consecutive array ... , 8, 9 b) 3, 1, 3, 1 c) 5, 4, 3, 3, 5 d) 1, 4, 1, 3
asked
Nov 15, 2016
in
Algorithms
by
mohit chawla
Active
(
2.7k
points)

414
views
sorting
quicksort
algorithms
+1
vote
1
answer
26
quick sort
Is quick sort inplace algorithm?
asked
Nov 7, 2016
in
Algorithms
by
vaishali jhalani
Loyal
(
6k
points)

222
views
algorithms
quicksort
sorting
0
votes
2
answers
27
Quick sort
@arjun sir why is quick sort with median as pivot not in practice even though it can sort the worst case list in O(nlogn) time? median can be found in O(n) time and this divides list into two halves. recurrance relation becomes T(n) = ... implement it bcoz "The hidden constants in this approach are high compared to normal Quicksort" but why are we caring about constants here?
asked
Nov 2, 2016
in
Algorithms
by
Anusha Motamarri
Boss
(
12.4k
points)

558
views
quicksort
algorithms
sorting
timecomplexity
+3
votes
0
answers
28
Doubt: DAA: Quick Sort
If every time a median which takes O(n) to be found, is chosen as pivot, then Quick Sort takes theeta(nlogn) time complexity. My question is if all the elements are same, will still be this median Quick Sort have time complexity as theeta(nlogn)?? Can someone please run the algo for 10, 10, 10, 10, 10 if the worst time TC is nlogn in case if median Quick Sort.
asked
Nov 2, 2016
in
Algorithms
by
Vijay Thakur
Boss
(
17.3k
points)

251
views
algorithms
sorting
timecomplexity
quicksort
0
votes
1
answer
29
Algorithm
asked
Oct 7, 2016
in
Algorithms
by
Rahul Jain25
Boss
(
11.7k
points)

237
views
algorithms
quicksort
+2
votes
1
answer
30
Randomised quicksort
Let us a consider a series of events where a random partition procedure always picks the median element among n distinct numbers dividing the array into two equal halves ( ignore floor and ceiling). What is the probability that such a partition procedure always picks the median element in all subsequent arrays till the entire array is sorted.
asked
Oct 4, 2016
in
Algorithms
by
vivek9837
Junior
(
923
points)

254
views
sorting
algorithms
quicksort
Page:
1
2
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
GATE score validity queries.
How to prepare for IISC Interdisciplinary Mathematical Sciences Interview
GO Hardcopy for GATE 2020
How to prepare for BARC interview
IIIT H
Follow @csegate
Recent questions tagged quicksort
Recent Blog Comments
THey removed it this year... I did not check it,...
even though i am not going for iiit , can you...
I don't think IIITD requires any codechef...
Will apply for IIITB. IIIT D requires a codechef...
Go for it. Nobody cares once you join a good IIT...
50,071
questions
53,206
answers
184,562
comments
70,425
users