About Quicksort and Mergesort

#1

I just finished studying about Quicksort and Mergesort from the lectures. However, I couldn’t find the analysis about the best case and worst case performance in terms of time complexity and use of auxiliary space. Please make me understand the cases along with the resons.

#2

hey @anshufirefox the best case and the worst case are defined according to the array which we have to sort.
like if you think about an array which is completely shuffled and there is no correctly sorted part in that, then arrives the worst case or algorithm will complete the task in the worst case .
but in contrary to this if only one or two elements are not in the sorted format then the algorithm will run in the best case time complexity.
if you have any doubt you can ask here:
Happy Learning !!

#3

I observed that if by mistake, we run the for loop till e and not e-1 in the partition function, the code simply stops working (not malfunction, but completely stopped working as if some bigger error has happened.) What could be the reson.

#4

that is beacuse in array you work on index based approach.
if you will try to do implementation on that index where there is nothing then it will definitely give error .

#5

This reason can be ruled out because the value of e that I am sending is n-1 and not n. So, we are safe here. There has to be some other reason. I’ve attached the link for the code.

#6

@anshufirefox could you please tell the line number where you have experienced that.

#7

Please observe line 8. The code I’ve sent won’t work unless you change the limit value of j to e-1 instead of e.

#8

hey this is because:


see line 10 and 18 in this.
this is because when you are running it for e times then at any point i will become greater then e and thats why it is giving error.
in the above code i have commented i it is indeed printing the wrong result but yes it is running fine.
indexing of array is creating a problem.
Happy Learning !!

#9

Could you please help me close this thread by sending the rating link? (I’m unable to close it by marking it as resolved. The button doesn’t work on my profile. Have reported it to the support team).

#10

Hello @anshufirefox i told you dear that i can do it either
.even i am facing this issue students are not able to mark their doubt as resolved.
and they are showing pending in my profile.

#11

Thanks a lot, the rating link that you sent on the other thread helped me closed it. :slight_smile:

#12

I hope that method would work for this thread as well

#13

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#14

Thank you so much Bhaiya, Really helpful :slight_smile: