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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged quicksort
+3
votes
1
answer
1
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 24, 2018
in
Algorithms
by
Shailin Shah

311
views
algorithms
probability
quicksort
+1
vote
1
answer
2
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

180
views
algorithms
quicksort
+1
vote
1
answer
3
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

500
views
quicksort
algorithms
sorting
timecomplexity
+9
votes
1
answer
4
TIFR2018B7
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 ... ${O} \left(\dfrac{1}{n^{2}}\right)$ $\Theta\left(\dfrac{1}{n \log^{2} n}\right)$
asked
Dec 10, 2017
in
Algorithms
by
Arjun

780
views
tifr2018
algorithms
sorting
quicksort
+1
vote
1
answer
5
3way quicksort
3way partitioning is a modification of quicksort that partitioned the elements into groups smaller than,equal to and larger than pivot. Only the group of smaller and larger elements need to be sorted. If there are N items and K unique value the running time of modified quick sort is (A) O(nlogk) (B) O(klogn) (C) O(nk) (D) O(k^2)
asked
Dec 8, 2017
in
Algorithms
by
manish suthar

436
views
algorithms
sorting
quicksort
0
votes
0
answers
6
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

900
views
quicksort
+4
votes
1
answer
7
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

400
views
algorithms
datastructures
sorting
quicksort
+1
vote
1
answer
8
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

243
views
algorithms
sorting
quicksort
+3
votes
3
answers
9
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

525
views
algorithms
sorting
timecomplexity
quicksort
+2
votes
1
answer
10
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 11, 2017
in
Algorithms
by
SHALINI PORWAL

466
views
algorithms
sorting
timecomplexity
quicksort
+2
votes
3
answers
11
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

346
views
algorithms
quicksort
timecomplexity
sorting
0
votes
2
answers
12
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

501
views
algorithms
quicksort
0
votes
1
answer
13
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

637
views
quick
quicksort
algorithms
sorting
timecomplexity
+2
votes
2
answers
14
Algorithm quicksort
Reply with solution @ Habibkhan,@Gabbar,@Arjun Sir
asked
Feb 7, 2017
in
Algorithms
by
Shubham Sharma 2

506
views
sorting
algorithms
quicksort
+2
votes
1
answer
15
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
dd

878
views
algorithms
quicksort
sorting
+1
vote
1
answer
16
Quicksort
Consider an array with following element 12, 18, 17,11, 13, 15, 16 ,14 The number of element will change their initial position after completion of partition algorithm by choosing 15 as a pivot are __ Please solve step by step.
asked
Nov 19, 2016
in
Algorithms
by
Yogesh Chaure

248
views
sorting
algorithms
quicksort
+9
votes
1
answer
17
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

578
views
sorting
quicksort
algorithms
+1
vote
1
answer
18
quick sort
Is quick sort inplace algorithm?
asked
Nov 7, 2016
in
Algorithms
by
vaishali jhalani

299
views
algorithms
quicksort
sorting
0
votes
1
answer
19
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

815
views
quicksort
algorithms
sorting
timecomplexity
0
votes
1
answer
20
Algorithm
asked
Oct 8, 2016
in
Algorithms
by
Rahul Jain25

603
views
algorithms
quicksort
+2
votes
1
answer
21
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 5, 2016
in
Algorithms
by
vivek9837

361
views
sorting
algorithms
quicksort
+1
vote
1
answer
22
quick sort
is it quick sort is inplace algorithm. according to me it takes o(logn) space in best case and as i know any algo takes more then 0(1) spcae count as not inplace algo then why quick sort is inplace plz explain clearly
asked
Jul 25, 2016
in
Algorithms
by
rajan

169
views
quicksort
+2
votes
1
answer
23
UGCNETSep2013II: 10
Suppose that the splits at every level of Quicksort are in proportion $1\beta \text{ to } \beta$, where $0 < \beta \leq 0.5$ is a constant. The number of elements in an array is n. The maximum depth is approximately 0.5 $\beta$ Ig n 0.5 (1$\beta$) Ig n (Ig n)/(Ig $\beta$) (Ig n)/Ig (1$\beta$)
asked
Jul 20, 2016
in
DS
by
jothee

1.6k
views
ugcnetsep2013ii
datastructures
sorting
algorithms
quicksort
0
votes
1
answer
24
UGCNETJune2014III: 66
Suppose that the splits at every level of quicksort are in the proportion $(1 – \alpha)$ to $\alpha$, where $0<\alpha\leq\frac{1}{2}$ is a constant. The minimum depth of a leaf in the recursion tree is approximately given by $\frac{lgn}{lg(1\alpha)}$ $\frac{lg(1\alpha)}{lgn}$ $\frac{lgn}{lg\alpha}$ $\frac{lg\alpha}{lgn}$
asked
Jul 13, 2016
in
Algorithms
by
makhdoom ghaya

720
views
ugcnetjune2014iii
datastructures
sorting
algorithms
quicksort
+1
vote
1
answer
25
quick sort time complexity
the worst case time complexity of quicksort for an elements when the median is selected as the pivot a. o(n^2) b.o(n) c.o(nlogn) d.o(logn)
asked
Mar 9, 2016
in
Algorithms
by
akankshay

3.1k
views
algorithms
timecomplexity
quicksort
+3
votes
2
answers
26
Quick Sort
Consider an array with the following elements: 12, 18, 17, 11, 13, 15, 16 and 14. How many element will change their initial position after completion of partition algorithm by choosing 15 as pivot? Given Answer : 7 ( only 16 is not swapped ) My Answer : 6 ( 16 ... 13 14 12 11 15 17 16 18 So 11 and 16 are not changed all other elements have changed their position Correct me if i am wrong
asked
Jan 17, 2016
in
Algorithms
by
pC

730
views
algorithms
quicksort
0
votes
1
answer
27
Give the result of partitioning the keys after the 1st pass of quicksort.
THISCOURSEISOVER Choose the last elements as pivot elements (R). Also for duplicates, adopt the convention that both pointers stop. a) EHIOCOIERRUSSVTS b) EHISCOIERRUSOVTS b) EHIOCOUESRTSSVTR c) EHIOOCIERRUSSVTS
asked
Jul 22, 2015
in
Algorithms
by
Saurabh Sharma

300
views
sorting
algorithms
quicksort
Page:
« prev
1
2
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
IISc CDS Interview Experience, 2020
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.2k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged quicksort
Recent Blog Comments
Yeah, Now it's on.
Can you check now?
Even I filled NIELIT form which had similar...
Today's test will be late  either midnight or...
on what time will be today's test?
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,345
questions
60,522
answers
201,950
comments
95,373
users