Register

Recent questions tagged quick-sort

0 votes
0 answers
62
cormen 3rd edition 7.2-6
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?
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 α....
User Avatar
1 votes
1 answer
65
Doubt
In Randomized Quick sort, Can we have partitioning algorithm that never gives worst case as $O(n^2)$ for every input?
In Randomized Quick sort, Can we have partitioning algorithm that never gives worst case as $O(n^2)$ for every input?
User Avatar
3 votes
1 answer
66
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)
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...
User Avatar
1 votes
0 answers
69
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
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,2A2=1,2,3,4,5
User Avatar
0 votes
2 answers
70
quick sort
User Avatar
1 votes
1 answer
72
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.
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 e...
User Avatar
3 votes
3 answers
73
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.
"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 ...
User Avatar
1 votes
1 answer
74
Please solve this Q
Q. The best case of quick sort helps Aditya to sort a particular data set of size ‘n’ in 640 ms. Suresh also tried the same algorithm on similar data set and it took him 256 ms in best case to sort a file of size 16. What could be Aditya’s file size?
Q. The best case of quick sort helps Aditya to sort a particular data set of size ‘n’ in 640 ms. Suresh also tried the same algorithm on similar data set and it took...
User Avatar
3 votes
1 answer
75
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?
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?
User Avatar
2 votes
3 answers
77
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.
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.
User Avatar
0 votes
2 answers
78
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 .
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 .
User Avatar
0 votes
1 answer
79
Space Complexity of Quick Sort
Is Quick Sort an in-place algorithm? I read somewhere that although its space complexity is O(logn) [best case], it is referred to as an in place algo by Wikipedia because it involves just swapping of elements. What is Correct?
Is Quick Sort an in-place algorithm?I read somewhere that although its space complexity is O(logn) [best case], it is referred to as an in place algo by Wikipedia because...
User Avatar
2 votes
5 answers
81
Algorithm quicksort
Reply with solution @ Habibkhan,@Gabbar,@Arjun Sir
Reply with solution @ Habibkhan,@Gabbar,@Arjun Sir
User Avatar
0 votes
1 answer
84
ace mock 6
which of the following methods will be the best if number of swappings done, is the only measure of efficiency? A) Bubble sort B) Selection sort C) Insertion sort D) Quick sort
which of the following methods will be the best if number of swappings done, is the only measure of efficiency?A) Bubble sort B) Selection sortC) Insertion so...
User Avatar
2 votes
1 answer
87
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)
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? (Assum...
User Avatar
1 votes
3 answers
89
ME test series
Suppose that the partition algorithm of quick sort always produce a 9-to-1 proportional split. Then the Running time of algorithm over an unsorted array of n-elements is ____________________? a) O(n2) b) O(nlogn) c) O(n) d) None
Suppose that the partition algorithm of quick sort always produce a 9-to-1 proportional split. Then the Running time of algorithm over an unsorted array of n-elements is ...
User Avatar
Page: