Recent questions tagged quicksort - GATE CSE Doubts

0 votes

0 answers

Average case analysis in Quicksort
In quick sort the time complexity equation is T(n)=T(k)+T(n-k-1)+⊝(n) in average case how does the equation comes out to be T(n)=T(n/9)+T(9n/10)+⊝(n) in Average case.

asked Apr 4 in Algorithms by soham04 (5 points) | 6 views

0 votes

0 answers

GATE 2014, QuickSort Comparisons
Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following holds? t1 = 5 t1 < t2 t1 > t2 t1 = t2

asked Dec 22, 2020 in Algorithms by susmit600 (5 points) | 27 views

0 votes

0 answers

quicksort sorting
I am getting a segmentation fault at line 12. when i tried to print temp it went in infinite loop. (si-start index, ei-end index) ; using namespace std; #include<iostream> void partition(int arr[],int si,int ei) { int i,count=0, temp; for(i=si+1;i<=ei;i++) { if(arr[ ... ) { cin>>arr[i]; } quicksort(arr,0,n-1); for(i=0;i<n;i++) { cout<<arr[i]; } return 0; }?

asked Sep 13, 2020 in Programming by jaskiran (5 points) | 39 views

0 votes

1 answer

MadeEasy Test Series
Sir, I think the answer is incorrect. It should be 9. Please confirm once. Here is my solution: They have clearly stated to exclude the comparisons if order of elements doesn't change in an insertion sort iteration. A = {15,7,20,13,87,3} Step1: {7,15,20,13,87,3} --> 1 comparison between 7 and ... -------------------------------------------------- Total 5+3+1 = 9 comparisons.

asked Aug 15, 2020 in Algorithms by sankalpmittal (41 points) | 20 views

0 votes

1 answer

Made easy postal study package
Give the result of partitioning the keys. T H I S C O U R S E I S O V E R after the 1st pass of quick sort. Choose the last elements as pivot elements(R). Also for duplicates, adopt the convention that both pointers stop. A)EHIOCOIERRUSSVTS B)EHISCOIERRUSOVTS C)EHIOCOUESRTSSVTR D)EHIOOCIERRUSSVTS (PLEASE SOMEONE SOLVE THIS)

asked Aug 6, 2020 in Algorithms by Prakhar Garg (5 points) | 32 views

0 votes

0 answers

GATE2019-20 Video Solution
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 Apr 18, 2020 in Algorithms by admin (573 points) | 6 views

0 votes

1 answer

Analysis of algorithms
Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort. A O(n^2 Logn) B O(n^2) C O(n Logn Logn) D O(nLogn)

asked Apr 18, 2020 in Algorithms by Prajesh007 (5 points) | 349 views

0 votes

2 answers

Made easy FLT 2020
Answer should be O(n^2) …. but they have given it as O(n^3).

asked Jan 17, 2020 in Programming by Priyansh Singh (227 points) | 55 views

0 votes

2 answers

made easy test series quick sort time complexity

asked Sep 20, 2019 in Algorithms by ck (5 points) | 188 views

To see more, click for the full list of questions or popular tags.

9,200 questions

3,182 answers

14,686 comments

96,168 users