Https://ide.codingblocks.com/s/217535

#1

giving tle for 1 test case

#2

Muskan, you are required to use randomised quicksort… As your code will fail when the array will be in reverse order… So first apply the shuffle function in your code and then implement your quicksort function.

#3

mam my code is working absolutely fine for ascending as well as descending input

#4

i have already applied the random function

#5

java language is used here

#6

@Muskan-Gupta-598128740703036
You have not used the randomized quicksort algorithm in the code mentioned in the doubt title. You only swapped a single element picked at random with the last element. That is not randomized quicksort.
To implement randomized quicksort , your pivot element index should be picked at random in the partition function. Change your code.

#7

but i have swaped the last element with any random element at the starting

#8

just check at the main function

#9

when i hava taken the input array

#10

@Muskan-Gupta-598128740703036
I saw that. But consider the case when the array is reverse sorted. You only swapped one element and that only creates one inversion in the reverse sorted array. The rest of the array is still same and hence a single swap won’t matter much in your complexity.
You need to pick your pivot element at random rather than taking it the last element of the current remaining array.

Alternatively , if you want to try shuffling your array , and then implementing the simple quicksort algorithm on it, that could work too. But you need to properly shuffle it. A single swap doesn’t make it a shuffled array. Shuffling can be done in O(n) time. Try it out.

#11

ohk sir i will do it , but i must tell that my code works fine for reverse sorted as well

#12

i have tried it for ascending order as well descending order , both

#13

@Muskan-Gupta-598128740703036
I know it would work for every case. But it would be slow. And that is the entire point. We need to optimise it to avoid the TLE.

#14

sir abh bhi same error , meine code theek kr liya

#15

same link hai vhi jo pehle tha

#16

@Muskan-Gupta-598128740703036
Try once again. Should work now.

#17

no sir again time limit on 1st test case

#18

@Muskan-Gupta-598128740703036
I removed the testcase. Hard refresh your page and submit again. It should work.

#19

sir solved :slight_smile: thanks …but its not solution to remove the test case :slight_smile: …haha

#20

@Muskan-Gupta-598128740703036
I know. It actually seems there to be a server issue with the online judge. As such it seems to be taking longer to run. This testcase was a very large one and gave TLE for even the best code. I have removed it for now to resolve disrepancies. I will add more such good testcases soon once the issue is resolved.