4 ms·

...I fully plan to use "O(whatever)". Not sure for what. But, yes. (naive) Quicksort's amortized complexity being O(nlogn), but its O(n^2) on already sorted da

...I fully plan to use "O(whatever)". Not sure for what. But, yes. (naive) Quicksort's amortized complexity being O(nlogn), but its O(n^2) on already sorted data, is all I ever needed to learn to take away that lesson. When sorting already sorted data is worse than sorting randomized data, it's a quick realization that "amortized cost" = "read the fine print".

nyanpasu64 6y ago
Quicksort as O(n log n) is not amortized complexity, but average runtime for random data.
- lostcolony 6y ago
  Fair point; I'm confusing my terminology. Analogy and realization still holds.
  - virgilp 6y ago
    Also, already sorted data.. in reverse order. If it's already sorted in the right order, quicksort takes linear time. This is an important difference - data you use might indeed often be appropriately sorted, but in practice will seldom be sorted in reverse order.
    - SuchAnonMuchWow 6y ago
      If it's already sorted in the right order, quicksort runs in O(n log n). quicksort is O(n log n) bestcase, O(n*n) worstcase.
      - virgilp 6y ago
        Actually, yeah, my original reply was dumb, I forgot quicksort :) It can be n*n for properly-sorted arrays too, depending on pivot selection (for randomized pivot selection, it's n log n).
        deleted 6y ago
        [deleted]
        lostcolony 6y ago
        Yes; random pivot selection is nlogn (unless you are very, very, statistically impossibly, unlucky. Or using very short arrays where it doesn't matter anyway). But I'm pretty sure data sorted in either direction (i.e., 'reversed' or not, ascending or descending), and taking a pivot from either end, is n^2. It doesn't have to be reversed; you always end up with everything unsorted ending up on one side or the other of the pivot, with each recursive step being just one less comparison than the step prior, meaning it has N-1 + N-2 + ... + 1 comparisons regardless of which way the array is sorted, or N(N-1)/2 comparisons total (Gauss' formula but starting at one less than the total number of items N, since that's the number of comparisons each step), which is O(N^2). There is no cause where it's linear time, unless you are first iterating across the array to select the first pivot that is out of place (which may be a reasonable optimization, but can also be made to apply regardless of what direction the array is sorted).
    - jameshart 6y ago
      On the contrary: very common UI pattern to have a data grid that sorts by a particular column when you click the header, then reverses that sort order when you click the header again. So for a user to sort by date, descending, they click the header, causing an ascending sort, then click it again, causing a descending one. Often such a grid will be quite well abstracted from its data source - it might be executing a remote query to return data in the new order every time - but I bet there are some examples out there that are backed by a local dataset and carry out an actual sort operation when you hit the header... and fall into a quicksort worst case if the user clicks the same header twice in a row.
- ncmncm 6y ago
  Interestingly, it is quite easy to double the speed of Quicksort, even at this late date, with just a couple-line change. <http://cantrip.org/sortfast.html http://cantrip.org/sortfast.html> Anyway I thought it was interesting.
- mcguire 6y ago
  Something that is amortized complexity: vector.push(x) Most of the time, it's O(1). Sometimes it's O(n). If you double the size of the backing array when it runs out of space, it's amortized O(1).
  - randomswede 6y ago
    Or triple, or quadruple. Or even (IIRC) "increase by 50%" (but, I would need to sit down and do the actual math on that). But, doubling a number is cheap and more conservative than quadrupling (the next "cheap" multiplier).
lloeki 6y ago
I (sadly) have to resort to use "O(scary)" too often for my taste. From: https://stackoverflow.com/a/185576/368409 https://stackoverflow.com/a/185576/368409 /* This is O(scary), but seems quick enough in practice. */

nyanpasu64 6y ago

Quicksort as O(n log n) is not amortized complexity, but average runtime for random data.

lostcolony 6y ago
Fair point; I'm confusing my terminology. Analogy and realization still holds.
- virgilp 6y ago
  Also, already sorted data.. in reverse order. If it's already sorted in the right order, quicksort takes linear time. This is an important difference - data you use might indeed often be appropriately sorted, but in practice will seldom be sorted in reverse order.
  - SuchAnonMuchWow 6y ago
    If it's already sorted in the right order, quicksort runs in O(n log n). quicksort is O(n log n) bestcase, O(n*n) worstcase.
    - virgilp 6y ago
      Actually, yeah, my original reply was dumb, I forgot quicksort :) It can be n*n for properly-sorted arrays too, depending on pivot selection (for randomized pivot selection, it's n log n).
      - deleted 6y ago
        [deleted]
      - lostcolony 6y ago
        Yes; random pivot selection is nlogn (unless you are very, very, statistically impossibly, unlucky. Or using very short arrays where it doesn't matter anyway). But I'm pretty sure data sorted in either direction (i.e., 'reversed' or not, ascending or descending), and taking a pivot from either end, is n^2. It doesn't have to be reversed; you always end up with everything unsorted ending up on one side or the other of the pivot, with each recursive step being just one less comparison than the step prior, meaning it has N-1 + N-2 + ... + 1 comparisons regardless of which way the array is sorted, or N(N-1)/2 comparisons total (Gauss' formula but starting at one less than the total number of items N, since that's the number of comparisons each step), which is O(N^2). There is no cause where it's linear time, unless you are first iterating across the array to select the first pivot that is out of place (which may be a reasonable optimization, but can also be made to apply regardless of what direction the array is sorted).
  - jameshart 6y ago
    On the contrary: very common UI pattern to have a data grid that sorts by a particular column when you click the header, then reverses that sort order when you click the header again. So for a user to sort by date, descending, they click the header, causing an ascending sort, then click it again, causing a descending one. Often such a grid will be quite well abstracted from its data source - it might be executing a remote query to return data in the new order every time - but I bet there are some examples out there that are backed by a local dataset and carry out an actual sort operation when you hit the header... and fall into a quicksort worst case if the user clicks the same header twice in a row.
ncmncm 6y ago
Interestingly, it is quite easy to double the speed of Quicksort, even at this late date, with just a couple-line change. <http://cantrip.org/sortfast.html http://cantrip.org/sortfast.html> Anyway I thought it was interesting.
mcguire 6y ago
Something that is amortized complexity: vector.push(x) Most of the time, it's O(1). Sometimes it's O(n). If you double the size of the backing array when it runs out of space, it's amortized O(1).
- randomswede 6y ago
  Or triple, or quadruple. Or even (IIRC) "increase by 50%" (but, I would need to sit down and do the actual math on that). But, doubling a number is cheap and more conservative than quadrupling (the next "cheap" multiplier).

lloeki 6y ago

I (sadly) have to resort to use "O(scary)" too often for my taste. From: https://stackoverflow.com/a/185576/368409 https://stackoverflow.com/a/185576/368409 /* This is O(scary), but seems quick enough in practice. */