Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged quick-sort
0
votes
1
answer
31
Cormen Edition 3 Exercise 7.4 Question 3 (Page No. 184)
Show that the expression $q^2 +(n-q-1)^2$ achieves a maximum over $q=0,1,\dots ,n-1$ when $q=0$ or $q=n-1$.
Show that the expression $q^2 +(n-q-1)^2$ achieves a maximum over $q=0,1,\dots ,n-1$ when $q=0$ or $q=n-1$.
akash.dinkar12
248
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
0
votes
2
answers
32
Cormen Edition 3 Exercise 7.4 Question 2 (Page No. 184)
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.
akash.dinkar12
632
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
quick-sort
time-complexity
descriptive
+
–
0
votes
1
answer
33
Cormen Edition 3 Exercise 7.3 Question 2 (Page No. 180)
RANDOMIZED-QUICKSORT(A, p, r) 1 if p < r 2 q = RANDOMIZED-PARTITION(A, p, r) 3 RANDOMIZED-QUICKSORT(A, p, q - 1) 4 RANDOMIZED-QUICKSORT(A, q + 1, r) RANDOMIZED-PARTITION(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.
RANDOMIZED-QUICKSORT(A, p, r) 1 if p < r 2 q = RANDOMIZED-PARTITION(A, p, r) 3 RANDOMIZED-QUICKSORT(A, p, q – 1) 4 RANDOMIZED-QUICKSORT(A, q + 1, r) RANDOMIZED-PARTITIO...
akash.dinkar12
478
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
0
votes
1
answer
34
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 worst-case running time?
Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?
akash.dinkar12
328
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
1
votes
1
answer
35
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 $1-2\alpha$ that on a random input array, PARTITION produces a split more balanced than $1-\alpha$ to $\alpha$.
Argue that for any constant $0<\alpha\leq 1/2$, the probability is approximately $1-2\alpha$ that on a random input array, PARTITION produces a split more balanced than $...
akash.dinkar12
402
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
difficult
+
–
0
votes
0
answers
36
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 round-off.)
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 ...
akash.dinkar12
319
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
0
votes
0
answers
37
Cormen Edition 3 Exercise 7.2 Question 4 (Page No. 178)
Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order ... -sorted input. Argue that the procedure INSERTION-SORT would tend to beat the procedure QUICKSORT on this problem.
Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order...
akash.dinkar12
493
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
sorting
quick-sort
descriptive
+
–
0
votes
1
answer
38
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.
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.
akash.dinkar12
1.1k
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
time-complexity
descriptive
+
–
1
votes
2
answers
39
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?
What is the running time of QUICKSORT when all elements of the array $A$ have the same value?
akash.dinkar12
511
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
time-complexity
descriptive
+
–
0
votes
1
answer
40
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 , q-1) 4 QUICKSORT(A, q + 1, r) How would you modify QUICKSORT to sort into nonincreasing order?
QUICKSORT(A,p,r) 1 if p < r 2 q = PARTITION(A,p,r) 3 QUICKSORT(A, p , q-1) 4 QUICKSORT(A, q + 1, r)How would you modify QUICKSORT to sort into nonincreasing order?
akash.dinkar12
908
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
0
votes
1
answer
41
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)$.
Give a brief argument that the running time of PARTITION on a subarray of size $n$ is $\Theta(n)$.
akash.dinkar12
1.4k
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
0
votes
1
answer
42
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.
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 element...
akash.dinkar12
1.7k
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
sorting
quick-sort
descriptive
+
–
0
votes
1
answer
43
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$
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 illustrat...
akash.dinkar12
1.5k
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
sorting
quick-sort
descriptive
+
–
29
votes
4
answers
44
GATE CSE 2019 | Question: 20
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 ________
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 ge...
Arjun
16.1k
views
Arjun
asked
Feb 7, 2019
Algorithms
gatecse-2019
numerical-answers
algorithms
quick-sort
probability
1-mark
+
–
3
votes
4
answers
45
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)
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 se...
newdreamz a1-z0
1.5k
views
newdreamz a1-z0
asked
Jan 21, 2019
Algorithms
algorithms
sorting
quick-sort
made-easy-test-series
+
–
0
votes
1
answer
46
Ace Test Series: Algorithms - Sorting
Shankar Kakde
542
views
Shankar Kakde
asked
Jan 13, 2019
Algorithms
ace-test-series
algorithms
quick-sort
recurrence-relation
+
–
0
votes
1
answer
47
made easy adv 2018
The median of n elements can be found in O(logn) time.which one of the following is correct about worst case time complexity of quick sort,if always median is selected as pivot element? a)O(logn) b)O(n) c)O(nlogn) d)O(nloglogn)
The median of n elements can be found in O(logn) time.which one of the following is correct about worst case time complexity of quick sort,if always median is selected a...
Gate Fever
1.1k
views
Gate Fever
asked
Dec 16, 2018
Algorithms
algorithms
time-complexity
quick-sort
made-easy-test-series
+
–
2
votes
0
answers
48
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 sub-array 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}{n-1}) = \frac{2}{n-1} $ Please verify.
Que – Consider the recursive quicksort algorithm with “random pivoting”. That is, in each recursive call, a pivot is chosen uniformly at random from the sub-array b...
Soumya29
1.0k
views
Soumya29
asked
Dec 3, 2018
Algorithms
algorithms
quick-sort
+
–
1
votes
2
answers
49
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.
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 ad...
Shubhanshu
5.0k
views
Shubhanshu
asked
Dec 1, 2018
Algorithms
algorithms
sorting
quick-sort
merge-sort
+
–
0
votes
1
answer
50
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 worst-case 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 worst-case time complexity for these three cases is O(n2) irrespective of the selection of the pivot element?
Consider the following inputs:1) 2 2 2 2 2 2 22) 1 2 3 4 5 6 73) 7 6 5 4 3 2 1In all three cases, the worst-case time complexity of quicksort is O(n2) My doubt is if I am...
garvit_vijai
869
views
garvit_vijai
asked
Nov 16, 2018
Algorithms
algorithms
quick-sort
time-complexity
+
–
0
votes
0
answers
51
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?
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 qui...
Gurdeep Saini
289
views
Gurdeep Saini
asked
Nov 13, 2018
Algorithms
algorithms
sorting
quick-sort
+
–
0
votes
1
answer
52
Quick Sort
In Quicksort let n/7 th smallest element is chosen using an O(n2 ) algorithm as the pivot. Calculate the worst case time complexity of the algorithm.
In Quicksort let n/7 th smallest element is chosen using an O(n2 ) algorithm as thepivot. Calculate the worst case time complexity of the algorithm.
Purvi Agrawal
3.7k
views
Purvi Agrawal
asked
Oct 13, 2018
Algorithms
quick-sort
algorithms
time-complexity
recurrence-relation
+
–
1
votes
2
answers
53
self doubt
What is the worst case time complexity of Quick Sort? Is it nlogn or n2
What is the worst case time complexity of Quick Sort?Is it nlogn or n2
Priyanka17
294
views
Priyanka17
asked
Sep 27, 2018
Algorithms
time-complexity
sorting
quick-sort
+
–
0
votes
1
answer
54
Randomized Quicksort
True or False : In randomized quicksort , each key is involved in the same number of comparisons.
True or False :In randomized quicksort , each key is involved in the same number of comparisons.
Vaishnavi01
659
views
Vaishnavi01
asked
Sep 21, 2018
Algorithms
sorting
algorithms
quick-sort
+
–
1
votes
2
answers
55
#Doubt
Quick sort is run on following inputs I1: stricltly increasing order of n input sequece I2: stricltly decreasing order of n input sequece Let S1 and S2 be the number of swaps made by the input I1 and I2 respectively Then A). S1<S2 B). S1>S2 C). S1=S2 D). Cannot predict anything for arbitrary n
Quick sort is run on following inputsI1: stricltly increasing order of n input sequeceI2: stricltly decreasing order of n input sequeceLet S1 and S2 be the number of swap...
kavya kamish upadhya
1.0k
views
kavya kamish upadhya
asked
Aug 21, 2018
Algorithms
algorithms
quick-sort
+
–
0
votes
0
answers
56
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; }
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 ...
srestha
644
views
srestha
asked
Aug 16, 2018
Programming in C
quick-sort
+
–
0
votes
1
answer
57
Ace Algorithms
If given numbers are 12,7,15,8,19,20,17,21,5,3 in _______ passes of quick sort element 5 will be in sorted position. (Considering last element as pivot)
If given numbers are 12,7,15,8,19,20,17,21,5,3 in _______ passes of quick sort element 5 will be in sorted position. (Considering last element as pivot)
Sambhrant Maurya
537
views
Sambhrant Maurya
asked
Aug 7, 2018
Algorithms
sorting
quick-sort
+
–
1
votes
1
answer
58
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?
After applying few passes of quick sort on a given array, the following output was obtained:1,10,5,8,25,44,55,30,70Then how many pivot elements are there in the above ou...
Sambhrant Maurya
1.1k
views
Sambhrant Maurya
asked
Aug 6, 2018
Algorithms
algorithms
quick-sort
+
–
0
votes
2
answers
59
sorting
The maximum number of swap possible of an unsorted array[1....n] in quicksort is? a) O(n) b) O($n^{2}$) Explain briefly.
The maximum number of swap possible of an unsorted array[1....n] in quicksort is?a) O(n)b) O($n^{2}$)Explain briefly.
Siddharth Bhardawaj
1.6k
views
Siddharth Bhardawaj
asked
Jul 19, 2018
Algorithms
sorting
quick-sort
+
–
1
votes
3
answers
60
Quicksort
Consider an array consisting of the following elements in unsorted order (placed randomly) but 60 as pivot element 60 80 15 95 7 12 35 90 55 Quicksort partition algorithm is applied by choosing first element as pivot element . How many total number of arrangement of array integers is possible preserving the effect of first pass of partition algorithm
Consider an array consisting of the following elements in unsorted order (placed randomly) but 60 as pivot element60 80 15 95 7 12 35 90 55Quicksort partition algorithm...
Tripti bhardwaj
4.0k
views
Tripti bhardwaj
asked
Jul 11, 2018
Algorithms
algorithms
quick-sort
numerical-answers
+
–
Page:
« prev
1
2
3
4
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register