Quick sort question

#1


in test case 3 it is showing time limit error wven though I have used shuffle function

#2

Hello @ayush15goel,

No you don’t have to shuffle the array each time.It will increase the time complexity.

In randomized Quick Sort,
example: 3,2,1,4

  1. you have to randomly select an element of the array.
    Suppose you selected 2.

  2. Swap it with the element at last index of the array.
    After Swapping: 3,4,1,2

  3. Now, perform the normal Quick sort on above taking last index as pivot.

4.Repeat all three steps for each iteration.

Hope, this would help.
Give a like if you are satisfied.

#3

tried this,but still showing time limit error.Can you pl make correction in the code

#4

Please, share the code where you have tried what i have suggested.

#5
#6

In your code neither you are implementing the 2nd point nor 4th point of my previous reply.

  1. The location where you are executing shuffle is wrong,
  2. The logic of shuffle is also wrong

Modification:

void quicksort(int a[],int s,int e){
if(s>=e){
return;
}
//Don’t use shuffle.
srand(time(NULL));
int random = s + rand() % (e - s);
swap(arr[random], arr[e]);

int p=partition(a,s,e);
quicksort(a,s,p-1);
quicksort(a,p+1,e);
}

This will solve your problem.
Give a like if you are satisfied.

1 Like
#7

thank you sir,got the mistake and it is working now

#8

Please, mark it as resolved.
BTW, i wont mind a like.:joy: