Best and worse case inputs for heap sort and quick sort? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:18:23Z https://cs.stackexchange.com/feeds/question/18391 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/18391 5 Best and worse case inputs for heap sort and quick sort? aisdmsaidmas https://cs.stackexchange.com/users/11638 2013-11-26T17:43:11Z 2017-11-10T16:37:28Z <p>So given an input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts?</p> <pre><code>Heap sort: best case - nlogn worst case - nlogn Quick sort: best case - nlogn worst case - n^2 </code></pre> <p>Where I get confused on these two is:</p> <ul> <li><strong>heap</strong>- Since the best and worst case are the same does it not matter the input order? The number of comparisons and assignments will always be the same? I imagine in a heap sort it may be the same since the real work is done in the insertion, but the sorting only uses the removal of the max/min heap? Is that why?</li> <li><strong>quick sort</strong>- This one I don't know for sure. I'm not sure what the best case and worst case situations are for this. If its a already sorted list of 10 strings for example wouldn't we always have to choose the same amount of pivots to get complete the recursive algorithm? Any help on this explanation would really help.</li> </ul> https://cs.stackexchange.com/questions/18391/-/18396#18396 3 Answer by Gaste for Best and worse case inputs for heap sort and quick sort? Gaste https://cs.stackexchange.com/users/11318 2013-11-26T21:03:49Z 2013-11-26T21:03:49Z <ul> <li><p><strong>Quick Sort</strong></p> <p><strong>Worst case:</strong> $\mathcal{O}(n^2)$. Lets assume the pivot element is always the right-most element: Input an already sorted list with $n$ elements. So each partitioning leads to one list with $n-1$ elements and one list with $0$ elements. Even if you choose the pivot element randomly, you can still be unlucky and always choose the maximum value in the list.</p> <p>Let $T(n)$ be the number of comparisions quicksort requires to sort a list with $n$ elements. Worst case: \begin{align} T(n) = &amp; T(n-1) + n &amp; \text{($T(n-1)$ recursive, $n$ to partion)}\\ = &amp; \frac{n(n+1)}{2} \in \mathcal{O}(n) \end{align}</p> <p><strong>Best case:</strong> $\mathcal{O}(n \log n)$. If the pivot element is chosen in such way, that it partitions the list evenly:</p> <p>\begin{align} T(n) = &amp; 2 \ T\left(\frac{n}{2}\right) + n &amp; (\text {2 times $\frac{n}{2}$ recursive, $n$ to partition)} \\ \in &amp; \mathcal{O}(n \log n) &amp; (\text{master theorem}) \end{align}</p></li> <li><p><strong>Heap Sort</strong></p> <p>The worst case and best case complexity for heap sort are both $\mathcal{O}(n \log n)$. Therefore heap sort needs $\mathcal{O}(n \log n)$ comparisons for any input array. Complexity of heap sort:</p> <p>\begin{align} &amp; \mathcal{O}(n) &amp; (\text{build $(1,n)$ heap}) \\ + &amp; \sum_{i=1}^{n} \mathcal{O}(\log i - \log 1) &amp; (\text{build $(1,j)$ heap}) \\ = &amp; \mathcal{O}(n) + \sum_{i=1}^{n} \mathcal{O}(\log i) &amp; (\text{logarithm quotient rule}) \\ = &amp; \mathcal{O}(n \log n) &amp; (\sum_{i=1}^{n} \log i &lt; \sum_{i=1}^{n} \log n = n \log n) \end{align}</p></li> </ul> https://cs.stackexchange.com/questions/18391/-/18946#18946 5 Answer by templatetypedef for Best and worse case inputs for heap sort and quick sort? templatetypedef https://cs.stackexchange.com/users/2131 2013-11-28T05:47:37Z 2017-11-10T16:37:28Z <blockquote> <p>heap- Since the best and worst case are the same does it not matter the input order? The number of comparisons and assignments will always be the same? I imagine in a heap sort it may be the same since the real work is done in the insertion, but the sorting only uses the removal of the max/min heap? Is that why?</p> </blockquote> <p>The number of comparisons made actually can depend on the order in which the values are given. The fact that the best and worst case are each &Theta;(n log n) - assuming all elements are distinct - only means that <em>asymptotically</em> there's no difference between the two, though they can differ by a constant factor. I don't have any simple examples of this off the top of my head, but I believe that you can construct inputs where the number of comparisons differs by a constant factor between the two approaches. Since big-O notation ignores constants, though, this isn't reflected in the best-case and worst-case analysis.</p> <blockquote> <p>quick sort- This one I don't know for sure. I'm not sure what the best case and worst case situations are for this. If its a already sorted list of 10 strings for example wouldn't we always have to choose the same amount of pivots to get complete the recursive algorithm? Any help on this explanation would really help.</p> </blockquote> <p>The number of pivots chosen is indeed the same regardless of the execution of the algorithm. However, the <em>work done per pivot</em> can vary based on what sort of splits you get. In the best case, the pivot chosen at each step ends up being the median element of the array. When this happens, there are (roughly) n comparisons done at the top layer of the recursion, then (roughly) n at the next layer because there are two subarrays of size n / 2, then there are (roughly) n at the next layer because there are four subarrays of size n / 4, etc. Since there are &Theta;(log n) layers and each layer does &Theta;(n) work, the total work done is &Theta;(n log n). On the other hand, consider choosing the absolute minimum of each array as a pivot. Then (roughly) n compares are done at the top layer, then (roughly) n - 1 in the next layer, then (roughly) n - 2 in the next, etc. The sum 1 + 2 + 3 + ... + n is &Theta;(n<sup>2</sup>), hence the worst case.</p> <p>Hope this helps!</p> https://cs.stackexchange.com/questions/18391/-/75176#75176 3 Answer by Mia for Best and worse case inputs for heap sort and quick sort? Mia https://cs.stackexchange.com/users/71809 2017-05-09T21:02:49Z 2017-05-09T21:02:49Z <p>Since nobody's really addressed heapSort yet: </p> <p>Assuming you're using a max heap represented as an array and inserting your max elements backwards into your output array/into the back of your array if you're doing it in-place, the worst case input for heapSort is any input that forces you to "bubble down" or reheapify every time you remove an element. This happens every time you are trying to sort a set with no duplicates. It will still be Θ(n log n), as templatetypedef said.</p> <p>This property implies that heapSort's best-case is when all elements are equal (Θ(n), since you don't have to reheapify after every removal, which takes log(n) time since the max height of the heap is log(n)). It's kind of a lousy/impractical case, though, which is why the real best case for heapsort is Θ(n log n). </p>