4 ms·

I think you are getting your information mixed up. Here is a comparison that shows quicksort running in 1/10th the time as heapsort. https://johnysswlab.com/wh

I think you are getting your information mixed up. Here is a comparison that shows quicksort running in 1/10th the time as heapsort. https://johnysswlab.com/why-is-quicksort-faster-than-heapsort-and-how-to-make-them-faster/ https://johnysswlab.com/why-is-quicksort-faster-than-heapsor...

xdavidliu 3y ago
we're talking about asymptotics (i.e. the exponent). Things like "1/10 the time" are utterly meaningless here.
- CyberDildonics 3y ago
  Who is talking about that? They said 'faster' not less algorithmic complexity. 1/10th the time is much faster.
  - graycat 3y ago
    > 1/10th the time is much faster. No, absolutely no, it's not in any meaningful or useful sense "faster" as in which algorithm is "faster". You utterly fail to get this point.
    - CyberDildonics 3y ago
      If something runs in less time, it's faster. If something runs in 1/10th the time as something else it is multiple orders of magnitude faster. I don't think I've ever seen someone try to redefine 'faster' before. You keep trying to equate naive algorithmic complexity and speed, but you haven't even linked anything that shows heapsort is better than other sorts like quicksort at that. You haven't actually linked anything to back up any of what you're saying, even the irrelevant offtopic claims.
graycat 3y ago
Versions of quick sort differ in how the partitions are determined. A guess is that some of the versions are not worst case O(n log n) for sorting n keys. In that case, for sufficiently large n, on a normal computer, any version of heap sort will beat that version of quick sort in number of comparisons, time in seconds, Joules of energy to run the computer, etc. It is this point that has much of the academic computer science community saying that no sorting algorithm based on comparing keys two at a time can beat heap sort. Sure, we don't know how big n has to be. In practice, in an actual case, the n might have to be too big for current computers. Sure, in practice, for some value of n, on some list of n keys, some version of heap sort, and some version of quick sort, the quick sort might run 10 times faster in seconds of elapsed time than heap sort.
- CyberDildonics 3y ago
  I'm not completely sure what you are saying, but do you actually think a heap sort is in general faster than a quicksort or mergesort? You realize that the worst case of a quick sort is easily avoided right? The only way it happens is if you have an already sorted array and you pick your pivots from the minimum or maximum values on every single partition. It is this point that has much of the academic computer science community saying that no sorting algorithm based on comparing keys two at a time can beat heap sort. I think you're the only one saying that. Where did you get this idea? I just showed you a quicksort being 10 times faster than a heapsort. You can try this for yourself. Sure, we don't know how big n has to be. In practice, in an actual case, the n might have to be too big for current computers. This is never going to be true. Quicksort and other sorts exploit locality much better. Partitioning an array gradually makes the sorting more local. That's going to work better relatively to a heap sort as data gets bigger, not worse. Sure, in practice, for some value of n, on some list of n keys, some version of heap sort, and some version of quick sort, the quick sort might run 10 times faster in seconds of elapsed time than heap sort. No, on any modern computer other sorts are going to beat a heapsort. It isn't exotic, it is how it works. Even if you have to scan every element first to get a distribution of your elements to choose your pivot, that is still going to be O(n log n) and it will still beat a heap sort. Heap sorts are not the fastest way to sort. They can be consistent and they can split the time between inserting and extracting elements.

xdavidliu 3y ago

we're talking about asymptotics (i.e. the exponent). Things like "1/10 the time" are utterly meaningless here.

CyberDildonics 3y ago
Who is talking about that? They said 'faster' not less algorithmic complexity. 1/10th the time is much faster.
- graycat 3y ago
  > 1/10th the time is much faster. No, absolutely no, it's not in any meaningful or useful sense "faster" as in which algorithm is "faster". You utterly fail to get this point.
  - CyberDildonics 3y ago
    If something runs in less time, it's faster. If something runs in 1/10th the time as something else it is multiple orders of magnitude faster. I don't think I've ever seen someone try to redefine 'faster' before. You keep trying to equate naive algorithmic complexity and speed, but you haven't even linked anything that shows heapsort is better than other sorts like quicksort at that. You haven't actually linked anything to back up any of what you're saying, even the irrelevant offtopic claims.

graycat 3y ago

Versions of quick sort differ in how the partitions are determined. A guess is that some of the versions are not worst case O(n log n) for sorting n keys. In that case, for sufficiently large n, on a normal computer, any version of heap sort will beat that version of quick sort in number of comparisons, time in seconds, Joules of energy to run the computer, etc. It is this point that has much of the academic computer science community saying that no sorting algorithm based on comparing keys two at a time can beat heap sort. Sure, we don't know how big n has to be. In practice, in an actual case, the n might have to be too big for current computers. Sure, in practice, for some value of n, on some list of n keys, some version of heap sort, and some version of quick sort, the quick sort might run 10 times faster in seconds of elapsed time than heap sort.

CyberDildonics 3y ago
I'm not completely sure what you are saying, but do you actually think a heap sort is in general faster than a quicksort or mergesort? You realize that the worst case of a quick sort is easily avoided right? The only way it happens is if you have an already sorted array and you pick your pivots from the minimum or maximum values on every single partition. It is this point that has much of the academic computer science community saying that no sorting algorithm based on comparing keys two at a time can beat heap sort. I think you're the only one saying that. Where did you get this idea? I just showed you a quicksort being 10 times faster than a heapsort. You can try this for yourself. Sure, we don't know how big n has to be. In practice, in an actual case, the n might have to be too big for current computers. This is never going to be true. Quicksort and other sorts exploit locality much better. Partitioning an array gradually makes the sorting more local. That's going to work better relatively to a heap sort as data gets bigger, not worse. Sure, in practice, for some value of n, on some list of n keys, some version of heap sort, and some version of quick sort, the quick sort might run 10 times faster in seconds of elapsed time than heap sort. No, on any modern computer other sorts are going to beat a heapsort. It isn't exotic, it is how it works. Even if you have to scan every element first to get a distribution of your elements to choose your pivot, that is still going to be O(n log n) and it will still beat a heap sort. Heap sorts are not the fastest way to sort. They can be consistent and they can split the time between inserting and extracting elements.