How can I make my code faster for SIGNFLIP problem?

1

My Solution : CodeChef: Practical coding for everyone

Problem Statement : CodeChef: Practical coding for everyone

Why am I getting TLE, I have seen other people solution and they have used quick sort from stdlib.h library ( qsort() ) as well, is my way of implementing quick sort slow ??
How can I write better and faster code in general please suggest ?

2

The way you choose the pivot element has a chance to make quicksort work in O(n^2). For example, try sorting 10^6 elements that are in an array in reversed order (e.g. 10 9 8 7 6 5 4 3 2 1). Your quicksort will take a long time.

Quicksort algorithm works on average O(n \log n). But worst case is O(n^2).

The way you could improve your implementation is to pick the pivot at random.

1 Like
3

I made my pivot random but my it still gives TLE :pensive:. I tried inbuilt qsort() and for some reason I get AC . :man_shrugging:

4

Unfortunately rand() gives back values from 0 to RAND_MAX and RAND_MAX is not big enough. So it’s not selecting all of the values in the range.

Although, I’m not sure if they are really testing that thoroughly.

You can use lrand48 from stdlib but doing % k will not result in uniformly random numbers (but I think that’s fine for the task).

Outside of randomness.

You start quicksort with l and h. That is in total h-l numbers if h is not included.

But look at the lines:

        quick_sort(arr,0,j);
        quick_sort(arr,j+1,h);

You want to sort quick_sort(arr, l, j), which is j-l numbers if j is not included. But your recursion always goes from 0. This will be in total j-0+h-j-1=h-1 numbers sorted on each recursion call. Your quicksort implementation has a bug where it is always quadratic.

2 Likes