Find a Best-Case Example of QuickSort

[Dada]

Homework Statement

Construct a best-case example for Quicksort with n = 15

Relevant Equations

Please see the images for algorithm of QuickSort

Hello to those who visit!

Give a question "Construct a best-case example for Quicksort with n = 15", please explain how to get this case? Is there other special cases too if possible?
The following images are the algorithm of Quicksort.

My guess is that if I sort them in order or use number repeatedly, then will it be the best case example?

Thank You!

 

[Mark44]

Homework Statement:: Construct a best-case example for Quicksort with n = 15
Relevant Equations:: Please see the images for algorithm of QuickSort

Hello to those who visit!

Give a question "Construct a best-case example for Quicksort with n = 15", please explain how to get this case? Is there other special cases too if possible?
The following images are the algorithm of Quicksort.

My guess is that if I sort them in order or use number repeatedly, then will it be the best case example?

Thank You!

No, that's not what the problem is asking for. Instead, they are looking for a set of 15 numbers arranged in some order, Quicksort will operate in the least amount of time. For example, another sort algorithm has a worst-case time if the numbers are sorted in the opposite order from the order that they should be in.

 

[Dada]

No, that's not what the problem is asking for. Instead, they are looking for a set of 15 numbers arranged in some order, Quicksort will operate in the least amount of time. For example, another sort algorithm has a worst-case time if the numbers are sorted in the opposite order from the order that they should be in.

Hello, Mark44!

Thanks for your clarification of my problem.

I am still struggling with how to make begin though the process of this problem.

Is it possible that you can provide me the best-case of n=5 as a model? Then I will try to figure out when n =15. When you provide me your best-case, please provide me your thought process if possible!

Thank You!

 

[Mark44]

Is it possible that you can provide me the best-case of n=5 as a model? Then I will try to figure out when n =15. When you provide me your best-case, please provide me your thought process if possible!

No, I can't do this due to the forum rules. Look in your textbook where they talk about best-case and worst-case scenarios for different sort algorithms.

 

[Dada]

No, I can't do this due to the forum rules. Look in your textbook where they talk about best-case and worst-case scenarios for different sort algorithms.

Okay, Mark44!

However, my textbook does not provide me the best-case or worst-case scenarios since it only provides the steps of processing the Quicksort algorithm, like showing how it works. This Quicksort only belongs to a section, so it does not spend more pages on those scenarios.

I will look for good info from others' websites to see whether they mention about those scenarios.

Thank you for answer my previous questions!

 

[Vanadium 50]

I will look for good info from others' websites to see whether they mention about those scenarios.

That sounds a lot like "I'll cheat somewhere else, thank you". I'm sure you can get an answer somewhere. I am not sure that the skill of Googling places to steal borrow other's work is as marketable as people seem to think it is.

What you should do instead is to run quicksort by hand with a small number of values to see what it is doing. Do this a few times with varying lengths and varying orders until you learn what quicksort is doing. Then you can answer the question on your own.

 

[Dada]

That sounds a lot like "I'll cheat somewhere else, thank you". I'm sure you can get an answer somewhere. I am not sure that the skill of Googling places to steal borrow other's work is as marketable as people seem to think it is.

What you should do instead is to run quicksort by hand with a small number of values to see what it is doing. Do this a few times with varying lengths and varying orders until you learn what quicksort is doing. Then you can answer the question on your own.

Hello, Vanadium 50!

Thank you for providing me a hint of Quicksort -- by testing "varying lengths"!

Before I posted this thread, I do understand how it works, which it compares and put the last element of array to the position that the left side elements are less that it and the right side elements are greater or equal it. Also, I spent about 15 min on this question after I have done another exercise for Quicksort.

From my textbook, I think it does not provide any info for the best-case scenario from my understanding of reading.

About the skill of Googling, I do agree that people are doing it a lot, including me, which is not a good habit since people will not learn much. However, the reason that I did not google my question before I come to here first is that here could provide some hints, or walk me through questions and let me understand more questions' requirements, as Mark44 has clarified about my guess is impossible. And I did spend some time on it again, but I did not get it, so I asked for help again if possible by providing me an example.

I did spend a lot of time on this problem but did not get any progress. I am a human, so I will get frustrated, but I still want to complete it if possible. I did ask my professor by email, but since his office hours are not today, I think I will not get responded soon.

So yes, about the skill of Googling, I did use it to find useful info if possible, but I still cannot find any example. However, I did get a hint from an idea, as you said, try to test "varying length." -- always cut the array into half repeatedly will provide the best-case scenario. And I did figure out the answer at the end for n = 15. I think my answer is correct when I used Quicksort to process, and it came out with a good result.

If you want to help me check my calculated answer, I can post here. Dada

 

[QuantumQuest]

@Dada let me make a few comments drawing from my own background and experience.
First, I totally agree to what @Mark44 and @Vanadium 50 have already said.

In order to understand how an algorithm does its job, you have to do it with pen and paper first. So, beginning from the general strategy that the algorithm follows - for example divide-and-conquer, dynamic programming, greedy etc., you first check what the algorithm utilizes to achieve it, referring mainly to the data structure(s) it utilizes. Then, you go lower into details and see how it really does it using abstractions of programming constructs (if clauses, loops etc.) i.e. I'm referring to pseudocode here - like the one you have in your attachment. Along the way, you have to keep in mind the special features the algorithm has - for instance Quicksort has the pivot value. So, using pen and paper first, you run the algorithm for different sets of values for various (relatively small) numbers of values. When you have sufficiently understood the way the algorithm works, you're (hopefully ;) ) ready to implement it using some programming language.

Now, for the running time of Quicksort algorithm, the first thing I'd point out is that it depends on the quality of the pivot. If you don't fully understand this - I don't say you don't, you have to study the way Quicksort works more thoroughly. What is the best case running time and when do we achieve it - the same for worst case scenario? How do we choose the pivot in the first place? These are both important questions you'll need to be able to answer.

 

[Dada]

@QuantumQuest

Thank you for your reply, providing your instructions on showing how I should work on algorithms when I am not familiar with, and suggesting me two important cases I need to learn.

Since I am probably done with the best-case, I will try to figure out the worst-case scenario by myself if possible. I will review the Quicksort algorithm first by writing the steps down several times more to understand deeper, and then continue to work on the worst-case scenario.