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
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged quicksort
0
votes
2
answers
1
QUICK SORT SELF DOUBT
In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexity of quick sort. O($n^2$) O($n^3$) O(nlogn) O(n)
asked
Sep 2
in
Algorithms
by
ajaysoni1924
Boss
(
10.5k
points)

171
views
algorithms
divideandconquer
quicksort
0
votes
1
answer
2
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.7k
points)

26
views
cormen
algorithms
quicksort
descriptive
difficult
0
votes
1
answer
3
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.7k
points)

19
views
cormen
algorithms
quicksort
descriptive
0
votes
1
answer
4
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.7k
points)

59
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
5
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.7k
points)

16
views
cormen
algorithms
quicksort
descriptive
0
votes
1
answer
6
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.7k
points)

27
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
7
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.7k
points)

28
views
cormen
algorithms
quicksort
descriptive
0
votes
1
answer
8
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.7k
points)

14
views
cormen
algorithms
quicksort
descriptive
0
votes
1
answer
9
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.7k
points)

13
views
cormen
algorithms
quicksort
descriptive
difficult
0
votes
0
answers
10
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.7k
points)

16
views
cormen
algorithms
quicksort
descriptive
0
votes
0
answers
11
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.7k
points)

17
views
cormen
algorithms
quicksort
timecomplexity
descriptive
+1
vote
1
answer
12
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.7k
points)

45
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
13
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.7k
points)

17
views
cormen
algorithms
quicksort
descriptive
0
votes
1
answer
14
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.7k
points)

14
views
cormen
algorithms
quicksort
descriptive
0
votes
0
answers
15
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.7k
points)

17
views
cormen
algorithms
sorting
quicksort
descriptive
0
votes
0
answers
16
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.7k
points)

16
views
cormen
algorithms
sorting
quicksort
descriptive
+9
votes
3
answers
17
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
(
422k
points)

3.1k
views
gate2019
numericalanswers
algorithms
quicksort
probability
0
votes
2
answers
18
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.6k
points)

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

49
views
acetestseries
algorithms
quicksort
+1
vote
0
answers
20
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
(
16.1k
points)

145
views
algorithms
quicksort
0
votes
2
answers
21
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
(
18.2k
points)

110
views
algorithms
sorting
quicksort
mergesort
0
votes
0
answers
22
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)

54
views
algorithms
quicksort
timecomplexity
0
votes
0
answers
23
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
Boss
(
10.2k
points)

58
views
algorithms
sortingalgorithmsquicksort
sorting
quicksort
0
votes
0
answers
24
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
(
116k
points)

40
views
quicksort
+1
vote
1
answer
25
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
(
3.3k
points)

74
views
algorithms
quicksort
+1
vote
2
answers
26
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)

482
views
quicksort
sorting
timecomplexity
0
votes
0
answers
27
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)

25
views
quicksort
+3
votes
1
answer
28
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)

169
views
algorithms
probability
quicksort
+1
vote
1
answer
29
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)

111
views
algorithms
quicksort
+1
vote
1
answer
30
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
(
8.2k
points)

312
views
quicksort
algorithms
sorting
timecomplexity
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
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Minimal Deterministic Finite Automata
To be aware of fake GATE test series
Standard Book Exercise Questions for Computer Science
Follow @csegate
Recent questions tagged quicksort
Recent Blog Comments
Favorite is not working for blogs.. In favorites...
Favourite option does work. But list options...
Blog favorite button doesnt work?
@Arjun Sir can we have an option to save such...
Thanks Sir
50,666
questions
56,165
answers
193,787
comments
93,872
users