3 deleted 1 character in body
source | link

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort usually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."

Edit:

Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $O(n)$ time, this gives $\Theta(n \log n)$ worst-case performance. However, since randomized quick-sortquicksort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used.

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort usually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."

Edit:

Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $O(n)$ time, this gives $\Theta(n \log n)$ worst-case performance. However, since randomized quick-sort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used.

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort usually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."

Edit:

Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $O(n)$ time, this gives $\Theta(n \log n)$ worst-case performance. However, since randomized quicksort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used.

2 added 405 characters in body
source | link

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort alwaysusually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."

Edit:

Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $O(n)$ time, this gives $\Theta(n \log n)$ worst-case performance. However, since randomized quick-sort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used.

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort always has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort usually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."

Edit:

Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $O(n)$ time, this gives $\Theta(n \log n)$ worst-case performance. However, since randomized quick-sort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used.

1
source | link

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort always has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."