5
$\begingroup$

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?

Heap sort:
best case - nlogn
worst case - nlogn

Quick sort:
best case - nlogn
worst case - n^2

Where I get confused on these two is:

  • 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?
  • 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.
$\endgroup$
  • 2
    $\begingroup$ You should realize that Quicksort is often implemented as a randomized algorithm. You seem not to know this. $\endgroup$ – Peter Shor Nov 26 '13 at 20:03
  • 2
    $\begingroup$ You should be aware of the difference between $n\log n$ and $O(n\log n)$. See Landau notation . $\endgroup$ – David Richerby Nov 26 '13 at 21:13
5
$\begingroup$

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?

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 Θ(n log n) - assuming all elements are distinct - only means that asymptotically 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.

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.

The number of pivots chosen is indeed the same regardless of the execution of the algorithm. However, the work done per pivot 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 Θ(log n) layers and each layer does Θ(n) work, the total work done is Θ(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 Θ(n2), hence the worst case.

Hope this helps!

$\endgroup$
  • $\begingroup$ Sir, how is best case of heapsort nlogn ? If we consider all elements are identical then the cost would be just iterating through all elements of the array and no shifting up till root. So it should be omega(n) according to me. $\endgroup$ – Zephyr Nov 10 '17 at 13:17
  • $\begingroup$ That’s a good point. I was assuming distinct elements, so I’ll go update this answer. $\endgroup$ – templatetypedef Nov 10 '17 at 16:36
3
$\begingroup$
  • Quick Sort

    Worst case: $\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.

    Let $T(n)$ be the number of comparisions quicksort requires to sort a list with $n$ elements. Worst case: \begin{align} T(n) = & T(n-1) + n & \text{($T(n-1)$ recursive, $n$ to partion)}\\ = & \frac{n(n+1)}{2} \in \mathcal{O}(n) \end{align}

    Best case: $\mathcal{O}(n \log n)$. If the pivot element is chosen in such way, that it partitions the list evenly:

    \begin{align} T(n) = & 2 \ T\left(\frac{n}{2}\right) + n & (\text {2 times $\frac{n}{2}$ recursive, $n$ to partition)} \\ \in & \mathcal{O}(n \log n) & (\text{master theorem}) \end{align}

  • Heap Sort

    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:

    \begin{align} & \mathcal{O}(n) & (\text{build $(1,n)$ heap}) \\ + & \sum_{i=1}^{n} \mathcal{O}(\log i - \log 1) & (\text{build $(1,j)$ heap}) \\ = & \mathcal{O}(n) + \sum_{i=1}^{n} \mathcal{O}(\log i) & (\text{logarithm quotient rule}) \\ = & \mathcal{O}(n \log n) & (\sum_{i=1}^{n} \log i < \sum_{i=1}^{n} \log n = n \log n) \end{align}

$\endgroup$
  • 2
    $\begingroup$ You haven't answered all the OP's questions, so I will answer one you missed; heap sort doesn't always use the same number of comparisons for a given number of elements. The worst case is $a\, n \log n$ and the best case is $b\, n \log n$, where $a > b$. $\endgroup$ – Peter Shor Nov 27 '13 at 18:47
  • $\begingroup$ Also note that the three-way variant has linear best case for single element input. $\endgroup$ – Ciro Santilli 新疆改造中心996ICU六四事件 Feb 11 '15 at 7:33
3
$\begingroup$

Since nobody's really addressed heapSort yet:

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.

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).

$\endgroup$
  • $\begingroup$ Your point on the lousy impractical case was just asked in my algorithms class. (beware of trick questions.) Of course, I'm still in agreement with your point. (and got my answer wrong as a result XD) $\endgroup$ – XChikuX Feb 13 '18 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.