4 ms·

I'm impressed you can write such a long story yet address none of my points. You should consider becoming a politician. The only relevant piece of information

I'm impressed you can write such a long story yet address none of my points. You should consider becoming a politician. The only relevant piece of information I could find in your anecdote is this: > I assumed that we were talking about in place sorting. If we limit ourselves to in-place sorting algorithms then we still are left with block sort, pdqsort, introsort and heap sort, all of which run in O(n log n). My argument still holds.

graycat 11y ago
I wrote that long post trying to explain my attitude on sorting software from 50,000 or so feet up and, in particular, why I have been happy just to use heap sort and forget about looking for anything faster on average. I was reluctant to read the documentation in your GitHub submission if only because in my software development I have never needed or used GitHub. Also, I was reluctant to believe that there could be any version of quicksort that would have worst case running time of O( n ln(n) ). Why reluctant to believe? First, sure, the usual version of quicksort has us select a pivot value for a partition from a "median of three" keys from that partition. Second, sure: For a good pivot value, we want essentially the median of the keys in the partition we are trying to split into two partitions. And, sure, the median of three approach to selecting a pivot value is an approximation to the median we really want and, thus, a relatively good pivot value. So this approach to selecting a pivot value promises on average to get faster average running times. Fine. Faster on average is good. Terrific. But this pivot selection rule says next to nothing about worst case running time, and, for claiming worst case running time of O( n ln(n) ), this is a biggie issue. Third, with this median of three approach to selecting pivot values, we can think of bad arrays of input keys that will cause quicksort to run in time no faster than O( n^2 ). Then maybe we can think of other ways to select pivot values that result in a new version of quicksort, a version that runs in O( n ln(n) ) again on the bad arrays. But with this change, here's the problem: We are lacking a proof that the worst case running time of the new version of quicksort has worst case running time of O( n ln(n) ). That is, our new version of quicksort is good for some old cases of bad arrays but may have created for itself some new cases of bad arrays. So, with no proof, the new version of quicksort may also have worst case running time of O( n^2 ) like the old version did. The main difference might be that the bad arrays for the new version are more complicated to construct than the bad arrays for the old case. But I just looked at the file README.MD you suggested. I see two issues: First Issue: > When a new pivot is chosen it's compared to the greatest element in the partition before it. If they compare equal we can derive that there are no elements smaller than the chosen pivot. When this happens we switch strategy for this partition, and filter out all elements equal to the pivot. If I understand this statement correctly, I suspect that for some arrays of input keys, the resulting algorithm won't actually sort the keys. That is, we won't have a sorting algorithm. Second Issue: > While this technically still allows for a quadratic worst case, the chances of it happening are astronomically small. For proving worst case running time of O( n ln(n) ), "astronomically small" is irrelevant. Maybe your remark "astronomically small" is just a side comment and not relevant to PDQSORT having worst case running time of O( n ln(n) ), but from your documentation I can't easily tell. > A bad partition occurs when the position of the pivot after partitioning is under 12.5% (1/8th) percentile or over 87,5% percentile - the partition is highly unbalanced. When this happens we will shuffle four elements at fixed locations for both partitions. This effectively breaks up many patterns. If we encounter more than log(n) bad partitions we will switch to heap sort. For this and the associated documentation, I don't see a solid argument that PDQSORT has worst case running time of O( n ln(n) ). For some work, a big-O guarantee on worst case performance is a biggie, as in crucial to human life. Such a guarantee is essentially a theorem in applied math called computer science. A good example of how to prove such theorems is, of course, in D. Knuth, The Art of Computer Programming, Volume 3, Sorting and Searching. Again, I have been happy just to use heap sort and forget about looking for anything faster on average.
- nightcracker 11y ago
  > If I understand this statement correctly, I suspect that for some arrays of input keys, the resulting algorithm won't actually sort the keys. That is, we won't have a sorting algorithm. You don't understand the statement correctly. However, this is not a trivial realization. Because pdqsort always recurses on the left partition first it means that every element to the left of the current recursive call is equal to or less than every element within the current recursive call. So if we find that the selected pivot is equal to an element before the current recursive call we can conclude that there can only be elements equal to the pivot, and not smaller, in the current recursive call. > Maybe your remark "astronomically small" is just a side comment and not relevant to PDQSORT having worst case running time of O( n ln(n) ). Correct. > For this and the associated documentation, I don't see a solid argument that PDQSORT has worst case running time of O( n ln(n) ). There is a very simple argument. The 'bad partition counter' is initially log(n). If we encounter a bad partition, we can do up to O(n) work. This can happen log(n) times. So we can do up to O(n log n) work on bad partitions. If we then encounter another bad partition, we switch to heapsort, which is O(n log n). If we encounter less than log(n) bad partitions Quicksort performed well enough to be O(n log n). For a similar approach, read up on introsort.
  - graycat 11y ago
    Okay.

graycat 11y ago

I wrote that long post trying to explain my attitude on sorting software from 50,000 or so feet up and, in particular, why I have been happy just to use heap sort and forget about looking for anything faster on average. I was reluctant to read the documentation in your GitHub submission if only because in my software development I have never needed or used GitHub. Also, I was reluctant to believe that there could be any version of quicksort that would have worst case running time of O( n ln(n) ). Why reluctant to believe? First, sure, the usual version of quicksort has us select a pivot value for a partition from a "median of three" keys from that partition. Second, sure: For a good pivot value, we want essentially the median of the keys in the partition we are trying to split into two partitions. And, sure, the median of three approach to selecting a pivot value is an approximation to the median we really want and, thus, a relatively good pivot value. So this approach to selecting a pivot value promises on average to get faster average running times. Fine. Faster on average is good. Terrific. But this pivot selection rule says next to nothing about worst case running time, and, for claiming worst case running time of O( n ln(n) ), this is a biggie issue. Third, with this median of three approach to selecting pivot values, we can think of bad arrays of input keys that will cause quicksort to run in time no faster than O( n^2 ). Then maybe we can think of other ways to select pivot values that result in a new version of quicksort, a version that runs in O( n ln(n) ) again on the bad arrays. But with this change, here's the problem: We are lacking a proof that the worst case running time of the new version of quicksort has worst case running time of O( n ln(n) ). That is, our new version of quicksort is good for some old cases of bad arrays but may have created for itself some new cases of bad arrays. So, with no proof, the new version of quicksort may also have worst case running time of O( n^2 ) like the old version did. The main difference might be that the bad arrays for the new version are more complicated to construct than the bad arrays for the old case. But I just looked at the file README.MD you suggested. I see two issues: First Issue: > When a new pivot is chosen it's compared to the greatest element in the partition before it. If they compare equal we can derive that there are no elements smaller than the chosen pivot. When this happens we switch strategy for this partition, and filter out all elements equal to the pivot. If I understand this statement correctly, I suspect that for some arrays of input keys, the resulting algorithm won't actually sort the keys. That is, we won't have a sorting algorithm. Second Issue: > While this technically still allows for a quadratic worst case, the chances of it happening are astronomically small. For proving worst case running time of O( n ln(n) ), "astronomically small" is irrelevant. Maybe your remark "astronomically small" is just a side comment and not relevant to PDQSORT having worst case running time of O( n ln(n) ), but from your documentation I can't easily tell. > A bad partition occurs when the position of the pivot after partitioning is under 12.5% (1/8th) percentile or over 87,5% percentile - the partition is highly unbalanced. When this happens we will shuffle four elements at fixed locations for both partitions. This effectively breaks up many patterns. If we encounter more than log(n) bad partitions we will switch to heap sort. For this and the associated documentation, I don't see a solid argument that PDQSORT has worst case running time of O( n ln(n) ). For some work, a big-O guarantee on worst case performance is a biggie, as in crucial to human life. Such a guarantee is essentially a theorem in applied math called computer science. A good example of how to prove such theorems is, of course, in D. Knuth, The Art of Computer Programming, Volume 3, Sorting and Searching. Again, I have been happy just to use heap sort and forget about looking for anything faster on average.

nightcracker 11y ago
> If I understand this statement correctly, I suspect that for some arrays of input keys, the resulting algorithm won't actually sort the keys. That is, we won't have a sorting algorithm. You don't understand the statement correctly. However, this is not a trivial realization. Because pdqsort always recurses on the left partition first it means that every element to the left of the current recursive call is equal to or less than every element within the current recursive call. So if we find that the selected pivot is equal to an element before the current recursive call we can conclude that there can only be elements equal to the pivot, and not smaller, in the current recursive call. > Maybe your remark "astronomically small" is just a side comment and not relevant to PDQSORT having worst case running time of O( n ln(n) ). Correct. > For this and the associated documentation, I don't see a solid argument that PDQSORT has worst case running time of O( n ln(n) ). There is a very simple argument. The 'bad partition counter' is initially log(n). If we encounter a bad partition, we can do up to O(n) work. This can happen log(n) times. So we can do up to O(n log n) work on bad partitions. If we then encounter another bad partition, we switch to heapsort, which is O(n log n). If we encounter less than log(n) bad partitions Quicksort performed well enough to be O(n log n). For a similar approach, read up on introsort.
- graycat 11y ago
  Okay.