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

I forgot my password
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
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
0
votes
1
answer
1
Cormen Edition 3 Exercise 7.4 Question 6 (Page No. 185)
Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst a $\alpha$to$(1\alpha)$ split, as a function of $\alpha$ in the range $0<\alpha<1$.
asked
Jun 28
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

17
views
cormen
algorithms
quicksort
descriptive
difficult
0
votes
1
answer
2
Cormen Edition 3 Exercise 7.4 Question 5 (Page No. 185)
We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is nearly sorted. Upon calling quicksort on a subarray with fewer than $k$ elements, let it simply return without ... $k$, both in theory and in practice?
asked
Jun 28
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

11
views
cormen
algorithms
quicksort
descriptive
0
votes
1
answer
3
Cormen Edition 3 Exercise 7.4 Question 4 (Page No. 184)
Show that RANDOMIZEDQUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.
asked
Jun 28
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

38
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
4
Cormen Edition 3 Exercise 7.4 Question 3 (Page No. 184)
Show that the expression $q^2 +(nq1)^2$ achieves a maximum over $q=0,1,\dots ,n1$ when $q=0$ or $q=n1$.
asked
Jun 28
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

11
views
cormen
algorithms
quicksort
descriptive
0
votes
0
answers
5
Cormen Edition 3 Exercise 7.4 Question 2 (Page No. 184)
Show that quicksort’s bestcase running time is $\Omega(n\ lg\ n)$.
asked
Jun 28
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

18
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
6
Cormen Edition 3 Exercise 7.3 Question 2 (Page No. 180)
RANDOMIZEDQUICKSORT(A, p, r) 1 if p < r 2 q = RANDOMIZEDPARTITION(A, p, r) 3 RANDOMIZEDQUICKSORT(A, p, q  1) 4 RANDOMIZEDQUICKSORT(A, q + 1, r) RANDOMIZEDPARTITION(A, p, r) 1 i = RANDOM(p, r) 2 ... made to the random number generator RANDOM in the worst case? How about in the best case? Give your answer in terms of $\Theta$ notation.
asked
Jun 28
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

12
views
cormen
algorithms
quicksort
descriptive
0
votes
1
answer
7
Cormen Edition 3 Exercise 7.3 Question 1 (Page No. 180)
Why do we analyze the expected running time of a randomized algorithm and not its worstcase running time?
asked
Jun 28
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

9
views
cormen
algorithms
quicksort
descriptive
0
votes
1
answer
8
Cormen Edition 3 Exercise 7.2 Question 6 (Page No. 179)
Argue that for any constant $0<\alpha\leq 1/2$, the probability is approximately $12\alpha$ that on a random input array, PARTITION produces a split more balanced than $1\alpha$ to $\alpha$.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

9
views
cormen
algorithms
quicksort
descriptive
difficult
0
votes
0
answers
9
Cormen Edition 3 Exercise 7.2 Question 5 (Page No. 178)
Suppose that the splits at every level of quicksort are in the proportion $1\alpha$ to $\alpha$, where $0<\alpha\leq1/2$ is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately $lg\ n /lg\ \alpha$ and the maximum depth is approximately $lg\ n / lg\ (1\alpha)$.(Don’t worry about integer roundoff.)
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

11
views
cormen
algorithms
quicksort
descriptive
0
votes
0
answers
10
Cormen Edition 3 Exercise 7.2 Question 3 (Page No. 178)
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

13
views
cormen
algorithms
quicksort
timecomplexity
descriptive
+1
vote
1
answer
11
Cormen Edition 3 Exercise 7.2 Question 2 (Page No. 178)
What is the running time of QUICKSORT when all elements of the array $A$ have the same value?
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

30
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
12
Cormen Edition 3 Exercise 7.1 Question 4 (Page No. 174)
QUICKSORT(A,p,r) 1 if p < r 2 q = PARTITION(A,p,r) 3 QUICKSORT(A, p , q1) 4 QUICKSORT(A, q + 1, r) How would you modify QUICKSORT to sort into nonincreasing order?
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

10
views
cormen
algorithms
quicksort
descriptive
0
votes
1
answer
13
Cormen Edition 3 Exercise 7.1 Question 3 (Page No. 174)
Give a brief argument that the running time of PARTITION on a subarray of size $n$ is $\Theta(n)$.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

12
views
cormen
algorithms
quicksort
descriptive
0
votes
0
answers
14
Cormen Edition 3 Exercise 7.1 Question 2 (Page No. 174)
What value of $q$ does PARTITION return when all elements in the array $A[p..r]$ have the same value? Modify PARTITION so that $q=\lfloor(p+r)/2 \rfloor$ when all elements in the array $A[p..r]$ have the same value.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

14
views
cormen
algorithms
sorting
quicksort
descriptive
0
votes
0
answers
15
Cormen Edition 3 Exercise 7.1 Question 1 (Page No. 173)
PARTITION(A,p,r) 1 x = A[r] 2 i = p – 1 3 for j = p to r – 1 4 if A[j] <= x 5 i = i + 1 6 exchange A[i] with A[j] 7 exchange A[i+1] with A[r] 8 return i + 1 illustrate the operation of PARTITION on the array $A=\langle 13,19,9,5,12,8,7,4,21,2,6,11\rangle$
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

12
views
cormen
algorithms
sorting
quicksort
descriptive
+6
votes
3
answers
16
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
(
416k
points)

2.9k
views
gate2019
numericalanswers
algorithms
quicksort
probability
0
votes
1
answer
17
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.5k
points)

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

44
views
acetestseries
algorithms
quicksort
+1
vote
0
answers
19
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.7k
points)

108
views
algorithms
quicksort
0
votes
2
answers
20
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
(
18k
points)

96
views
algorithms
sorting
quicksort
mergesort
0
votes
0
answers
21
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
(
257
points)

39
views
algorithms
quicksort
timecomplexity
0
votes
0
answers
22
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.9k
points)

53
views
algorithms
sortingalgorithmsquicksort
sorting
quicksort
0
votes
0
answers
23
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
(
113k
points)

38
views
quicksort
+1
vote
1
answer
24
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
(
2.4k
points)

66
views
algorithms
quicksort
+1
vote
2
answers
25
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
(
257
points)

432
views
quicksort
sorting
timecomplexity
0
votes
0
answers
26
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
(
365
points)

23
views
quicksort
+3
votes
1
answer
27
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
(
71
points)

158
views
algorithms
probability
quicksort
+1
vote
1
answer
28
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.6k
points)

107
views
algorithms
quicksort
+1
vote
1
answer
29
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
(
8k
points)

291
views
quicksort
algorithms
sorting
timecomplexity
+7
votes
1
answer
30
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
Veteran
(
416k
points)

414
views
tifr2018
algorithms
sorting
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged quicksort
Recent Blog Comments
Refund time depends on the payment mode ...
@Arjun Sir , when can i expect my refund in the...
This book is returned you can enable a pay now...
@Pranavcool The book stocks are over and no one...
@Lokesh Thats unfortunate. I have refunded you....
49,830
questions
54,802
answers
189,512
comments
80,755
users